Approximation techniques for spatial data

ABSTRACT

Spatial Database Management Systems (SDBMS), e.g., Geographical Information Systems, that manage spatial objects such as points, lines, and hyper-rectangles, often have very high query processing costs. Accurate selectivity estimation during query optimization therefore is crucially important for finding good query plans, especially when spatial joins are involved. Selectivity estimation has been studied for relational database systems, but to date has only received little attention in SDBMS. In this paper, we introduce novel methods that permit high-quality selectivity estimation for spatial joins and range queries. Our techniques can be constructed in a single scan over the input, handle inserts and deletes to the database incrementally, and hence they can also be used for processing of streaming spatial data. In contrast to previous approaches, our techniques return approximate results that come with provable probabilistic quality guarantees. We present a detailed analysis and experimentally demonstrate the efficacy of the proposed techniques.

REFERENCES

• 1: Accurate Estimation of the Cost of Spatial Selections, Proceedings of the 16th International Conference on Data Engineering, p.123, February 28-March 03, 2000
• 2: Swarup Acharya , Viswanath Poosala , Sridhar Ramaswamy, Selectivity estimation in spatial databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.13-24, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: Noga Alon , Phillip B. Gibbons , Yossi Matias , Mario Szegedy, Tracking join and self-join sizes in limited storage, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.10-20, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303978]
• 4: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 5: Ning An , Zhen-Yu Yang , Anand Sivasubramaniam, Selectivity Estimation for Spatial Joins, Proceedings of the 17th International Conference on Data Engineering, p.368-375, April 02-06, 2001
• 6: 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]
• 7: Ziv Bar-Yosseff , Ravi Kumar , D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 06-08, 2002, San Francisco, California
• 8: Alberto Belussi , Christos Faloutsos, Self-spacial join selectivity estimation using fractal concepts, ACM Transactions on Information Systems (TOIS), v.16 n.2, p.161-201, April 1998 [doi>10.1145/279339.279342]
• 9: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Parallel Processing of Spatial Joins Using R-trees, Proceedings of the Twelfth International Conference on Data Engineering, p.258-265, February 26-March 01, 1996
• 10: Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding Frequent Items in Data Streams, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.693-703, July 08-13, 2002
• 11: Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.296-306, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773182]
• 12: G. Cormode and S. Muthukrishnan. An improved data stream summary: The count-min sketch and its applications. In LATIN, pages 29--38, 2004.
• 13: A. Das, J. Gehrke, and M. Riedewald. Approximation techniques for spatial data. Technical report, Cornell University, 2004. http://techreports.library.cornell.edu.
• 14: Alin Dobra , Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Processing complex aggregate queries over data streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564699]
• 15: Christos Faloutsos , Bernhard Seeger , Agma Traina , Caetano Traina, Jr., Spatial join selectivity using power laws, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.177-188, May 15-18, 2000, Dallas, Texas, United States
• 16: S. Ganguly, M. N. Garofalakis, and R. Rastogi. Processing data-stream join aggregates using skimmed sketches. In Proc. EDBT, pages 569--586, 2004.
• 17: A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss. How to summarize the universe: Dynamic maintenance of quantiles. In Proc. VLDB, pages 454--465, 2002.
• 18: Peter J. Haas , Joseph M. Hellerstein, Online query processing: a tutorial, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.623, May 21-24, 2001, Santa Barbara, California, United States
• 19: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 20: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, A Cost Model for Estimating the Performance of Spatial Joins Using R-trees, Proceedings of the Ninth International Conference on Scientific and Statistical Database Management, p.30-38, August 11-13, 1997 [doi>10.1109/SSDM.1997.621148]
• 21: Analyzing Range Queries on Spatial Data, Proceedings of the 16th International Conference on Data Engineering, p.525, February 28-March 03, 2000
• 22: Hans-Peter Kriegel , Martin Pfeifle , Marco Pötke , Thomas Seidl, A Cost Model for Interval Intersection Queries on RI-Trees, Proceedings of the 14th International Conference on Scientific and Statistical Database Management, p.131-141, July 24-26, 2002 [doi>10.1109/SSDM.2002.1029713]
• 23: Nikos Mamoulis , Dimitris Papadias, Selectivity Estimation of Complex Spatial Queries, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.155-174, July 12-15, 2001
• 24: Dimitris Papadias , Timos Sellis , Yannis Theodoridis , Max J. Egenhofer, Topological relations in the world of minimum bounding rectangles: a study with R-trees, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.92-103, May 22-25, 1995, San Jose, California, United States
• 25: Exploring Spatial Datasets with Histograms, Proceedings of the 18th International Conference on Data Engineering, p.93, February 26-March 01, 2002
• 26: Chengyu Sun , Divyakant Agrawal , Amr El Abbadi, Selectivity Estimation for Spatial Joins with Geometric Selections, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.609-626, March 25-27, 2002
• 27: Yufei Tao , George Kollios , Jeffrey Considine , Feifei Li , Dimitris Papadias, Spatio-Temporal Aggregation Using Sketches, Proceedings of the 20th International Conference on Data Engineering, p.214, March 30-April 02, 2004
• 28: Nitin Thaper , Sudipto Guha , Piotr Indyk , Nick Koudas, Dynamic multidimensional histograms, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564741]
• 29: Yannis Theodoridis , Timos Sellis, A model for the prediction of R-tree performance, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-171, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237705]
• 30: Yannis Theodoridis , Emmanuel Stefanakis , Timos Sellis, Efficient Cost Models for Spatial Queries Using R-Trees, IEEE Transactions on Knowledge and Data Engineering, v.12 n.1, p.19-32, January 2000 [doi>10.1109/69.842247]