Range-based Obstructed Nearest Neighbor Queries

Summary: RONN extends CONN to return obstructed NN for every point in a range; baseline CONNB reduces to R-tree range queries. Proposes O-tree with optimal obstacle balance (OOB) to partition obstructed space, enabling RONN-OA and polygon indexing; experiments show RONN-OA beats R-tree baselines and OOB offers best balance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5323
Venue: SIGMOD
Year: 2016
Pagerank: 5.282937e-05
Overall Rank: 9,354 | 35.83%
DOI: 10.1145/2882903.2915234

Incoming Non-self Citations Over Time

Authors

1. Huaijie Zhu (Northeastern University)
2. Xiaochun Yang (Northeastern University)
3. Bin Wang (Northeastern University)
4. Wang-Chien Lee (Pennsylvania State University)

BibTeX Citation

@inproceedings{zhu_sigmod16,
        title = {{Range-based Obstructed Nearest Neighbor Queries}},
        author = {Zhu, Huaijie and Yang, Xiaochun and Wang, Bin and Lee, Wang-Chien},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915234},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915234},
        year = {2016}
}

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 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
1,281	Continuous Nearest Neighbor Search	2002	VLDB	0.00011349245
1,620	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB	0.00010206305
1,734	The New Casper: Query Processing for Location Services without Compromising Privacy	2006	VLDB	9.9009944e-05
7,140	Continuous Obstructed Nearest Neighbor Queries in Spatial Databases	2009	SIGMOD	5.6928705e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,618	Continuous Monitoring of Nearest Neighbors on Land Surface	2009	VLDB
2	10,417	WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search	2026	SIGMOD
3	623	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD
4	4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD
5	1,814	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD
6	6,561	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB
7	28	Nearest Neighbor Queries	1995	SIGMOD
8	12,463	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB
9	5,875	VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries	2010	VLDB
10	7,140	Continuous Obstructed Nearest Neighbor Queries in Spatial Databases	2009	SIGMOD