Sampling in dynamic data streams and applications
G. Frahling, P. Indyk, C. Sohler, in: Proceedings of the Twenty-First Annual Symposium on Computational Geometry - SCG ’05, 2005.
Download
No fulltext has been uploaded.
Conference Paper
| Published
| English
Author
Frahling, Gereon;
Indyk, Piotr;
Sohler, Christian
Abstract
A dynamic geometric data stream is a sequence of m Add/Remove operations of points from a discrete geometric space (1,...,Δ)d [21]. Add(p) inserts a point p from (1,...,Δ)d into the current point set, Remove(p) deletes p from P. We develop low-storage data structures to (i) maintain ε-approximations of range spaces of P with constant VC-dimension and (ii) maintain an ε-approximation of the weight of the Euclidean minimum spanning tree of P. Our data structures use O(log3ε • log3(1/ε) • log(1/ε)/ε2) and O(log (1/δ) • (log Δ/ε)O(d)) bits of memory, respectively (we assume that the dimension d is a constant), and they are correct with probability 1-δ. These results are based on a new data structure that maintains a set of elements chosen (almost) uniformly at random from P.
Publishing Year
Proceedings Title
Proceedings of the twenty-first annual symposium on Computational geometry - SCG '05
LibreCat-ID
Cite this
Frahling G, Indyk P, Sohler C. Sampling in dynamic data streams and applications. In: Proceedings of the Twenty-First Annual Symposium on Computational Geometry - SCG ’05. ; 2005. doi:10.1145/1064092.1064116
Frahling, G., Indyk, P., & Sohler, C. (2005). Sampling in dynamic data streams and applications. In Proceedings of the twenty-first annual symposium on Computational geometry - SCG ’05. https://doi.org/10.1145/1064092.1064116
@inproceedings{Frahling_Indyk_Sohler_2005, title={Sampling in dynamic data streams and applications}, DOI={10.1145/1064092.1064116}, booktitle={Proceedings of the twenty-first annual symposium on Computational geometry - SCG ’05}, author={Frahling, Gereon and Indyk, Piotr and Sohler, Christian}, year={2005} }
Frahling, Gereon, Piotr Indyk, and Christian Sohler. “Sampling in Dynamic Data Streams and Applications.” In Proceedings of the Twenty-First Annual Symposium on Computational Geometry - SCG ’05, 2005. https://doi.org/10.1145/1064092.1064116.
G. Frahling, P. Indyk, and C. Sohler, “Sampling in dynamic data streams and applications,” in Proceedings of the twenty-first annual symposium on Computational geometry - SCG ’05, 2005.
Frahling, Gereon, et al. “Sampling in Dynamic Data Streams and Applications.” Proceedings of the Twenty-First Annual Symposium on Computational Geometry - SCG ’05, 2005, doi:10.1145/1064092.1064116.
Google Scholar