Spatial Join Selectivity Using Power Laws Christos Faloutsos, Bernhard Seeger, Agma J. M. Traina, and Caetano Traina Jr.   View Paper (PDF)   Return to Research Sessions 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 Note: References link to DBLP on the Web. [APR+98] Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter : Scalable Sweeping-Based Spatial Join. VLDB 1998 : 570-581 [BF95] Alberto Belussi , Christos Faloutsos : Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension. VLDB 1995 : 299-310 [BKS93] Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger : Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993 : 237-246 [BSW99] Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer : The Bulk Index Join: A Generic Approach to Processing Non-Equijoins. ICDE 1999 : 257 [CEN89] ... [CHR84] Stavros Christodoulakis : Implications of Certain Assumptions in Database Performance Evaluation. TODS 9(2) : 163-186(1984) [CMN99] Surajit Chaudhuri , Rajeev Motwani , Vivek R. Narasayya : On Random Sampling over Joins. SIGMOD Conference 1999 : 263-274 [DNS91] David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider : An Evaluation of Non-Equijoin Algorithms. VLDB 1991 : 443-452 [FJS97] ... [FK94] Christos Faloutsos , Ibrahim Kamel : Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension. PODS 1994 : 4-13 [FRM94] Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos : Fast Subsequence Matching in Time-Series Databases. SIGMOD Conference 1994 : 419-429 [GÜN93] Oliver Günther : Efficient Computation of Spatial Joins. ICDE 1993 : 50-59 [GÜT94] Ralf Hartmut Güting : An Introduction to Spatial Database Systems. VLDB Journal 3(4) : 357-399(1994) [HKMRT96] Kimmo Hätönen , Mika Klemettinen , Heikki Mannila , Pirjo Ronkainen , Hannu Toivonen : Knowledge Discovery from Telecommunication Network Alarm Databases. ICDE 1996 : 115-122 [KS97] Nick Koudas , Kenneth C. Sevcik : Size Separation Spatial Join. SIGMOD Conference 1997 : 324-335 [KS98] Nick Koudas , Kenneth C. Sevcik : High Dimensional Similarity Joins: Algorithms and Performance Evaluation. ICDE 1998 : 466-475 [KW99] Arnd Christian König , Gerhard Weikum : Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-size Estimation. VLDB 1999 : 423-434 [LR94] Ming-Ling Lo , Chinya V. Ravishankar : Spatial Joins Using Seeded Trees. SIGMOD Conference 1994 : 209-220 [MP99] Nikos Mamoulis , Dimitris Papadias : Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999 : 1-12 [MTV95] Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo : Discovering Frequent Episodes in Sequences. KDD 1995 : 210-215 [NH94] Raymond T. Ng , Jiawei Han : Efficient and Effective Clustering Methods for Spatial Data Mining. VLDB 1994 : 144-155 [ORE86] Jack A. Orenstein : Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986 : 326-336 [PD96] Jignesh M. Patel , David J. DeWitt : Partition Based Spatial-Merge Join. SIGMOD Conf. 1996 : 259-270 [POO97] Viswanath Poosala : Histogram-Based Estimation Techniques in Database Systems. Ph.D. thesis, Univ. of Wisconsin-Madison 1997 [PMT99] Dimitris Papadias , Nikos Mamoulis , Yannis Theodoridis : Processing and Optimization of Multiway Spatial Joins Using R-Trees. PODS 1999 : 44-55 [SAC+79] Patricia G. Selinger , Morton M. Astrahan , Donald D. Chamberlin , Raymond A. Lorie , Thomas G. Price : Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979 : 23-34 [SCO92] ... [SIL96] ... [SK96] Kenneth C. Sevcik , Nick Koudas : Filter Trees for Managing Spatial Data over a Range of Size Granularities. VLDB 1996 : 16-27 [SSA97] Kyuseok Shim , Ramakrishnan Srikant , Rakesh Agrawal : High-Dimensional Similarity Joins. ICDE 1997 : 301-311 [TP91] ... [TS96] Yannis Theodoridis , Timos K. Sellis : A Model for the Prediction of R-tree Performance. PODS 1996 : 161-171 [TSS98] Yannis Theodoridis , Emmanuel Stefanakis , Timos K. Sellis : Cost Models for Join Queries in Spatial Databases. ICDE 1998 : 476-483 [WKS+96] Howard D. Wactlar , Takeo Kanade , Michael A. Smith , Scott M. Stevens : Intelligent Access to Digital Video: Informedia Project. IEEE Computer 29(5) : 46-52(1996) [VW99] Jeffrey Scott Vitter , Min Wang : Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets. SIGMOD Conference 1999 : 193-204 BIBTEX @inproceedings{DBLP:conf/sigmod/FaloutsosSTT00,   author    = {Christos Faloutsos and                 Bernhard Seeger and                 Agma J. M. Traina and                 Caetano Traina Jr.},    editor    = {Weidong Chen and                 Jeffrey F. Naughton and                 Philip A. Bernstein},    title     = {Spatial Join Selectivity Using Power Laws},    booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on                 Management of Data, May 16-18, 2000, Dallas, Texas, USA},    journal   = {SIGMOD Record},    publisher = {ACM},    volume    = {29},    number    = {2},    year      = {2000},    isbn      = {1-58113-218-2},    pages     = {177-188},    crossref  = {DBLP:conf/sigmod/2000},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.