Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/61291
Title: Exploit every bit : effective caching for high-dimensional nearest neighbor search
Authors: Tang, B
Yiu, ML 
Hua, KA
Keywords: Caching
High dimensional data
Histogram
Similarity search
Issue Date: 2016
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on knowledge and data engineering, 2016, v. 28, no. 5, 7374714, p. 1175-1188 How to cite?
Journal: IEEE transactions on knowledge and data engineering 
Abstract: High-dimensional k nearest neighbor (kNN) search has a wide range of applications in multimedia information retrieval. Existing disk-based k NN search methods incur significant I/O costs in the candidate refinement phase. In this paper, we propose to cache compact approximate representations of data points in main memory in order to reduce the candidate refinement time during k NN search. This problem raises two challenging issues: (i) which is the most effective encoding scheme for data points to support k NN search? and (ii) what is the optimal number of bits for encoding a data point? For (i), we formulate and solve a novel histogram optimization problem that decides the most effective encoding scheme. For (ii), we develop a cost model for automatically tuning the optimal number of bits for encoding points. In addition, our approach is generic and applicable to exact/approximate k NN search methods. Extensive experimental results on real datasets demonstrate that our proposal can accelerate the candidate refinement time of k NN search by at least an order of magnitude.
URI: http://hdl.handle.net/10397/61291
ISSN: 1041-4347
EISSN: 1558-2191
DOI: 10.1109/TKDE.2016.2515603
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

3
Last Week
0
Last month
Citations as of Aug 10, 2017

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
Citations as of Jul 28, 2017

Page view(s)

29
Last Week
1
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



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