Beyond millisecond latency kNN search on commodity machine

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.