PQTable: Fast Exact Asymmetric Distance Neighbor Search for Product Quantization Using Hash Tables
We propose the product quantization table (PQTable), a product quantization-based hash table that is fast and requires neither parameter tuning nor training steps. The PQTable produces exactly the same results as a linear PQ search, and is 10^2 to 10^5 times faster when tested on the SIFT1B data. In addition, although state-of-the-art performance can be achieved by previous inverted-indexing-based approaches, such methods do require manually designed parameter setting and much training, whereas our method is free from them. Therefore, PQTable offers a practical and useful solution for real-world problems.
Code (0)
등록된 구현이 없습니다.
Tasks
QuantizationSimilar Papers 제목 키워드 기반
PQTable: Non-exhaustive Fast Search for Product-quantized Codes using Hash Tables
In this paper, we propose a product quantization table (PQTable); a fast search method for product-quantized codes via hash-tables. An identifier of each database vector is associated with the slot of a hash table by usi…
CPUQuantizationApproximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach
Approximate Nearest Neighbor Search (ANNS) is fundamental to modern AI applications. Most existing solutions optimize query efficiency but fail to align with the practical requirements of modern workloads. In this paper,…
An algorithm for L1 nearest neighbor search via monotonic embedding
Fast algorithms for nearest neighbor (NN) search have in large part focused on L2 distance. Here we develop an approach for L1 distance that begins with an explicit and exact embedding of the points into L2. We show how …
Rank-Approximate Nearest Neighbor Search: Retaining Meaning and Speed in High Dimensions
The long-standing problem of efficient nearest-neighbor (NN) search has ubiquitous applications ranging from astrophysics to MP3 fingerprinting to bioinformatics to movie recommendations. As the dimensionality of the da…
Vocal Bursts Intensity PredictionAsymmetric Learning Vector Quantization for Efficient Nearest Neighbor Classification in Dynamic Time Warping Spaces
The nearest neighbor method together with the dynamic time warping (DTW) distance is one of the most popular approaches in time series classification. This method suffers from high storage and computation requirements fo…
ClassificationDynamic Time WarpingGeneral ClassificationQuantization+3