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
3245
Venue
SIGMOD
Year
2000
Pagerank
6.0369275e-05
Overall Rank
5,932 | 59.31%
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,703 Approximation Techniques for Spatial Data 2004 SIGMOD 7.1829776e-05
4,450 Power-Law Based Estimation of Set Similarity Join Size 2009 VLDB 6.6972929e-05
5,534 Skew-Aware Join Optimization for Array Databases 2015 SIGMOD 6.1831004e-05
8,155 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 5.4766319e-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.0024089429
41 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00046675394
54 On Random Sampling over Joins 1999 SIGMOD 0.00040810225
88 Efficient and Effective Clustering Methods for Spatial Data Mining 1994 VLDB 0.00035240327
96 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00034590762
145 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.00029548428
210 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00024797689
213 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024723025
728 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014542772
1,129 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00012061727
1,373 A Model for the Prediction of R-tree Performance 1996 PODS 0.0001098638
1,729 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.908788e-05
1,880 Scalable Sweeping-Based Spatial Join 1998 VLDB 9.5562066e-05
2,310 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.7650894e-05
2,774 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 8.1372328e-05
3,066 Size Separation Spatial Join 1997 SIGMOD 7.7941163e-05
4,815 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.4949956e-05
5,202 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.3194496e-05
7,744 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 5.5541724e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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