Spatial join selectivity using power laws

ABSTRACT

We discovered a surprising law governing the spatial join selectivity across two sets of points. An example of such a spatial join is “find the libraries that are within 10 miles of schools”. Our law dictates that the number of such qualifying pairs follows a power law, whose exponent we call “pair-count exponent” (PC). We show that this law also holds for self-spatial-joins (“find schools within 5 miles of other schools”) in addition to the general case that the two point-sets are distinct. Our law holds for many real datasets, including diverse environments (geographic datasets, feature vectors from biology data, galaxy data from astronomy).

In addition, we introduce the concept of the Box-Occupancy-Product-Sum (BOPS) plot, and we show that it can compute the pair-count exponent in a timely manner, reducing the run time by orders of magnitude, from quadratic to linear. Due to the pair-count exponent and our analysis (Law 1), we can achieve accurate selectivity estimates in constant time (O(1)) without the need for sampling or other expensive operations. The relative error in selectivity is about 30% with our fast BOPS method, and even better (about 10%), if we use the slower, quadratic method.

REFERENCES

• APR+98: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Scalable Sweeping-Based Spatial Join, Proceedings of the 24rd International Conference on Very Large Data Bases, p.570-581, August 24-27, 1998
• BF 95: 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
• BKS 93: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• BSW 99: The Bulk Index Join: A Generic Approach to Processing Non-Equijoins, Proceedings of the 15th International Conference on Data Engineering, p.257, March 23-26, 1999
• CEN 89: Bureau of the Census - Tiger#Line Precensus Files: 1990 technical documentation. Bureau of the Census. Washington, D.C. 1989.
• CHR 84: S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984 [doi>10.1145/329.318578]
• CMN 99: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• DNS 91: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider, An Evaluation of Non-Equijoin Algorithms, Proceedings of the 17th International Conference on Very Large Data Bases, p.443-452, September 03-06, 1991
• FJS97: C. Faloutsos, H.V. Jagadish and N. Sidiropoulos - "Information Recovery from Partial data". Tech. Report ISR-TR-97-7, Inst. For Systems Research, Univ. of Maryland, College Park, MD, 1997.
• FK 94: Christos Faloutsos , Ibrahim Kamel, Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.4-13, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182593]
• FRM 94: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• GÜN93: Oliver Günther, Efficient Computation of Spatial Joins, Proceedings of the Ninth International Conference on Data Engineering, p.50-59, April 19-23, 1993
• GÜT 94: Ralf Hartmut Güting, An introduction to spatial database systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• HKMRT 96: Kimmo Hätönen , Mika Klemettinen , Heikki Mannila , Pirjo Ronkainen , Hannu Toivonen, Knowledge Discovery from Telecommunication Network Alarm Databases, Proceedings of the Twelfth International Conference on Data Engineering, p.115-122, February 26-March 01, 1996
• KS 97: Nick Koudas , Kenneth C. Sevcik, Size separation spatial join, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.324-335, May 11-15, 1997, Tucson, Arizona, United States
• KS 98: Nick Koudas , Kenneth C. Sevcik, High Dimensional Similarity Joins: Algorithms and Performance Evaluation, Proceedings of the Fourteenth International Conference on Data Engineering, p.466-475, February 23-27, 1998
• KW 99: Arnd Christian König , Gerhard Weikum, Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-size Estimation, Proceedings of the 25th International Conference on Very Large Data Bases, p.423-434, September 07-10, 1999
• LR 94: Ming-Ling Lo , Chinya V. Ravishankar, Spatial joins using seeded trees, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.209-220, May 24-27, 1994, Minneapolis, Minnesota, United States
• MP 99: Nikos Mamoulis , Dimitris Papadias, Integration of spatial join algorithms for processing multiple inputs, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.1-12, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• MTV 95: H. Mannila, H. Toivonen, A. I. Verkamo - "Discovering Frequent Episodes in Sequences". KDD 1995, pp.210-215.
• NH 94: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• ORE 86: Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States
• PD 96: Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada
• POO 97: Viswanath Poosala, Histogram-based estimation techniques in database systems, University of Wisconsin at Madison, Madison, WI, 1997
• PMT 99: Dimitris Papadias , Nikos Mamoulis , Yannis Theodoridis, Processing and optimization of multiway spatial joins using R-trees, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.44-55, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303981]
• 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]
• SCO 92: D. W. Scott - Multivariate Density Estimation, Wiley & Sons 1992.
• SIL 96: B. W. Silverman - Density Estimation for Statistics and Data Analysis. Chapman & Hall 1986.
• SK 96: Kenneth C. Sevcik , Nick Koudas, Filter Trees for Managing Spatial Data over a Range of Size Granularities, Proceedings of the 22th International Conference on Very Large Data Bases, p.16-27, September 03-06, 1996
• SSA 97: Kyuseok Shim , Ramakrishnan Srikant , Rakesh Agrawal, High-Dimensional Similarity Joins, Proceedings of the Thirteenth International Conference on Data Engineering, p.301-311, April 07-11, 1997
• TP 91: M. Turk and A. Pentland- "Eigenfaces for Recognition". Journal of cognitive Neuroscience, vol 3(1), 1991, pp. 71-86.
• TS 96: 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]
• TSS 98: Yannis Theodoridis , Emmanuel Stefanakis , Timos K. Sellis, Cost Models for Join Queries in Spatial Databases, Proceedings of the Fourteenth International Conference on Data Engineering, p.476-483, February 23-27, 1998
• WKS+96: Howard D. Wactlar , Takeo Kanade , Michael A. Smith , Scott M. Stevens, Intelligent Access to Digital Video: Informedia Project, Computer, v.29 n.5, p.46-52, May 1996 [doi>10.1109/2.493456]
• VW 99: Jeffrey Scott Vitter , Min Wang, Approximate computation of multidimensional aggregates of sparse data using wavelets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.193-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Management, Theory