| Title | Accelerated Approximate Nearest Neighbors Search Through Hierarchical Product Quantization |
| Publication Type | Conference Paper |
| Year of Publication | 2019 |
| Authors | Abdelhadi, Ameer M.S., Bouganis, Christos-Savvas, Constantinides, George A. |
| Conference Name | 2019 International Conference on Field-Programmable Technology (ICFPT) |
| Keywords | accelerated Approximate Nearest Neighbors search, ANN search, approximate search, artificial intelligence, Cartesian product, classification, field programmable gate arrays, FPGA-tailored architecture, hardware acceleration, hierarchical PQ, Hierarchical product Quantization, High-Dimensional Indexing, HPQ, information retrieval, learning (artificial intelligence), machine learning, mathematics computing, Measurement, Metrics, multiple low-dimensional codebooks, nearest neighbor search, nearest neighbour methods, neural nets, Online Indexing, pattern classification, product quantization, pubcrawl, query answering, query processing, regression, regression analysis, search problems, Search Space, similarity search, vector quantization |
| Abstract | A fundamental recurring task in many machine learning applications is the search for the Nearest Neighbor in high dimensional metric spaces. Towards answering queries in large scale problems, state-of-the-art methods employ Approximate Nearest Neighbors (ANN) search, a search that returns the nearest neighbor with high probability, as well as techniques that compress the dataset. Product-Quantization (PQ) based ANN search methods have demonstrated state-of-the-art performance in several problems, including classification, regression and information retrieval. The dataset is encoded into a Cartesian product of multiple low-dimensional codebooks, enabling faster search and higher compression. Being intrinsically parallel, PQ-based ANN search approaches are amendable for hardware acceleration. This paper proposes a novel Hierarchical PQ (HPQ) based ANN search method as well as an FPGA-tailored architecture for its implementation that outperforms current state of the art systems. HPQ gradually refines the search space, reducing the number of data compares and enabling a pipelined search. The mapping of the architecture on a Stratix 10 FPGA device demonstrates over x250 speedups over current state-of-the-art systems, opening the space for addressing larger datasets and/or improving the query times of current systems. |
| DOI | 10.1109/ICFPT47387.2019.00019 |
| Citation Key | abdelhadi_accelerated_2019 |
Accelerated Approximate Nearest Neighbors Search Through Hierarchical Product Quantization