Continuous Monitoring of Nearest Neighbors on Land Surface

Summary: Presents two exact, dynamic skNN methods for moving objects on land surfaces, enabling GIS/LBS monitoring. SE-Tree is fat/short; ASI-Tree, a balanced angular-index tree with precomputed surface distances, localizes searches and speeds shortest-paths, beating SE-Tree. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h5e1c6fbe55717503
Venue: VLDB
Year: 2009
Pagerank: 9.9409992e-05
Overall Rank: 1,661 | 88.87%
DOI: 10.14778/1687627.1687753

Incoming Non-self Citations Over Time

Authors

1. Songhua Xing (University of Southern California)
2. Cyrus Shahabi (University of Southern California)
3. Bei Pan (University of Southern California)

BibTeX Citation

@article{xing_vldb09,
        title = {{Continuous Monitoring of Nearest Neighbors on Land Surface}},
        author = {Xing, Songhua and Shahabi, Cyrus and Pan, Bei},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687753},
        url = {https://doi.org/10.14778/1687627.1687753},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,729	New Lower and Upper Bounds for Shortest Distance Queries on Terrains	2016	VLDB	5.2705676e-05
8,733	Finding Shortest Paths on Terrains by Killing Two Birds with One Stone	2014	VLDB	5.2705676e-05
8,738	Finding Shortest Path on Land Surface	2011	SIGMOD	5.2705676e-05
10,507	Constrained Shortest Path Finding on Terrain Surfaces	2026	SIGMOD	4.9605343e-05
10,601	Efficient Proximity Queries on Simplified Height Maps	2026	SIGMOD	4.9605343e-05
11,560	Proximity Queries on Point Clouds using Rapid Construction Path Oracle	2024	SIGMOD	4.9605343e-05
11,747	EAR-Oracle: On Efficient Indexing for Distance Queries between Arbitrary Points on Terrain Surface	2023	SIGMOD	4.9605343e-05
12,340	Distance Oracle on Terrain Surface	2017	SIGMOD	4.9605343e-05
12,534	Terrain-Toolkit: A Multi-Functional Tool for Terrain Data	2014	VLDB	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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.0019892478
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051134355
449	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018112854
463	Query Processing in Spatial Network Databases	2003	VLDB	0.00017806376
547	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016545689
681	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00014792999
1,311	Continuous Nearest Neighbor Search	2002	VLDB	0.00011063629
1,574	Reverse kNN Search in Arbitrary Dimensionality	2004	VLDB	0.00010164216
1,660	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB	9.9414118e-05
1,662	Indexing Land Surface for Efficient kNN Query	2008	VLDB	9.9409992e-05
3,666	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD	7.0975312e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	681	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB
2	28	Nearest Neighbor Queries	1995	SIGMOD
3	5,981	k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation	2016	VLDB
4	2,206	Monitoring Path Nearest Neighbor in Road Networks	2009	SIGMOD
5	10,719	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD
6	8,733	Finding Shortest Paths on Terrains by Killing Two Birds with One Stone	2014	VLDB
7	8,923	Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks	2024	VLDB
8	6,073	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD
9	1,660	Continuous Nearest Neighbor Monitoring in Road Networks	2006	VLDB
10	1,662	Indexing Land Surface for Efficient kNN Query	2008	VLDB