{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,4]],"date-time":"2025-10-04T14:39:44Z","timestamp":1759588784863,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T00:00:00Z","timestamp":1177977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,5]]},"abstract":"<jats:p>We present memory-efficient deterministic algorithms for constructing \u03f5-nets and \u03f5-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide guaranteed bounds on their approximation factors. We show how our deterministic samples can be used to answer approximate online iceberg geometric queries on data streams. We use these techniques to approximate several robust statistics of geometric data streams, including Tukey depth, simplicial depth, regression depth, the Thiel-Sen estimator, and the least median of squares. Our algorithms use only a polylogarithmic amount of memory, provided the desired approximation factors are at least inverse-polylogarithmic. We also include a lower bound for noniceberg geometric queries.<\/jats:p>","DOI":"10.1145\/1240233.1240239","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:11Z","timestamp":1181140631000},"page":"16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Deterministic sampling and range counting in geometric data streams"],"prefix":"10.1145","volume":"3","author":[{"given":"Amitabha","family":"Bagchi","sequence":"first","affiliation":[{"name":"Indian Institute of Technology, Hauz Khas, New Delhi, India"}]},{"given":"Amitabh","family":"Chaudhary","sequence":"additional","affiliation":[{"name":"Notre Dame University, Notre Dame, IN"}]},{"given":"David","family":"Eppstein","sequence":"additional","affiliation":[{"name":"University of California at Irvine, Irvine, CA"}]},{"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[{"name":"University of California at Irvine, Irvine, CA"}]}],"member":"320","published-online":{"date-parts":[[2007,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Agarwal P. K. Har-Peled S. and Varadarajan K. R. 2005. Geometric approximation via coresets. http:\/\/valis.cs.uiuc.edu\/sariel\/research\/papers\/.  Agarwal P. K. Har-Peled S. and Varadarajan K. R. 2005. Geometric approximation via coresets. http:\/\/valis.cs.uiuc.edu\/sariel\/research\/papers\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008736"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009502"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997842"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90015-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-001-0092-1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00025-4"},{"key":"e_1_2_1_9_1","unstructured":"Br\u00f6nnimann H. Chen B. Dash M. Haas P. Qiao Y. and Scheuerman P. 2003a. Efficient data-reduction methods for on-line association rule discovery. In Data Mining: Next Generation Challenges and Future Directions Selected papers from the NSF Workshop on Next-Generation Data Mining (NGDM '02). MIT Press Cambridges MA. 190--208.  Br\u00f6nnimann H. Chen B. Dash M. Haas P. Qiao Y. and Scheuerman P. 2003a. Efficient data-reduction methods for on-line association rule discovery. In Data Mining: Next Generation Challenges and Future Directions Selected papers from the NSF Workshop on Next-Generation Data Mining (NGDM '02). MIT Press Cambridges MA. 190--208."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956761"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780620"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187743"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1142\/S021819599600023X"},{"key":"e_1_2_1_14_1","volume-title":"Tech. Rep. 2003-11, DIMACS.","author":"Cormode G.","year":"2003","unstructured":"Cormode , G. , and Muthukrishnan , S . 2003 . Radial histograms for spatial streams. Tech. Rep. 2003-11, DIMACS. Cormode, G., and Muthukrishnan, S. 2003. Radial histograms for spatial streams. Tech. Rep. 2003-11, DIMACS."},{"volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 635--644","author":"Datar M.","key":"e_1_2_1_15_1","unstructured":"Datar , M. , Gionis , A. , Indyk , P. , and Motwani , R . 2002. Maintaining stream statistics over sliding windows . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 635--644 . Datar, M., Gionis, A., Indyk, P., and Motwani, R. 2002. Maintaining stream statistics over sliding windows. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 635--644."},{"volume-title":"Proceedings of the 10th Annual European Symposium on Algorithms (ESA). 348--360","author":"Demaine E. D.","key":"e_1_2_1_16_1","unstructured":"Demaine , E. D. , L\u00f3pez-Ortiz , A. , and Munro , J. I . 2002. Frequency estimation of Internet packet streams with limited space . In Proceedings of the 10th Annual European Symposium on Algorithms (ESA). 348--360 . Demaine, E. D., L\u00f3pez-Ortiz, A., and Munro, J. I. 2002. Frequency estimation of Internet packet streams with limited space. In Proceedings of the 10th Annual European Symposium on Algorithms (ESA). 348--360."},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases. 299--310","author":"Fang M.","key":"e_1_2_1_18_1","unstructured":"Fang , M. , Shivakumar , N. , Garcia-Molina , H. , Motwani , R. , and Ullman , J. D . 1998. Computing iceberg queries efficiently . In Proceedings of the International Conference on Very Large Data Bases. 299--310 . Fang, M., Shivakumar, N., Garcia-Molina, H., Motwani, R., and Ullman, J. D. 1998. Computing iceberg queries efficiently. In Proceedings of the International Conference on Very Large Data Bases. 299--310."},{"key":"e_1_2_1_19_1","volume-title":"Tech. Rep. YALEU\/DCS\/TR-1245","author":"Feigenbaum J.","year":"2002","unstructured":"Feigenbaum , J. , Kannan , S. , and Zhang , J . 2002 . Computing diameter in the streaming and sliding-window models. Tech. Rep. YALEU\/DCS\/TR-1245 , Yale University . Feigenbaum, J., Kannan, S., and Zhang, J. 2002. Computing diameter in the streaming and sliding-window models. Tech. Rep. YALEU\/DCS\/TR-1245, Yale University."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009325"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796588"},{"volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 253--254","author":"Gupta A.","key":"e_1_2_1_23_1","unstructured":"Gupta , A. , and Zane , F. X . 2003. Counting inversions in lists . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 253--254 . Gupta, A., and Zane, F. X. 2003. Counting inversions in lists. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 253--254."},{"volume-title":"Proceedings of the 11th Annual European Symposium on Algorithms. Lecture Notes in Computer Science. Springer Verlag","author":"Har-Peled S.","key":"e_1_2_1_24_1","unstructured":"Har-Peled , S. , and Mazumdar , S . 2003. Fast algorithms for computing the smallest k-enclosing disc . In Proceedings of the 11th Annual European Symposium on Algorithms. Lecture Notes in Computer Science. Springer Verlag , Berlin. Har-Peled, S., and Mazumdar, S. 2003. Fast algorithms for computing the smallest k-enclosing disc. In Proceedings of the 11th Annual European Symposium on Algorithms. Lecture Notes in Computer Science. Springer Verlag, Berlin."},{"volume-title":"Proceedings of the ACM\/DIMACS Workshop on Management and Processing of Data Streams. http:\/\/www.research.att.com\/conf\/mpds2003\/.","author":"Hershberger J.","key":"e_1_2_1_25_1","unstructured":"Hershberger , J. , and Suri , S . 2003. Convex hulls and related problems in data streams . In Proceedings of the ACM\/DIMACS Workshop on Management and Processing of Data Streams. http:\/\/www.research.att.com\/conf\/mpds2003\/. Hershberger, J., and Suri, S. 2003. Convex hulls and related problems in data streams. In Proceedings of the ACM\/DIMACS Workshop on Management and Processing of Data Streams. http:\/\/www.research.att.com\/conf\/mpds2003\/."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 539--545","author":"Indyk P.","year":"2003","unstructured":"Indyk , P. 2003 a. Better algorithms for high-dimensional proximity problems via asymmetric embeddings . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 539--545 . Indyk, P. 2003a. Better algorithms for high-dimensional proximity problems via asymmetric embeddings. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 539--545."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the ACM\/DIMACS Workshop on Management and Processing of Data Streams. http:\/\/www.research.att.com\/conf\/mpds2003\/.","author":"Indyk P.","year":"2003","unstructured":"Indyk , P. 2003 b. Stream-Based geometric algorithms . In Proceedings of the ACM\/DIMACS Workshop on Management and Processing of Data Streams. http:\/\/www.research.att.com\/conf\/mpds2003\/. Indyk, P. 2003b. Stream-Based geometric algorithms. In Proceedings of the ACM\/DIMACS Workshop on Management and Processing of Data Streams. http:\/\/www.research.att.com\/conf\/mpds2003\/."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/160985.161003"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases. 814--825","author":"Korn F.","key":"e_1_2_1_30_1","unstructured":"Korn , F. , Muthukrishnan , S. , and Srivastava , D . 2002. Reverse nearest neighbour aggregates over data streams . In Proceedings of the International Conference on Very Large Data Bases. 814--825 . Korn, F., Muthukrishnan, S., and Srivastava, D. 2002. Reverse nearest neighbour aggregates over data streams. In Proceedings of the International Conference on Very Large Data Bases. 814--825."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 20th International Symposium Theoretical Aspects of Computer Science, H. Alt and M. Habib, Eds. Lecture Notes in Computer Science","volume":"2607","author":"Langerman S.","unstructured":"Langerman , S. , and Steiger , W . 2003. Optimization in arrangements . In Proceedings of the 20th International Symposium Theoretical Aspects of Computer Science, H. Alt and M. Habib, Eds. Lecture Notes in Computer Science , vol. 2607 . Springer Verlag, Berlin. 50--61. Langerman, S., and Steiger, W. 2003. Optimization in arrangements. In Proceedings of the 20th International Symposium Theoretical Aspects of Computer Science, H. Alt and M. Habib, Eds. Lecture Notes in Computer Science, vol. 2607. Springer Verlag, Berlin. 50--61."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176347507"},{"volume-title":"Proceedings of the International Conference on Very Large Data Bases. 346--357","author":"Manku G. S.","key":"e_1_2_1_33_1","unstructured":"Manku , G. S. , and Motwani , R . 2002. Approximate frequency counts over data streams . In Proceedings of the International Conference on Very Large Data Bases. 346--357 . Manku, G. S., and Motwani, R. 2002. Approximate frequency counts over data streams. In Proceedings of the International Conference on Very Large Data Bases. 346--357."},{"volume-title":"Discrete and Computational Geometry: Papers from the DIMACS Special Year, J. E. Goodman et al., eds. Number 6 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"Matou\u0161ek J.","key":"e_1_2_1_34_1","unstructured":"Matou\u0161ek , J. 1991. Computing the center of planar point sets . In Discrete and Computational Geometry: Papers from the DIMACS Special Year, J. E. Goodman et al., eds. Number 6 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science . American Mathematical Society , Boston, MA . 221--230. Matou\u0161ek, J. 1991. Computing the center of planar point sets. In Discrete and Computational Geometry: Papers from the DIMACS Special Year, J. E. Goodman et al., eds. Number 6 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, Boston, MA. 221--230."},{"volume-title":"New Trends in Discrete and Computational Geometry","author":"Matou\u0161ek J.","key":"e_1_2_1_35_1","unstructured":"Matou\u0161ek , J. 1993. Epsilon-Nets and computational geometry . In New Trends in Discrete and Computational Geometry , J. Pach, ed. Algorithms and Combinatorics, vol. 10 . Springer Verlag , Heidelberg. 69--89. Matou\u0161ek, J. 1993. Epsilon-Nets and computational geometry. In New Trends in Discrete and Computational Geometry, J. Pach, ed. Algorithms and Combinatorics, vol. 10. Springer Verlag, Heidelberg. 69--89."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1018"},{"volume-title":"Handbook of Computational Geometry, J.-R","author":"Matou\u0161ek J.","key":"e_1_2_1_37_1","unstructured":"Matou\u0161ek , J. 2000. Derandomization in computational geometry . In Handbook of Computational Geometry, J.-R . Sack and J. Urrutia, eds. Elsevier Science, North Holland , Amsterdam . 559--595. Matou\u0161ek, J. 2000. Derandomization in computational geometry. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds. Elsevier Science, North Holland, Amsterdam. 559--595."},{"key":"e_1_2_1_38_1","volume-title":"Data streams: Algorithms and applications. Invited talk at (Symposium on Discrete Algorithms) (SODA)","author":"Muthukrishnan S.","year":"2003","unstructured":"Muthukrishnan , S. 2003. Data streams: Algorithms and applications. Invited talk at (Symposium on Discrete Algorithms) (SODA) 2003 . Available on request by email to muthu@research.att.com. Muthukrishnan, S. 2003. Data streams: Algorithms and applications. Invited talk at (Symposium on Discrete Algorithms) (SODA) 2003. Available on request by email to muthu@research.att.com."},{"key":"e_1_2_1_39_1","article-title":"Regression depth","volume":"94","author":"Rousseeuw P. J.","year":"1999","unstructured":"Rousseeuw , P. J. , and Hubert , M. 1999 . Regression depth . J. Amer. Statis. Assoc. 94 , 446, 388--402. Rousseeuw, P. J., and Hubert, M. 1999. Regression depth. J. Amer. Statis. Assoc. 94, 446, 388--402.","journal-title":"J. Amer. Statis. Assoc."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Rousseeuw P. J. and Leroy A. M. 1987. Robust Regression and Outlier Detection. John Wiley New York.   Rousseeuw P. J. and Leroy A. M. 1987. Robust Regression and Outlier Detection. John Wiley New York.","DOI":"10.1002\/0471725382"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008945009397"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1968.10480934"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997844"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the Koninalijke Nederlandse Akademie van Weinenschatpen A 53","author":"Thiel H.","year":"1950","unstructured":"Thiel , H. 1950 . A rank-invariant method of linear and polynomial regression analysis, Part 3 . Proceedings of the Koninalijke Nederlandse Akademie van Weinenschatpen A 53 , 1397--1412. Thiel, H. 1950. A rank-invariant method of linear and polynomial regression analysis, Part 3. Proceedings of the Koninalijke Nederlandse Akademie van Weinenschatpen A 53, 1397--1412."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1116025"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240239","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1240233.1240239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:08Z","timestamp":1750258328000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1240233.1240239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["10.1145\/1240233.1240239"],"URL":"https:\/\/doi.org\/10.1145\/1240233.1240239","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2007,5]]},"assertion":[{"value":"2007-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}