文章基本信息

标题：Practical Low-Dimensional Halfspace Range Space Sampling
本地全文：下载
作者：Michael Matheny ; Jeff M. Phillips
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：112
页码：1-14
DOI：10.4230/LIPIcs.ESA.2018.62
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Partitions; Range Spaces; Sampling; Halfspaces