Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates

Summary: Proposes three spatial dominance operators to prune NN candidates for multi-instance objects, covering diverse NN functions. Classifies NN functions into three families, with efficient dominance checks and candidate generation, delivering major candidate reduction and strong empirical performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5060
Venue: SIGMOD
Year: 2015
Pagerank: 4.3544778e-05
Overall Rank: 9,308 | 35.31%
DOI: 10.1145/2723372.2749442

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,827	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	4.6379617e-05
10,711	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
74	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00057797415
1,181	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00013447487
1,535	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011461371
1,612	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011142757
1,703	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010820803
2,334	Orion 2.0: Native Support for Uncertain Data	2008	SIGMOD	9.01132e-05
2,457	The Spatial Skyline Queries	2006	VLDB	8.7618183e-05
4,370	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.2392118e-05
4,721	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9647585e-05
7,080	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	4.8353058e-05
7,539	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD	4.7116182e-05
9,119	Hypersphere Dominance: An Optimal Approach	2014	SIGMOD	4.3881453e-05
9,120	Using Sets of Feature Vectors for Similarity Search on Voxelized CAD Objects	2003	SIGMOD	4.3881453e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,629	Spatial Queries with Two kNN Predicates	2012	VLDB	4.4766922e-05
1,769	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010608375
1,317	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB	0.00012615781
1,535	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011461371
3,080	Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor	2009	VLDB	7.5993605e-05
7,080	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	4.8353058e-05
2,371	Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data	2007	VLDB	8.9443366e-05
2,099	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5429949e-05
2,248	On Efficient Spatial Matching	2007	VLDB	9.1958821e-05
7,539	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD	4.7116182e-05