Beyond millisecond latency kNN search on commodity machine

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

doi:10.1109/TKDE.2015.2426702

Beyond millisecond latency kNN search on commodity machine

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

The Hong Kong Polytechnic University

Research output: Journal article publication › Journal article › Academic research › peer-review

7 Citations (Scopus)

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	https://doi.org/10.1109/TKDE.2015.2426702
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

More information

10.1109/TKDE.2015.2426702

http://hdl.handle.net/10397/96220

Cite this

@article{b85373f49c5e4c8ba8785c31aea95e98,

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

keywords = "Nearest neighbor searches, Overlay networks, Spatial databases",

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

year = "2015",

month = oct,

day = "1",

doi = "10.1109/TKDE.2015.2426702",

language = "English",

volume = "27",

pages = "2618--2631",

journal = "IEEE Transactions on Knowledge and Data Engineering",

issn = "1041-4347",

publisher = "IEEE Computer Society",

number = "10",

}

TY - JOUR

T1 - Beyond millisecond latency kNN search on commodity machine

AU - Liao, Bailong

AU - Leong Hou, U.

AU - Yiu, Man Lung

AU - Gong, Zhiguo

PY - 2015/10/1

Y1 - 2015/10/1

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

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

KW - Nearest neighbor searches

KW - Overlay networks

KW - Spatial databases

UR - https://www.scopus.com/pages/publications/84941367984

U2 - 10.1109/TKDE.2015.2426702

DO - 10.1109/TKDE.2015.2426702

M3 - Journal article

SN - 1041-4347

VL - 27

SP - 2618

EP - 2631

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

IS - 10

M1 - 2426702

ER -

Beyond millisecond latency kNN search on commodity machine

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this