Indexing Land Surface for Efficient kNN Query

Summary: Proposes the Surface Index R-tree (SIR-tree) with Tight Surface Index (TSI) and Loose Surface Index (LSI) to support exact skNN on land surfaces. Supports a priori-k-free, incremental search with localized pruning, reporting exact shortest surface paths and outperforming baselines in efficiency and accuracy on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hcf10fd7f84d8b621
Venue: VLDB
Year: 2008
Pagerank: 9.9787032e-05
Overall Rank: 1,651 | 88.91%
DOI: 10.14778/1454159.1454276

Incoming Non-self Citations Over Time

Authors

1. Cyrus Shahabi (University of Southern California)
2. Lu-An Tang (University of Southern California)
3. Songhua Xing (University of Southern California)

BibTeX Citation

@article{shahabi_vldb08,
        title = {{Indexing Land Surface for Efficient kNN Query}},
        author = {Shahabi, Cyrus and Tang, Lu-An and Xing, Songhua},
        journal = {PVLDB},
        series = {{VLDB} '08},
        volume = {1},
        number = {2},
        pages = {1020--1031},
        doi = {10.14778/1454159.1454276},
        url = {https://doi.org/10.14778/1454159.1454276},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,650	Continuous Monitoring of Nearest Neighbors on Land Surface	2009	VLDB	9.9787032e-05
8,701	New Lower and Upper Bounds for Shortest Distance Queries on Terrains	2016	VLDB	5.2905577e-05
8,705	Finding Shortest Paths on Terrains by Killing Two Birds with One Stone	2014	VLDB	5.2905577e-05
8,710	Finding Shortest Path on Land Surface	2011	SIGMOD	5.2905577e-05
10,429	Constrained Shortest Path Finding on Terrain Surfaces	2026	SIGMOD	4.9793485e-05
10,524	Efficient Proximity Queries on Simplified Height Maps	2026	SIGMOD	4.9793485e-05
11,503	Proximity Queries on Point Clouds using Rapid Construction Path Oracle	2024	SIGMOD	4.9793485e-05
11,695	EAR-Oracle: On Efficient Indexing for Distance Queries between Arbitrary Points on Terrain Surface	2023	SIGMOD	4.9793485e-05
12,291	Distance Oracle on Terrain Surface	2017	SIGMOD	4.9793485e-05
12,485	Terrain-Toolkit: A Multi-Functional Tool for Terrain Data	2014	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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.001992968
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051312804
458	Query Processing in Spatial Network Databases	2003	VLDB	0.00017868943
545	Influence Sets Based on Reverse Nearest Neighbor Queries	2000	SIGMOD	0.00016607433
677	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB	0.00014843441
1,304	Continuous Nearest Neighbor Search	2002	VLDB	0.00011104243

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,600	Efficient kNN Search in Public Transportation Networks	2024	VLDB
2	677	Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases	2004	VLDB
3	8,701	New Lower and Upper Bounds for Shortest Distance Queries on Terrains	2016	VLDB
4	28	Nearest Neighbor Queries	1995	SIGMOD
5	2,681	Distance Indexing on Road Networks	2006	VLDB
6	10,647	High-Throughput k Nearest Neighbors Search in Road Networks	2026	SIGMOD
7	6,107	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD
8	8,705	Finding Shortest Paths on Terrains by Killing Two Birds with One Stone	2014	VLDB
9	8,895	Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks	2024	VLDB
10	1,650	Continuous Monitoring of Nearest Neighbors on Land Surface	2009	VLDB