中文摘要：

近似近邻查询是信息检索领域中的一项重要技术.随着文本、图像、视频等非结构化数据规模的迅速增长,如何对海量高维数据进行快速、准确的查询是处理大规模数据所必须面对的问题.哈希作为近似近邻查询的关键方法之一,能够在保持数据相似性的条件下对高维数据进行大比例压缩.以往所提出的哈希方法往往都是应对集中式存储的数据,因而难以处理分布式存储的数据.该文提出了一种基于乘积量化的分布式哈希学习方法SparkPQ,并在Spark分布式计算框架下实现算法.在传统的乘积量化方法的基础上,该文首先给出了分布式乘积量化模型的形式化定义.然后,作者设计了一种按行列划分的分布式矩阵,采用分布式K-Means算法实现模型求解和码本训练,利用训练出的码本模型对分布式数据进行编码和索引.最终,该文构建了一套完整的近似近邻查询系统,不仅可以大幅降低存储和计算开销,而且在保证高检索准确率的条件下加速查询效率.在较大规模的图像检索数据集上进行的实验验证了方法的正确性和可扩展性.

英文摘要：

Approximate nearest neighbor（ANN）search is an important technique in Information Retrieval.With rapid growth of volumes of unstructured data like texts,images,and videos,how to perform efficient and accurate search from large-scale data becomes an inevitable problem.As a key approach to approximate nearest neighbor search,hashing can perform similarity-preserving compression for high-dimensional data.Previous hashing methods are usually applied to centralized data,hence they cannot process distributed data.In this paper,SparkPQ,a novel distributed learning to hash method based on Product Quantization（PQ）is proposed,which is implemented in the Spark distributed computing framework.Based on the seminal Product Quantization（PQ）method,we first give a formal definition of distributed Product Quantization model.Then,we design a distributed matrix partitioned by rows and columns and apply distributed K-Means algorithm to solve the SparkPQ model and train a codebook.We encode and index the distributed data from database with the codebook model.Finally,we build an integrated ANN search system which not only reduces the storage and computation cost substantially,but also speeds up thesearch efficiency with guaranteed search accuracy.A comprehensive empirical study on largescale image retrieval datasets validates the effectiveness and scalability of the proposed distributed learning to hash method.