● 摘要
大数据时代的到来给海量数据的管理带来了新的挑战和契机。其中，大数据（尤其是非结构化数据）的快速检索作为一个非常关键问题亟待解决。基于哈希的最近邻搜索在实时性和准确性方面优势显著，成为解决大数据管理的关键技术之一。
已有哈希最近邻搜索方法通常仅能处理向量等简单类型的数据。而在实际应用中，图像、视频等非结构化数据往往同时存在属性、 语义、底层特征等多种类型的描述特征。针对这些复杂多样的特征数据，如何设计高效的非结构化数据的哈希最近邻搜索方法还需要深入研究。
论文针对海量非结构化数据（尤其是图像），结合四面体数据模型，分别面向基于底层特征和基于底层特征与语义特征关联的检索模式，从底层特征分布的感知、多特征的关联（多种底层特征关联、底层特征和语义特征关联）以及面向应用的通用哈希等三个层次，较系统地研究了基于哈希的大规模近似最近邻搜索问题。%总体而言，本文主要内容和贡献如下：
（1）在底层特征分布感知方面，论文同时考虑了底层特征的局部近邻结构和全局聚类分布两个因素，提出了结构共享的哈希方法。该方法充分利用整个数据空间的信息，将哈希投影向量拆分为共享子空间和原始数据空间两个部分，其中共享子空间对应于所有哈希函数共享的内部结构。论文将哈希视为特征降维和量化过程的复合，在该过程中最大程度地保持原始数据的局部相似性并减少二元量化损失，因此保证了学习到的哈希函数不仅能够捕捉数据局部的最近邻结构，还可以感知数据全局的聚类分布状态。该方法结合了数据的局部和全局特性，通过哈希函数结构共享，从整体上提高了所有哈希函数的区分能力。
（2）在多种底层特征关联方面，论文研究了多种底层特征的融合策略，提出了同时适用于监督和非监督情形的统一的多特征核哈希框架。多种特征经过非线性映射后在核空间中串联组合成一种特征，该特征在一定程度上降低了计算量，同时使哈希函数转化为能够支持多种数据类型的多核线性组合的形式。对于监督情形，该方法充分利用多种特征的互补关系来保持原始数据的语义相似关系；而对于非监督情形，则通过低秩矩阵恢复发现多种特征定义的相似度量中共有的数据内在的相似关系。该方法能够综合多种互补的底层特征，缩小了语义鸿沟，从而提高了非结构化数据检索的鲁棒性和准确率。
（3）在底层特征和语义特征关联方面，论文针对多标签数据首次提出了支持底层特征和语义特征关联查询的哈希方法，扩展了传统哈希方法的使用范围。该方法利用部分语义标签在特征空间分布相似的特点，采用提升方法顺序寻找标签和哈希函数之间的稀疏关联性，同时学习针对标签子集的高质量哈希函数。针对底层特征和与语义特征的关联查询，该方法通过选择与查询关键字最关联的哈希函数来完成检索，实现查询自适应。该方法中每个哈希函数仅针对存在语义关联的标签子集，因此能够更好地保持数据的语义相似关系，同时还非常适合大规模的多标签数据。
（4）在通用哈希方面，论文借鉴特征选择的思想，首次提出了基于哈希比特选择的通用的哈希最近邻搜索方法。该方法采用无向加权图来表示候选的哈希比特，从理论上将哈希比特选择问题转化为图上的稠密子图（正则主导集合）发现，并给出了快速求解算法。针对多哈希表查询，论文进一步提出了基于比特选择的多哈希表构造方法。该方法顺序选取互补的哈希表来降低哈希表之间的冗余度，使得新构建的哈希表能够拟补前面哈希表的不足。本文提出的哈希比特选择方法具备很强的通用性，不仅支持不同类型、不同配置的哈希算法，同时还支持多特征融合等各种检索场景。