Database Paper Browser

Back to papers

Continuous Nearest Neighbor Search

Summary: Continuous nearest neighbor query over a line segment q=[s,e] returns <point, interval> pairs, i.e., the NN for each subpoint along the path. The paper replaces repetitive NN calls with a single-segment query, yielding orders-of-magnitude lower cost, plus analytical models for output size and query cost and several extensions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
8853
Venue
VLDB
Year
2002
Pagerank
0.00012871443
Overall Rank
1,272 | 91.17%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank Citing Paper Year Venue Pagerank
1,156 SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases 2004 SIGMOD 0.00013606064
1,511 Continuous Monitoring of Nearest Neighbors on Land Surface 2009 VLDB 0.00011582099
1,512 Indexing Land Surface for Efficient kNN Query 2008 VLDB 0.00011582099
1,545 Monitoring Path Nearest Neighbor in Road Networks 2009 SIGMOD 0.00011428609
1,916 A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects 2005 SIGMOD 0.00010110473
3,815 Location-based Spatial Queries 2003 SIGMOD 6.7314038e-05
4,896 The V*-Diagram: A Query-Dependent Approach to Moving KNN Queries 2008 VLDB 5.8467149e-05
6,378 Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings 2018 VLDB 5.0844506e-05
7,048 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 4.8460286e-05
7,539 Boosting Spatial Pruning: On Optimal Pruning of MBRs 2010 SIGMOD 4.7116182e-05
8,554 Lazy Updates: An Efficient Technique to Continuously Monitoring Reverse kNN 2009 VLDB 4.4893996e-05
8,928 Processing Moving kNN Queries Using Influential Neighbor Sets 2015 VLDB 4.4229886e-05
8,956 Efficient Algorithms for Finding Optimal Meeting Point on Road Networks 2011 VLDB 4.4188719e-05
9,119 Hypersphere Dominance: An Optimal Approach 2014 SIGMOD 4.3881453e-05
9,307 Range-based Obstructed Nearest Neighbor Queries 2016 SIGMOD 4.3544778e-05
9,365 Probabilistic Nearest Neighbor Queries on Uncertain Moving Object Trajectories 2014 VLDB 4.3468776e-05
9,899 An Extendable Framework for Managing Uncertain Spatio-Temporal Data 2014 SIGMOD 4.2559233e-05
12,235 K-Nearest Neighbor Search for Fuzzy Objects 2010 SIGMOD 4.1905499e-05
12,638 Integrated Data Management for Mobile Services in the Real World 2003 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank Cited Paper Year Venue Pagerank
2 R-Trees: A Dynamic Index Structure For Spatial Searching 1984 SIGMOD 0.0032118946
6 The R*-tree: An Efficient and Robust Access Method for Points and Rectangles 1990 SIGMOD 0.0016113151
24 The R+-Tree: A Dynamic Index For Multi-Dimensional Objects 1987 VLDB 0.00083300888
48 Nearest Neighbor Queries 1995 SIGMOD 0.0006954126
78 A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces 1998 VLDB 0.00056385781
628 Indexing the Positions of Continuously Moving Objects 2000 SIGMOD 0.00018957327
665 Fast Nearest Neighbor Search in Medical Image Databases 1996 VLDB 0.00018437125
798 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.00016484637
1,004 On Indexing Mobile Objects 1999 PODS 0.00014694512
1,180 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00013455619
1,605 Incremental Distance Join Algorithms for Spatial Databases 1998 SIGMOD 0.00011180126
1,769 Closest Pair Queries in Spatial Databases 2000 SIGMOD 0.00010608375
3,301 Indexing the Distance: An Efficient Method to KNN Processing 2001 VLDB 7.2450912e-05
3,802 Time-Parameterized Queries in Spatio-Temporal Databases 2002 SIGMOD 6.7524078e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,062 Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbor Searches 2000 VLDB 7.6348035e-05
210 Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph 2019 VLDB 0.00034086264
6,497 Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020 SIGMOD 5.0324877e-05
10,165 Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search 2026 SIGMOD 4.1905499e-05
4,721 Nearest-Neighbor Searching Under Uncertainty 2012 PODS 5.9647585e-05
2,342 Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring 2005 SIGMOD 9.0005088e-05
1,580 Continuous Nearest Neighbor Monitoring in Road Networks 2006 VLDB 0.00011272266
1,180 A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space 1997 PODS 0.00013455619
7,048 Continuous Obstructed Nearest Neighbor Queries in Spatial Databases 2009 SIGMOD 4.8460286e-05
3,415 Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates 2003 VLDB 7.1162894e-05