基于哈希的海量高维数据近似最近邻查询研究

To address huge complexity of storage and computation that is brought about by large-scale high-dimensional data, we explore the hashing theory and its application in nearest neighbor search in this project. Though hashing technology is widely used as an effective method for compact representation of high-dimensional data, there still exists some drawbacks when dealing with approximate nearest neighbor search. Existing methods either obtains their efficiency in time by costing a huge amount of space or saves the space by sacrificing time. In this project, we first propose a novel version of approximate nearest neighbor problem, called I-th approximate nearest neighbor. Then, based on the analysis of the mechanism of hash mappings for high-dimensional data, we propose a computing model of hashing for approximate nearest neighbor search and build a framework of high-dimensional indexing and search based on linear order structures, in order to solve the issue of huge storage for existing methods. Finally, as for the hashed hamming space, we explore the mechanism of indexing and search for hamming distance and enhance the efficiency of nearest neighbor search in hamming space, as well as solve the high complexity of search for existing methods. In essence, there are two different solutions, "collision and filtering" and "compression and representation", for hashing to solve approximate nearest neighbor search, which could be combined together in this project. Its main feature is to bring about the efficiency in storage space and search time simultaneously and further satisfy the requirement of storage and search for large-scale high-dimensional data in the environment of big data.

本课题针对海量高维数据带来的存储、计算复杂度过高的问题，研究哈希理论及其在最近邻查询中的应用。哈希作为一种数据紧致表达的有效手段已经得到广泛应用，但是在处理近似最近邻查询时依然存在缺陷，现有方法或者以巨大的空间开销换取时间高效性，或者以时间开销节省存储空间。本课题首先针对最近邻查询，研究并提出一种返回近似第I个近邻的新型查询问题。其次，分析高维数据的哈希映射机理，提出面向近似最近邻查询的哈希计算模型，建立基于线序的高维向量空间索引与查询框架，解决现有方法存储开销巨大问题；最后，针对哈希映射后的海明空间，研究面向海明距离的索引与查询机理，实现海明空间中的高效最近邻查询，解决目前方法查询复杂度过高问题。本质上，哈希用于近似最近邻查询，存在"碰撞"过滤和压缩表达两种截然不同的解决思路，本课题融合两种思路，其特色是同时实现存储空间和查询时间的高效性，满足大数据环境下海量高维数据的存储和查询需求。

本课题针对海量高维数据带来的存储、计算复杂度过高的问题，研究哈希理论及最近邻查询方法，突破“海量高维数据的高效表达与近似计算”和“海明空间索引与查询机理”两个关键科学问题，并将这些理论成果迁移至复杂网络数据的高效管理与挖掘、大规模图像数据的紧致表达与检索以及复杂数据的安全计算与检索三个领域。项目组首先提出面向运动对象的近邻检索方法，优化基于聚类的高维数据近邻检索方法，建立新的基于 LSH 的高效索引机制，从而进一步提升了海量高维数据的索引和检索效率；紧接着将海量高维数据的索引机制引入网络数据管理中，提升了网络数据的组织管理效率，从而更好的实现一种典型网络数据（社会数据）的挖掘；为了进一步提升图像检索的效率，项目组针对灰度直方图、BOF特征等设计了新型的紧致表达方法，基于矩特征设计了高效的图像分类方法，再进一步结合项目组提出的海量高维数据索引技术，提升图像检索和分类的效率；最后，项目组成员依托于基于LSH的高效索引机制，提出了面向文本、地理信息数据和高维数据等不同应用于场景的安全检索方法，设计了通用的距离度量机制的安全计算方法和加密数据的高效安全访问方法，较为系统的结局了复杂数据的安全计算与检索问题。.项目组通过四年的持续深耕，共计发表论文 24 篇，其中 CCF Rank A / 中科院 I 区论文 3 篇，中科院 II 区论文 8 篇， CCF Rank B 会议论文 1 篇；新增申请发明专利 7 项，新增授权发明专利 6 项，其中新增申请并授权专利 3 项；培养已毕业博士生4人，已毕业硕士生25人。本课题的顺利开展为“海量高维数据的最近邻查询”的理论研究与实际成果转化奠定了技术基础。