Abstract
The k nearest neighbor (k NN) search on road networks is an important function in web mapping services. These services are now dealing with rapidly arriving queries, that are issued by a massive amount of users. While overlay graph-based indices can answer shortest path queries efficiently, there have been no studies on utilizing such indices to answer k NN queries efficiently. In this paper, we fill this research gap and present two efficient k NN search solutions on overlay graph-based indices. Experimental results show that our solutions offer very low query latency (0.1 ms) and require only small index sizes, even for 10-million-node networks.
Original language | English |
---|---|
Article number | 2426702 |
Pages (from-to) | 2618-2631 |
Number of pages | 14 |
Journal | IEEE Transactions on Knowledge and Data Engineering |
Volume | 27 |
Issue number | 10 |
DOIs | |
Publication status | Published - 1 Oct 2015 |
Keywords
- Nearest neighbor searches
- Overlay networks
- Spatial databases
ASJC Scopus subject areas
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics