Beyond millisecond latency kNN search on commodity machine

Bailong Liao, U. Leong Hou, Man Lung Yiu, Zhiguo Gong

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)


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 languageEnglish
Article number2426702
Pages (from-to)2618-2631
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number10
Publication statusPublished - 1 Oct 2015


  • Nearest neighbor searches
  • Overlay networks
  • Spatial databases

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Beyond millisecond latency kNN search on commodity machine'. Together they form a unique fingerprint.

Cite this