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: 5262
Venue: SIGMOD
Year: 2016
Pagerank: 5.3600341e-05
Overall Rank: 9,227 | 35.88%
DOI: 10.1145/2882903.2915234

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,456	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.6751632e-05
10,711	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.1725247e-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.0011613174
1,275	Continuous Nearest Neighbor Search	2002	VLDB	0.00011473408
1,592	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB	0.00010343711
1,705	The New Casper: Query Processing for Location Services without Compromising Privacy	2006	VLDB	0.00010052533
7,021	Continuous Obstructed Nearest Neighbor Queries in Spatial Databases	2009	SIGMOD	5.7807026e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,249	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD	5.5241293e-05
10,129	WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search	2026	SIGMOD	5.1725247e-05
608	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00015876047
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011613174
1,806	Analysis Of Object Oriented Spatial Access Methods	1987	SIGMOD	9.8129659e-05
6,486	Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data	2011	VLDB	5.9225833e-05
30	Nearest Neighbor Queries	1995	SIGMOD	0.00052357678
12,276	Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures	2010	VLDB	5.1725247e-05
5,785	VoR-Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries	2010	VLDB	6.1500691e-05
7,021	Continuous Obstructed Nearest Neighbor Queries in Spatial Databases	2009	SIGMOD	5.7807026e-05