Accelerated Approximate Nearest Neighbors Search Through Hierarchical Product Quantization
Accelerated Approximate Nearest Neighbors Search Through Hierarchical Product Quantization
复制标题
DOI：
10.1109/icfpt47387.2019.00019
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Ameer Abdelhadi;C. Bouganis;G. Constantinides
中科院分区：
文献类型：
--
作者：
Ameer Abdelhadi;C. Bouganis;G. Constantinides
在许多机器学习应用程序中，一个基本的重复任务是在高维度量空间中搜索最近邻。为了回答大规模问题中的查询，最先进的方法采用近似最近邻（ANN）搜索，一种以高概率返回最近邻的搜索，以及压缩数据集的技术。基于乘积量化（PQ）的人工神经网络搜索方法已经在包括分类、回归和信息检索在内的几个问题中表现出了最先进的性能。数据集被编码为多个低维码本的笛卡尔积，从而实现更快的搜索和更高的压缩。基于PQ的ANN搜索方法本质上是并行的，可用于硬件加速。本文提出了一种新的分层PQ（HPQ）的人工神经网络搜索方法，以及FPGA定制的架构，其实现优于当前最先进的系统。HPQ逐渐细化搜索空间，减少数据比较的数量，并支持流水线搜索。在Stratix 10 FPGA器件上的架构映射显示，与当前最先进的系统相比，加速超过250倍，为处理更大的数据集和/或改善当前系统的查询时间开辟了空间。
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 ×250 speedups over current state-of-the-art systems, opening the space for addressing larger datasets and/or improving the query times of current systems.