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: 5059
Venue: SIGMOD
Year: 2015
Pagerank: 4.3571035e-05
Overall Rank: 9,308 | 35.25%
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
8,175	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	4.5676289e-05
10,703	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	4.1945683e-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.00057857292
1,179	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00013457451
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
1,609	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011150935
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
2,331	Orion 2.0: Native Support for Uncertain Data	2008	SIGMOD	9.018559e-05
2,457	The Spatial Skyline Queries	2006	VLDB	8.769229e-05
4,373	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.2443809e-05
4,724	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9697823e-05
7,084	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	4.839879e-05
7,540	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD	4.7159549e-05
9,121	Hypersphere Dominance: An Optimal Approach	2014	SIGMOD	4.3922853e-05
9,122	Using Sets of Feature Vectors for Similarity Search on Voxelized CAD Objects	2003	SIGMOD	4.3922853e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,629	Spatial Queries with Two kNN Predicates	2012	VLDB	4.4809879e-05
1,768	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010622873
1,403	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB	0.00012176993
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
3,071	Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor	2009	VLDB	7.6120001e-05
7,084	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	4.839879e-05
2,366	Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data	2007	VLDB	8.9523637e-05
2,107	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.5330494e-05
2,247	On Efficient Spatial Matching	2007	VLDB	9.2048219e-05
7,540	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD	4.7159549e-05