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.8805774e-05
Overall Rank
6,068 | 59.33%
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,765 Approximation Techniques for Spatial Data 2004 SIGMOD 7.0178846e-05
4,551 Power-Law Based Estimation of Set Similarity Join Size 2009 VLDB 6.5314641e-05
5,680 Skew-Aware Join Optimization for Array Databases 2015 SIGMOD 6.0233693e-05
8,346 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 5.3339321e-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.0023948467
42 Fast Subsequence Matching in Time-Series Databases 1994 SIGMOD 0.00045609336
57 On Random Sampling over Joins 1999 SIGMOD 0.0003999751
94 Efficient and Effective Clustering Methods for Spatial Data Mining 1994 VLDB 0.00034470298
102 Spatial Query Processing in an Object-Oriented Database System 1986 SIGMOD 0.00033850505
146 Efficient Processing of Spatial Joins Using R-trees 1993 SIGMOD 0.000289618
220 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00024275691
222 Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets 1999 SIGMOD 0.00024136952
760 Partition Based Spatial-Merge Join 1996 SIGMOD 0.0001419395
1,143 Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension 1994 PODS 0.00011810737
1,412 A Model for the Prediction of R-tree Performance 1996 PODS 0.00010725178
1,754 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.7111856e-05
1,930 Scalable Sweeping-Based Spatial Join 1998 VLDB 9.3453623e-05
2,368 Spatial Joins Using Seeded Trees 1994 SIGMOD 8.5495935e-05
2,838 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB 7.9401525e-05
3,131 Size Separation Spatial Join 1997 SIGMOD 7.6016052e-05
4,954 Integration of Spatial Join Algorithms for Processing Multiple Inputs 1999 SIGMOD 6.3263552e-05
5,350 Filter Trees for Managing Spatial Data Over a Range of Size Granularities 1996 VLDB 6.1545256e-05
7,924 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 5.4090777e-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,957 Spatio-Textual Similarity Joins 2013 VLDB
3 2,368 Spatial Joins Using Seeded Trees 1994 SIGMOD
4 4,551 Power-Law Based Estimation of Set Similarity Join Size 2009 VLDB
5 999 Spatial Hash-Joins 1996 SIGMOD
6 530 Multi-Step Processing of Spatial Joins 1994 SIGMOD
7 3,765 Approximation Techniques for Spatial Data 2004 SIGMOD
8 11,547 Optimal (Multiway) Spatial Joins 2024 PODS
9 2,176 Selectivity Estimation in Spatial Databases 1999 SIGMOD
10 2,838 Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension 1995 VLDB