Adaptive sampling for geometric problems over data streams

ABSTRACT

Geometric coordinates are an integral part of many data streams. Examples include sensor locations in environmental monitoring, vehicle locations in traffic monitoring or battlefield simulations, scientific measurements of earth or atmospheric phenomena, etc. How can one summarize such data streams using limited storage so that many natural geometric queries can be answered faithfully? Some examples of such queries are: report the smallest convex region in which a chemical leak has been sensed, or track the diameter of the dataset. One can also pose queries over multiple streams: track the minimum distance between the convex hulls of two data streams; or report when datasets A and B are no longer linearly separable.In this paper, we propose an adaptive sampling scheme that gives provably optimal error bounds for extremal problems of this nature. All our results follow from a single technique for computing the approximate convex hull of a point stream in a single pass. Our main result is this: given a stream of two-dimensional points and an integer r, we can maintain an adaptive sample of at most 2r + 1 points such that the distance between the true convex hull and the convex hull of the sample points is O(D/r²), where D is the diameter of the sample set. With our sample convex hull, all the queries mentioned above can be answered in either O(log r) or O(r) time.

REFERENCES

• 1: Pankaj K. Agarwal , Sariel Har-Peled , Kasturi R. Varadarajan, Approximating extent measures of points, Journal of the ACM (JACM), v.51 n.4, p.606-635, July 2004 [doi>10.1145/1008731.1008736]
• 2: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 3: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 4: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 5: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 6: G. Cormode and S. Muthukrishnan. Radial histogram for spatial streams. Technical Report 2003--11, DIMACS, 2003.
• 7: R. M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. J. Approx. Theory, 10:227--236, 1974.
• 8: http://www.earthscope.org.
• 9: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, An Approximate L1-Difference Algorithm for Massive Data Streams, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.501, October 17-18, 1999
• 10: J. Feigenbaum, S. Kannan, and J. Zhang. Computing diameter in the streaming and sliding-window models, 2002. Manuscript.
• 11: J. Gray, A. Szalay, A. Thakar, P. Z. Zunszt, T. Malik, J. Raddick, C. Stoughton, and J. vandenBerg. The SDSS SkyServer: Public access to the Sloan digital sky server data. Technical Report MSR-TR-2001-104, Microsoft Research, 2001.
• 12: Michael Greenwald , Sanjeev Khanna, Space-efficient online computation of quantile summaries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.58-66, May 21-24, 2001, Santa Barbara, California, United States
• 13: P. M. Gruber. Approximation of convex bodies. In P. M. Gruber and J. M. Wills, editors, Convexity and its Applications, pages 131--162. Birkhäuser, Basel, Switzerland, 1983.
• 14: P. Indyk. Stream-based geometric algorithms. In Proc. ACM/DIMACS Workshop on Management and Processing of Data Streams, 2003.
• 15: Nicolai M. Josuttis, The C++ standard library: a tutorial and reference, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 16: P. S. Kenderov. Polygonal approximation of plane convex compacts. J. Approx. Theory, 38:221--239, 1983.
• 17: Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Random sampling techniques for space efficient online computation of order statistics of large datasets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.251-262, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 18: D. E. McClure and R. A. Vitale. Polygonal approximation of plane convex bodies. J. Math. Anal. Appl., 51:326--358, 1975.
• 19: S. Muthukrishnan. Data streams: Algorithms and applications. Technical report, Computer Science Department, Rutgers University, 2003.
• 20: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 21: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 22: T. J. Richardson. Approximation of planar convex sets from hyperplane probes. Discrete Comput. Geom., 18(2):151--177, 1997.