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: 3183
Venue: SIGMOD
Year: 2000
Pagerank: 5.1753664e-05
Overall Rank: 6,161 | 57.14%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,543	Approximation Techniques for Spatial Data	2004	SIGMOD	6.9917053e-05
4,873	Power-Law Based Estimation of Set Similarity Join Size	2009	VLDB	5.8602304e-05
5,960	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD	5.2559595e-05
7,827	Containment Join Size Estimation: Models and Methods	2003	SIGMOD	4.6411831e-05

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.0040449103
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
27	Efficient and Effective Clustering Methods for Spatial Data Mining	1994	VLDB	0.00080736878
65	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00062029383
76	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057303551
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766
152	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00040963225
273	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029390945
925	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015264328
1,114	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.00013901031
1,528	A Model for the Prediction of R-tree Performance	1996	PODS	0.00011497734
1,695	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	0.00010882793
2,094	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5547223e-05
2,672	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.3363695e-05
2,974	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	7.789769e-05
3,457	Size Separation Spatial Join	1997	SIGMOD	7.0755358e-05
4,529	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.1078661e-05
4,612	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0484423e-05
7,729	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6660821e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
148	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041182766
3,514	Spatio-Textual Similarity Joins	2013	VLDB	7.0226998e-05
2,672	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.3363695e-05
4,873	Power-Law Based Estimation of Set Similarity Join Size	2009	VLDB	5.8602304e-05
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013486418
478	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.0002222104
3,543	Approximation Techniques for Spatial Data	2004	SIGMOD	6.9917053e-05
10,921	Optimal (Multiway) Spatial Joins	2024	PODS	4.1945683e-05
2,053	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6728745e-05
2,974	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	7.789769e-05