Beyond millisecond latency kNN search on commodity machine

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

doi:10.1109/ICDE.2016.7498406

Beyond millisecond latency kNN search on commodity machine

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

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

Abstract

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 language	English
Title of host publication	2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016
Publisher	IEEE
Pages	1524-1525
Number of pages	2
ISBN (Electronic)	9781509020195
DOIs	https://doi.org/10.1109/ICDE.2016.7498406
Publication status	Published - 22 Jun 2016
Event	32nd IEEE International Conference on Data Engineering, ICDE 2016 - Helsinki, Finland Duration: 16 May 2016 → 20 May 2016

Conference

Conference	32nd IEEE International Conference on Data Engineering, ICDE 2016
Country/Territory	Finland
City	Helsinki
Period	16/05/16 → 20/05/16

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

More information

10.1109/ICDE.2016.7498406

Cite this

@inproceedings{19a17ee72ab144a4b58a579a9129912c,

title = "Beyond millisecond latency kNN search on commodity machine",

abstract = "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.",

author = "Bailong Liao and {Hou U}, Leong and Yiu, {Man Lung} and Zhiguo Gong",

year = "2016",

month = jun,

day = "22",

doi = "10.1109/ICDE.2016.7498406",

language = "English",

pages = "1524--1525",

booktitle = "2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016",

publisher = "IEEE",

address = "United States",

note = "32nd IEEE International Conference on Data Engineering, ICDE 2016 ; Conference date: 16-05-2016 Through 20-05-2016",

}

TY - GEN

T1 - Beyond millisecond latency kNN search on commodity machine

AU - Liao, Bailong

AU - Hou U, Leong

AU - Yiu, Man Lung

AU - Gong, Zhiguo

PY - 2016/6/22

Y1 - 2016/6/22

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84980395690&partnerID=8YFLogxK

U2 - 10.1109/ICDE.2016.7498406

DO - 10.1109/ICDE.2016.7498406

M3 - Conference article published in proceeding or book

SP - 1524

EP - 1525

BT - 2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016

PB - IEEE

T2 - 32nd IEEE International Conference on Data Engineering, ICDE 2016

Y2 - 16 May 2016 through 20 May 2016

ER -

Beyond millisecond latency kNN search on commodity machine

Abstract

Conference

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this