TY - GEN
T1 - Fast nearest neighbor search on road networks
AU - Hu, Haibo
AU - Lee, Dik Lun
AU - Xu, Jianliang
PY - 2006/7/10
Y1 - 2006/7/10
N2 - Nearest neighbor (NN) queries have been extended from Euclidean spaces to road networks. Existing approaches are either based on Dijkstra-like network expansion or NN/distance precomputation. The former may cause an explosive number of node accesses for sparse datasets because all nodes closer than the NN to the query must be visited. The latter, e.g., the Voronoi Network Nearest Neighbor (V N 3) approach, can handle sparse datasets but is inappropriate for medium and dense datasets due to its high precomputation and storage overhead. In this paper, we propose a new approach that indexes the network topology based on a novel network reduction technique. It simplifies the network by replacing the graph topology with a set of interconnected tree-based structures called SPIE's. An nd index is developed for each SPIE and our new (k)NN search algorithms on an SPIE follow a predetermined tree path to avoid costly network expansion. By mathematical analysis and experimental results, our new approach is shown to be efficient and robust for various network topologies and data distributions.
AB - Nearest neighbor (NN) queries have been extended from Euclidean spaces to road networks. Existing approaches are either based on Dijkstra-like network expansion or NN/distance precomputation. The former may cause an explosive number of node accesses for sparse datasets because all nodes closer than the NN to the query must be visited. The latter, e.g., the Voronoi Network Nearest Neighbor (V N 3) approach, can handle sparse datasets but is inappropriate for medium and dense datasets due to its high precomputation and storage overhead. In this paper, we propose a new approach that indexes the network topology based on a novel network reduction technique. It simplifies the network by replacing the graph topology with a set of interconnected tree-based structures called SPIE's. An nd index is developed for each SPIE and our new (k)NN search algorithms on an SPIE follow a predetermined tree path to avoid costly network expansion. By mathematical analysis and experimental results, our new approach is shown to be efficient and robust for various network topologies and data distributions.
UR - http://www.scopus.com/inward/record.url?scp=33745627053&partnerID=8YFLogxK
M3 - Conference article published in proceeding or book
SN - 3540329609
SN - 9783540329602
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 186
EP - 203
BT - Advances in Database Technology - EDBT 2006 - 10th International Conference on Extending Database Technology, Proceedings
T2 - 10th International Conference on Extending Database Technology, EDBT 2006
Y2 - 26 March 2006 through 31 March 2006
ER -