Selectivity estimation in spatial databases

ABSTRACT

Selectivity estimation of queries is an important and well-studied problem in relational database systems. In this paper, we examine selectivity estimation in the context of Geographic Information Systems, which manage spatial data such as points, lines, poly-lines and polygons. In particular, we focus on point and range queries over two-dimensional rectangular data. We propose several techniques based on using spatial indices, histograms, binary space partitionings (BSPs), and the novel notion of spatial skew. Our techniques carefully partition the input rectangles into subsets and approximate each partition accurately. We present a detailed experimental study comparing the proposed techniques and the best known sampling and parametric techniques. We evaluate them using synthetic as well as real-life TIGER datasets. Based on our experiments, we identify a BSP based partitioning that we call Min-Skew which consistently provides the most accurate selectivity estimates for spatial queries. The Min-Skew partitioning can be constructed efficiently, occupies very little space, and provides accurate selectivity estimates over a broad range of spatial queries.

REFERENCES

• Ant92: Gennady Antoshenkov, Random Sampling from Pseudo-Ranked B+ Trees, Proceedings of the 18th International Conference on Very Large Data Bases, p.375-382, August 23-27, 1992
• Aok97: Paul M. Aoki, Generalizing "Search" in Generalized Search Trees, University of California at Berkeley, Berkeley, CA, 1997
• APR99: 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
• ARC93: ARC/INFO. Understanding GIS--the ARCflNFO method. ARC/INFO, 1993. Rev. 6 for workstations.
• BF95: Alberto Belussi , Christos Faloutsos, Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension, Proceedings of the 21th International Conference on Very Large Data Bases, p.299-310, September 11-15, 1995
• BKSS90: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• CR94: Chungmin Melvin Chen , Nick Roussopoulos, Adaptive selectivity estimation using query feedback, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.161-172, May 24-27, 1994, Minneapolis, Minnesota, United States
• DeW94: David J. DeWitt , Navin Kabra , Jun Luo , Jignesh M. Patel , Jie-Bing Yu, Client-Server Paradise, Proceedings of the 20th International Conference on Very Large Data Bases, p.558-569, September 12-15, 1994
• GG82: Erol Gelenbe , Danièle Gardy, The Size of Projections of Relations Satisfying a Functional Dependency, Proceedings of the 8th International Conference on Very Large Data Bases, p.325-333, September 08-10, 1982
• GRSS97: Stéphane Grumbach , Philippe Rigaux , Michel Scholl , Luc Segoufin, DEDALE, A Spatial Constraint Database, Proceedings of the 6th International Workshop on Database Programming Languages, p.38-59, August 18-20, 1997
• Gut85: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• HNSS95: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Lynne Stokes, Sampling-Based Estimation of the Number of Distinct Values of an Attribute, Proceedings of the 21th International Conference on Very Large Data Bases, p.311-322, September 11-15, 1995
• Int97: Intergraph Corp. MGE Z O, "hap://www.intergraph.com/iss/products/mge/mge- 7.0.htm", 1997.
• KMS97: Sanjeev Khanna , S. Muthukrishnan , Steven Skiena, Efficient Array Partitioning, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.616-626, July 07-11, 1997
• Koo80: Robert Philip Kooi, The optimization of queries in relational databases, 1980
• LNS90: Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States
• Map98: Maplnfo Corp. The Maplnfo Story, "hap://www.mapinfo.com/mapinfo/mapinfostory.htmr', 1998.
• MPS99: S. Muthukrishnan , Viswanath Poosala , Torsten Suel, On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications, Proceeding of the 7th International Conference on Database Theory, p.236-256, January 10-12, 1999
• PI97: Viswanath Poosala , Yannis E. Ioannidis, Selectivity Estimation Without the Attribute Value Independence Assumption, Proceedings of the 23rd International Conference on Very Large Data Bases, p.486-495, August 25-29, 1997
• PIHS96: Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.294-305, June 04-06, 1996, Montreal, Quebec, Canada
• Poo97: Viswanath Poosala, Histogram-based estimation techniques in database systems, University of Wisconsin at Madison, Madison, WI, 1997
• PSC84: Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• SAC+79: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• Sam89a: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• Sam89b: H. Street. The Design and Analyses of Spatial Data Structures. Addison Wesley, MA, 1989.
• SFGM93: Michael Stonebraker , Jim Frew , Kenn Gardels , Jeff Meredith, The SEQUOIA 2000 storage benchmark, ACM SIGMOD Record, v.22 n.2, p.2-11, June 1, 1993
• SRF87: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• tig92: Tiger/line files (tm), 1992 technical documentation. Technical report, U. S. Bureau of the Census, 1992.
• TS96: 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]
• Ube94: Michael Ubell, The Montage extensible DataBlade architecture, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.482, May 24-27, 1994, Minneapolis, Minnesota, United States
• Zip49: G.K. Zipf. Human behaviour and the principle of least effort. Addison-Wesley, Reading, MA, 1949.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance, Theory