DBScholar

Back to papers

Spatial Join Selectivity Using Power Laws

Summary: Power-law spatial join selectivity for point sets; defines pair-count exponent (PC) for cross- and self-joins. Introduces the Box-Occupancy-Product-Sum (BOPS) plot to estimate PC in linear time and selectivity in O(1) with ~30% error (10% for the quadratic method) across diverse datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h78663aa4b64328d0
Venue
SIGMOD
Year
2000
Pagerank
5.9028248e-05
Overall Rank
6,052 | 59.32%
DOI
10.1145/342009.335412

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{faloutsos_sigmod00,
        title = {{Spatial Join Selectivity Using Power Laws}},
        author = {Faloutsos, Christos and Seeger, Bernhard and Traina, Agma and Traina, Jr., Caetano},
        series = {{SIGMOD} '00},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/342009.335412},
        url = {https://dl.acm.org/doi/10.1145/342009.335412},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank Citing Paper Year Venue Pagerank
3,758 Approximation Techniques for Spatial Data 2004 SIGMOD 7.0437238e-05
4,536 Power-Law Based Estimation of Set Similarity Join Size 2009 VLDB 6.5557137e-05
5,666 Skew-Aware Join Optimization for Array Databases 2015 SIGMOD 6.0462129e-05
8,325 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 5.3540828e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
1 Access Path Selection in a Relational Database Management System 1979 SIGMOD 0.0023947656
42 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00045773967
57 On Random Sampling over Joins 1999 SIGMOD 0.00040108301
94 Efficient and Effective Clustering Methods for Spatial Data Mining 1994 VLDB 0.00034579889
101 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00033937215
146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00029061754
220 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00024344086
222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024218831
752 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014246504
1,142 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011848523
1,405 A Model for the Prediction of R-tree Performance 1996 PODS 0.0001076417
1,741 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.7382372e-05
1,922 Scalable Sweeping-Based Spatial Join 1998 VLDB 9.3751198e-05
2,358 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.5817166e-05
2,827 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.967335e-05
3,120 Size Separation Spatial Join 1997 SIGMOD 7.6300049e-05
4,927 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.3503189e-05
5,328 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.1778312e-05
7,904 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 5.4295914e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD
2 2,944 Spatio-Textual Similarity Joins 2013 VLDB
3 2,358 Spatial Joins Using Seeded Trees 1994 SIGMOD
4 4,536 Power-Law Based Estimation of Set Similarity Join Size 2009 VLDB
5 994 Spatial Hash-Joins 1996 SIGMOD
6 527 Multi-Step Processing of Spatial Joins 1994 SIGMOD
7 3,758 Approximation Techniques for Spatial Data 2004 SIGMOD
8 11,489 Optimal (Multiway) Spatial Joins 2024 PODS
9 2,162 Selectivity Estimation in Spatial Databases 1999 SIGMOD
10 2,827 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB