PQBF: I/O-Efficient Approximate Nearest Neighbor Search by Product Quantization
Refereed conference paper presented and published in conference proceedings


Times Cited
Altmetrics Information
.

Other information
AbstractApproximate nearest neighbor (ANN) search in high-dimensional space plays an essential role in many multimedia applications. Recently, product quantization (PQ) based methods for ANN search have attracted enormous attention in the community of computer vision, due to its good balance between accuracy and space requirement. PQ based methods embed a high-dimensional vector into a short binary code (called PQ code), and the squared Euclidean distance is estimated by asymmetric quantizer distance (AQD) with pretty high precision. Thus, ANN search in the original space can be converted to similarity search on AQD using the PQ approach. All existing PQ methods are in-memory solutions, which may not handle massive data if they cannot fit entirely in memory. In this paper, we propose an I/O-efficient PQ based solution for ANN search. We design an index called PQB+-forest to support efficient similarity search on AQD. PQB+-forest first creates a number of partitions of the PQ codes by a coarse quantizer and then builds a B+-tree, called PQB+-tree, for each partition. The search process is greatly expedited by focusing on a few selected partitions that are closest to the query, as well as by the pruning power of PQB+-trees. According to the experiments conducted on two large-scale data sets containing up to 1 billion vectors, our method outperforms its competitors, including the state-of-the-art PQ method and the state-of-the-art LSH methods for ANN search.
All Author(s) ListYingfan LIU, Hong CHENG, Jiangtao CUI
Name of Conference2017 ACM Conference on Information and Knowledge Management (CIKM 2017)
Start Date of Conference06/11/2017
End Date of Conference10/11/2017
Place of ConferencePan Pacific
Country/Region of ConferenceSingapore
Proceedings TitleProceedings of the 2017 ACM Conference on Information and Knowledge Management, CIKM 2017
Year2017
Pages667 - 676
ISBN978-1-4503-4918-5
LanguagesEnglish-United States

Last updated on 2021-18-01 at 01:15