Beyond millisecond latency kNN search on commodity machine

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


To the best of our knowledge, this is the first work that offers very low latency (0.1ms) per kNN query on 10-million-node networks on a commodity machine. This translates to a query throughput of 10,000 queries per second per commodity machine. Our experimental studies on large scale road networks show that our solutions are 1-3 orders of magnitudes faster than existing methods while our indexes are compact and can fit into main memory. In the future, we plan to further enhance the performance of kNN search with keywords.
Original languageEnglish
Title of host publication2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016
Number of pages2
ISBN (Electronic)9781509020195
Publication statusPublished - 22 Jun 2016
Event32nd IEEE International Conference on Data Engineering, ICDE 2016 - Helsinki, Finland
Duration: 16 May 201620 May 2016


Conference32nd IEEE International Conference on Data Engineering, ICDE 2016

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Graphics and Computer-Aided Design
  • Computer Networks and Communications
  • Information Systems
  • Information Systems and Management

Cite this