Algorithms for dynamic geometric problems over data streams. (English) Zbl 1192.68179
Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 373-380, electronic only (2004).
For the entire collection see [Zbl 1074.68504].
References:
| [1] | N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. Proceedings of the Symposium on Theory of Computing, pages 20-29, 1996.]] 10.1145/237814.237823 · Zbl 0922.68057 |
| [2] | V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristics for k-median and facility location problems. Proceedings of the Symposium on Theory of Computing, 2002.]] 10.1145/380752.380755 |
| [3] | Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. Proceedings of the Symposium on Foundations of Computer Science, 1996.]] |
| [4] | M. Charikar. Similarity estimation techniques from rounding. Proceedings of the Symposium on Theory of Computing, 2002.]] 10.1145/509907.509965 |
| [5] | M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. Plotkin. Approximating a finite metric by a small number of tree metrics. Proceedings of the Symposium on Foundations of Computer Science, 1998.]] |
| [6] | M. Charikar, L. O’Callaghan, and R. Panigrahy. Better streaming algorithms for clustering problems. Proceedings of the Symposium on Theory of Computing, pages 30-39, 2003.]] 10.1145/780542.780548 · Zbl 1192.68350 |
| [7] | B. Chazelle, R. Rubinfeld, and L. Trevisan. Approximating the minimum spanning tree weight in sublinear time. ICALP, 2001.]] |
| [8] | G. Cormode, M. Datar, P. Indyk, and S. Muthukrishnan. Comparing data streams using hamming norms. Proceedings of the International Conference on Very Large Databases (VLDB), 2002.]] |
| [9] | G. Cormode and S. Muthukrishnan. Improved data stream summaries: The count-min sketch and its applications. DIMACS Tech Report, 2003.]] |
| [10] | A. Czumaj and C. Sohler. Estimating the weight of metric minimum spanning trees in sublinear-time. Proceedings of the Symposium on Theory of Computing, 2004.]] 10.1145/1007352.1007386 · Zbl 1192.68888 |
| [11] | P. Flajolet and G. Martin. Probabilistic counting algorithms for data base applications. Journal of Computer and System Sciences, 31:182-209, 1985.]] 10.1016/0022-0000(85)90041-8 · Zbl 0583.68059 |
| [12] | G. Frahling and C. Sohler. Estimating the weight of euclidean minimum spanning trees in data streams. Manuscript, 2004.]] |
| [13] | A. Gilbert, S. Guha, Y. Kotidis, P. Indyk, M. Muthukrishnan, and M. Strauss. Fast, small-space algorithms for approximate histogram maintenance. Proceedings of the Symposium on Theory of Computing, 2002.]] 10.1145/509907.509966 · Zbl 1192.68962 |
| [14] | S. Guha, N. Mishra, R. Motwani, and L. O’Callaghan. Clustering data streams. Proceedings of the Symposium on Theory of Computing, 2001.]] |
| [15] | S. Har-Peled and S. Mazumdar. Coresets for k-means and k-medians and their applications. Proceedings of the Symposium on Theory of Computing, 2004.]] 10.1145/1007352.1007400 |
| [16] | J. M. Hellerstein, S. Madden, and W. Hong. The sensor spectrum: technology, trends and requirements. SIGMOD Record, December, 2003.]] 10.1145/959060.959065 |
| [17] | M. Hoffman, S. Muthukrishnan, and R. Raman. Location streams: Models and algorithms. manuscript, 2004.]] |
| [18] | P. Indyk. Stable distributions, pseudorandom generators, embeddings and data stream computation. Proceedings of the Symposium on Foundations of Computer Science, 2000.]] |
| [19] | P. Indyk and N. Thaper. Fast color image retrieval via embeddings. Workshop on Statistical and Computational Theories of Vision (at ICCV), 2003.]] |
| [20] | E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. Proceedings of the Thirtieth ACM Symposium on Theory of Computing, pages 614-623, 1998.]] 10.1145/276698.276877 · Zbl 1029.68542 |
| [21] | Adam Meyerson. Online facility location. Proceedings of the Symposium on Foundations of Computer Science, pages 426-431, 2001.]] |
| [22] | K. Munagala. Personal communication. 2003.]] |
| [23] | J. I. Munro and M. S. Paterson. Selection and sorting with limited storage. TCS, 12, 1980.]] · Zbl 0441.68067 |
| [24] | S. Muthukrishnan. Data streams: Algorithms and applications (invited talk at soda’03). Available at http://athos.rutgers.edu/muthu/stream-1-1. ps, 2003.]] |
| [25] | L. A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385-393, 1982.]] · Zbl 0508.68021 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
