PQBF: I/O-Efficient Approximate Nearest Neighbor Search by Product Quantization

摘要: Approximate nearest neighbor (ANN) search in high-dimensional space plays an essential role many multimedia applications. Recently, product quantization (PQ) based methods for ANN have attracted enormous attention the community of computer vision, due to its good balance between accuracy and requirement. PQ embed a vector into short binary code (called code), squared Euclidean distance is estimated by asymmetric quantizer (AQD) with pretty high precision. Thus, original can be converted similarity on AQD using approach. All existing are in-memory solutions, which may not handle massive data if they cannot fit entirely memory. In this paper, we propose I/O-efficient solution search. We design index called PQB+-forest support efficient AQD. first creates number partitions codes coarse then builds B+-tree, PQB+-tree, each partition. The process greatly expedited focusing few selected that closest query, as well pruning power PQB+-trees. According experiments conducted two large-scale sets containing up 1 billion vectors, our method outperforms competitors, including state-of-the-art LSH