Boosting Spatial Pruning: On Optimal Pruning of MBRs

Summary: Dominance-based pruning criterion for multi-dimensional MBRs: decide when A is definitely closer to query R than B, outperforming min/max-distance heuristics. Also handles partial domination and incremental, conservative estimates of total dominators, with strong empirical gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4293
Venue: SIGMOD
Year: 2010
Pagerank: 5.6358517e-05
Overall Rank: 7,350 | 49.58%
DOI: 10.1145/1807167.1807174

Incoming Non-self Citations Over Time

Authors

1. Tobias Emrich (Ludwig Maximilian University of Munich)
2. Hans-Peter Kriegel (Ludwig Maximilian University of Munich)
3. Peer Kroeger (Ludwig Maximilian University of Munich)
4. Matthias Renz (Ludwig Maximilian University of Munich)
5. Andreas Zuefle (Ludwig Maximilian University of Munich)

BibTeX Citation

@inproceedings{emrich_sigmod10,
        title = {{Boosting Spatial Pruning: On Optimal Pruning of MBRs}},
        author = {Emrich, Tobias and Kriegel, Hans-Peter and Kroeger, Peer and Renz, Matthias and Zuefle, Andreas},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807174},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807174},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,052	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.9941393e-05
6,561	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	5.8389373e-05
9,261	Hypersphere Dominance: An Optimal Approach	2014	SIGMOD	5.2968259e-05
9,355	Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates	2015	SIGMOD	5.282937e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
28	Nearest Neighbor Queries	1995	SIGMOD	0.00052102434
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
359	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.0002023153
560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016525569
601	Exact Indexing of Dynamic Time Warping	2002	VLDB	0.00015870156
1,281	Continuous Nearest Neighbor Search	2002	VLDB	0.00011349245
1,486	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00010625076
1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00010229844
1,612	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010218134
9,262	Using Sets of Feature Vectors for Similarity Search on Voxelized CAD Objects	2003	SIGMOD	5.2968259e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,555	Efficient Aggregation over Objects with Extent	2002	PODS
2	449	Query Processing in Spatial Network Databases	2003	VLDB
3	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
4	11,141	Optimal (Multiway) Spatial Joins	2024	PODS
5	4,657	Finding Near Neighbors Through Cluster Pruning	2007	PODS
6	8,828	Constraint-Based Query Optimization for Spatial Databases	1991	PODS
7	3,703	Approximation Techniques for Spatial Data	2004	SIGMOD
8	2,827	Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data	2007	VLDB
9	3,290	Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees	1995	SIGMOD
10	9,355	Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates	2015	SIGMOD