Cited By
View all- Cormode GJowhari H(2019)L Samplers and Their ApplicationsACM Computing Surveys10.1145/329771552:1(1-31)Online publication date: 13-Feb-2019
Width of Points in the Streaming Model
Article No.: 5, Pages 1 - 10
Abstract
In this article, we show how to compute the width of a dynamic set of low-dimensional points in the streaming model. In particular, we assume that the stream contains both insertions of points and deletions of points to a set S, and the goal is to compute the width of the set S, namely the minimal distance between two parallel hyperplanes sandwiching the point set S.
Our algorithm (1 + ϵ) approximates the width of the set S using space polylogarithmic in the size of S and the aspect ratio of S. This is the first such algorithm that supports both insertions and deletions of points to the set S: previous algorithms for approximating the width of a point set only supported additions [Agarwal et al. 2004; Chan 2006], or a sliding window [Chan and Sadjad 2006].
This solves an open question from the “2009 Kanpur list” of open problems in data streams, property testing, and related topics [Indyk et al. 2011].
References
[1]
Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. 2004. Approximating extent measures of points. Journal of the ACM 51, 4, 606--635.
[2]
Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. 2005. Geometric approximation via coresets—survey. In Combinatorial and Computational Geometry. University Press.
[3]
Saugata Basu, Richard Pollack, and Marie-Françoise Roy. 1996. On the combinatorial and algebraic complexity of quantifier elimination. Journal of the ACM 43, 6, 1002--1045.
[4]
Timothy M. Chan. 2006. Faster core-set constructions and data-stream algorithms in fixed dimensions. Computational Geometry 35, 1--2, 20--35.
[5]
Timothy M. Chan. 2009. Dynamic coresets. Discrete Computational Geometry 42, 3, 469--488.
[6]
Timothy M. Chan and Bashir S. Sadjad. 2006. Geometric optimization problems over sliding windows. International Journal of Computational Geometry and Applications 16, 2--3, 145--158.
[7]
Joan Feigenbaum, Sampath Kannan, and Jian Zhang. 2004. Computing diameter in the streaming and sliding-window models. Algorithmica 41, 1, 25--41.
[8]
Gereon Frahling, Piotr Indyk, and Christian Sohler. 2005. Sampling in dynamic data streams and applications. In Proceedings of the Symposium on Computational Geometry (SoCG’05). 142--149.
[9]
Gereon Frahling and Christian Sohler. 2005. Coresets in dynamic geometric data streams. In Proceedings of the Symposium on Theory of Computing (STOC’05). 209--217.
[10]
Piotr Indyk. 2004. Algorithms for dynamic geometric problems over data streams. In Proceedings of the Symposium on Theory of Computing (STOC’04). 373--380.
[11]
Piotr Indyk, Moshe Lewenstein, Ohad Lipsky, and Ely Porat. 2004. Closest pair problems in very high dimensions. In Proceedings of International Colloquium on Automata, Languages, and Programming (ICALP’04). 782--792.
[12]
Piotr Indyk, Andrew McGregor, Ilan Newman, and Krzysztof Onak. 2011. Open problems in data streams, property testing, and related topics. Retrieved December 8, 2015, from http://www.cs.umass.edu/mcgregor/papers/11-openproblems.pdf.
[13]
Muthu Muthukrishnan. 2005. Data Streams: Algorithms and Applications. Now Publishers.
[14]
Kasturi Varadarajan and Xin Xiao. 2012. A near-linear algorithm for projective clustering integer points. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’12). 1329--1342.
Index Terms
- Width of Points in the Streaming Model
Recommendations
Width of points in the streaming model
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithmsWe show how to compute the width of a dynamic set of low-dimensional points in the streaming model. In particular, we assume the stream contains both insertions of points and deletions of points to a set S, and the goal is to compute the width of the ...
Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions
AbstractIn this paper we present efficient algorithms to compute the radius, diameter, incenter, circumcenter, width and k dimensional enclosing cylinder for convex polyhedral and convex polyhedral offset distance functions in plane and in ℜ d ...
Range-aggregate queries for geometric extent problems
CATS '13: Proceedings of the Nineteenth Computing: The Australasian Theory Symposium - Volume 141Let S be a set of n points in the plane. We present data structures that solve range-aggregate query problems on three geometric extent measure problems. Using these data structures, we can report, for any axis-parallel query rectangle Q, the area/...
Comments
Information & Contributors
Information
Published In
February 2016
243 pages
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Accepted: 01 December 2016
Revised: 01 December 2016
Published: 08 February 2016
Received: 01 June 2012
Published in TALG Volume 12, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
- National Science Foundation (NSF)
- Gordon Wu fellowship
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 136Total Downloads
- Downloads (Last 12 months)15
- Downloads (Last 6 weeks)7
Reflects downloads up to 22 Oct 2024
Other Metrics
Citations
Cited By
View all- Cormode GJowhari H(2019)L Samplers and Their ApplicationsACM Computing Surveys10.1145/329771552:1(1-31)Online publication date: 13-Feb-2019
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in