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: 5121
Venue: SIGMOD
Year: 2015
Pagerank: 5.282937e-05
Overall Rank: 9,355 | 35.82%
DOI: 10.1145/2723372.2749442

Incoming Non-self Citations Over Time

Authors

1. Xiaoyang Wang (University of New South Wales)
2. Ying Zhang (University of Technology Sydney)
3. Wenjie Zhang (University of New South Wales)
4. Xuemin Lin (University of New South Wales)
5. Muhammad Aamir Cheema (Monash University)

BibTeX Citation

@inproceedings{wang_sigmod15,
        title = {{Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates}},
        author = {Wang, Xiaoyang and Zhang, Ying and Zhang, Wenjie and Lin, Xuemin and Cheema, Muhammad Aamir},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2749442},
        url = {https://dl.acm.org/doi/10.1145/2723372.2749442},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,995	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.7301567e-05
9,776	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.2209769e-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
50	Efficient Query Evaluation on Probabilistic Databases	2004	VLDB	0.00043596705
1,097	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00012181027
1,327	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB	0.00011141552
1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00011025316
1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00010229844
2,042	Orion 2.0: Native Support for Uncertain Data	2008	SIGMOD	9.2691675e-05
2,689	The Spatial Skyline Queries	2006	VLDB	8.2559825e-05
4,112	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.8944534e-05
4,850	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	6.480347e-05
7,025	Nearest Neighbor Searching Under Uncertainty II	2013	PODS	5.7234179e-05
7,350	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD	5.6358517e-05
9,261	Hypersphere Dominance: An Optimal Approach	2014	SIGMOD	5.2968259e-05
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,659	Spatial Queries with Two kNN Predicates	2012	VLDB
2	1,685	Closest Pair Queries in Spatial Databases	2000	SIGMOD
3	1,441	Efficient Processing of Top-k Spatial Preference Queries	2011	VLDB
4	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
5	3,118	Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor	2009	VLDB
6	7,025	Nearest Neighbor Searching Under Uncertainty II	2013	PODS
7	2,827	Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data	2007	VLDB
8	2,158	What is the nearest neighbor in high dimensional spaces?	2000	VLDB
9	2,349	On Efficient Spatial Matching	2007	VLDB
10	7,350	Boosting Spatial Pruning: On Optimal Pruning of MBRs	2010	SIGMOD