License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.62
URN: urn:nbn:de:0030-drops-95250
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9525/
Go to the corresponding LIPIcs Volume Portal

Matheny, Michael ; Phillips, Jeff M.

Practical Low-Dimensional Halfspace Range Space Sampling

pdf-format:
LIPIcs-ESA-2018-62.pdf (0.6 MB)

Abstract

We develop, analyze, implement, and compare new algorithms for creating epsilon-samples of range spaces defined by halfspaces which have size sub-quadratic in 1/epsilon, and have runtime linear in the input size and near-quadratic in 1/epsilon. The key to our solution is an efficient construction of partition trees. Despite not requiring any techniques developed after the early 1990s, apparently such a result was never explicitly described. We demonstrate that our implementations, including new implementations of several variants of partition trees, do indeed run in time linear in the input, appear to run linear in output size, and observe smaller error for the same size sample compared to the ubiquitous random sample (which requires size quadratic in 1/epsilon). This result has direct applications in speeding up discrepancy evaluation, approximate range counting, and spatial anomaly detection.

BibTeX - Entry

@InProceedings{matheny_et_al:LIPIcs:2018:9525,
  author =	{Michael Matheny and Jeff M. Phillips},
  title =	{{Practical Low-Dimensional Halfspace Range Space Sampling}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{62:1--62:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9525},
  URN =		{urn:nbn:de:0030-drops-95250},
  doi =		{10.4230/LIPIcs.ESA.2018.62},
  annote =	{Keywords: Partitions, Range Spaces, Sampling, Halfspaces}
}

Keywords: Partitions, Range Spaces, Sampling, Halfspaces
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI