Beyond millisecond latency kNN search on commodity machine
Liao B.1; Leong Hou U.1; Yiu M.L.1; Gong Z.2
2015-10-01
Source PublicationIEEE Transactions on Knowledge and Data Engineering
ISSN10414347
Volume27Issue:10Pages:2618-2631
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.

KeywordNearest Neighbor Searches Overlay Networks Spatial Databases
DOI10.1109/TKDE.2015.2426702
URLView the original
Indexed BySCIE
Language英语
WOS Research AreaComputer Science ; Engineering
WOS SubjectComputer Science, Artificial Intelligence ; Computer Science, Information Systems ; Engineering, Electrical & Electronic
WOS IDWOS:000361245300003
Fulltext Access
Citation statistics
Cited Times [WOS]:4   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionDEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Affiliation1.Universidade de Macau
2.Hong Kong Polytechnic University
First Author AffilicationUniversity of Macau
Recommended Citation
GB/T 7714
Liao B.,Leong Hou U.,Yiu M.L.,et al. Beyond millisecond latency kNN search on commodity machine[J]. IEEE Transactions on Knowledge and Data Engineering,2015,27(10):2618-2631.
APA Liao B.,Leong Hou U.,Yiu M.L.,&Gong Z..(2015).Beyond millisecond latency kNN search on commodity machine.IEEE Transactions on Knowledge and Data Engineering,27(10),2618-2631.
MLA Liao B.,et al."Beyond millisecond latency kNN search on commodity machine".IEEE Transactions on Knowledge and Data Engineering 27.10(2015):2618-2631.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Liao B.]'s Articles
[Leong Hou U.]'s Articles
[Yiu M.L.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Liao B.]'s Articles
[Leong Hou U.]'s Articles
[Yiu M.L.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Liao B.]'s Articles
[Leong Hou U.]'s Articles
[Yiu M.L.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.