Accelerated approximate nearest neighbors search through hierarchical product quantization

Abstract

A fundamental recurring task in many machinelearning applications is the search for the Nearest Neighbor inhigh dimensional metric spaces. Towards answering queries inlarge scale problems, state-of-the-art methods employ Approx-imate Nearest Neighbors (ANN) search, a search that returnsthe nearest neighbor with high probability, as well as techniquesthat compress the dataset. Product-Quantization (PQ) based ANNsearch methods have demonstrated state-of-the-art performancein several problems, including classification, regression and infor-mation retrieval. The dataset is encoded into a Cartesian productof multiple low-dimensional codebooks, enabling faster searchand higher compression. Being intrinsically parallel, PQ-basedANN search approaches are amendable for hardware accelera-tion. This paper proposes a novel Hierarchical PQ (HPQ) basedANN search method as well as an FPGA-tailored architecturefor its implementation that outperforms current state of theart systems. HPQ gradually refines the search space, reducingthe number of data compares and enabling a pipelined search.The mapping of the architecture on a Stratix 10 FPGA devicedemonstrates over×250 speedups over current state-of-the-artsystems, opening the space for addressing larger datasets and/orimproving the query times of current systems.