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: 3184
Venue: SIGMOD
Year: 2000
Pagerank: 5.1708554e-05
Overall Rank: 6,170 | 57.12%
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,540	Approximation Techniques for Spatial Data	2004	SIGMOD	6.9922652e-05
4,871	Power-Law Based Estimation of Set Similarity Join Size	2009	VLDB	5.8568724e-05
5,961	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD	5.2510172e-05
7,833	Containment Join Size Estimation: Models and Methods	2003	SIGMOD	4.6367487e-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.0040465394
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
27	Efficient and Effective Clustering Methods for Spatial Data Mining	1994	VLDB	0.00080846213
65	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00061977022
75	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00057450043
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
151	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00041010211
275	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029381206
923	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00015254021
1,111	Beyond Uniformity and Independence : Analysis of R-trees Using the Concept of Fractal Dimension	1994	PODS	0.0001389881
1,519	A Model for the Prediction of R-tree Performance	1996	PODS	0.00011535609
1,691	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	0.00010890775
2,119	Scalable Sweeping-Based Spatial Join	1998	VLDB	9.5036401e-05
2,673	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.3323551e-05
2,978	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	7.7848117e-05
3,462	Size Separation Spatial Join	1997	SIGMOD	7.0683581e-05
4,539	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD	6.0982886e-05
4,613	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.0427196e-05
7,727	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	4.6616221e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
147	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00041201518
3,294	Spatio-Textual Similarity Joins	2013	VLDB	7.2590482e-05
2,673	Spatial Joins Using Seeded Trees	1994	SIGMOD	8.3323551e-05
4,871	Power-Law Based Estimation of Set Similarity Join Size	2009	VLDB	5.8568724e-05
1,174	Spatial Hash-Joins	1996	SIGMOD	0.00013490827
479	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00022182486
3,540	Approximation Techniques for Spatial Data	2004	SIGMOD	6.9922652e-05
10,925	Optimal (Multiway) Spatial Joins	2024	PODS	4.1905499e-05
2,056	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6692561e-05
2,978	Estimating the Selectivity of Spatial Queries Using the 'Correlation' Fractal Dimension	1995	VLDB	7.7848117e-05