面向复杂结构数据的哈希方法研究及其应用

Similarity computation and search upon large amount of data is the basic step towards further mining and learning tasks. For these two fundamental problems, hashing method is an effective tool. The real applications of hashing method include near-duplicate web page detection in the context of search engine and so on. However, existing hashing methods are mostly designed for simple-structured data, such as vectors and sets. There are few research works upon data of complex structure such as tree, graph and so on, while many kinds of data are naturally expressed by complex structures, such as chemical structures, social patterns in the context of social network, etc. In this project, we will make efforts to design hashing method for data of complex structure, to enable efficient similarity computation and search upon this kind of data. Furthermore, we will make substantial improvement over existing hashing methods, to decrease the error of similarity estimation, or to accelerate hash code generation. The research of this project can be applied to fast clustering, near-duplicate detection, similarity search and so on. This research project has important theoretical and practical values.

对大规模数据的相似计算和相似搜索是对数据进行进一步挖掘和学习的基础。对于这两个基础问题，哈希方法是一种有力的工具。目前的哈希方法已经在实际中得到了部分应用，比如搜索引擎中的近似重复网页检测等等。但是目前已有的哈希方法只能适用于简单结构类型的数据，比如向量、集合等。而对复杂结构的数据，如树、图等，目前还鲜有相应的哈希方法研究。而实际中有很多类型的数据是由这种复杂结构来表示的，比如化学分子结构，社交网络中的社交连接关系等等。本课题主要研究对复杂结构的数据设计相应的哈希方法，从而实现对这类数据的高效的相似计算和相似搜索。此外，本课题将改进已有的哈希方法，降低哈希码对数据间相似度的估计误差，或者加速哈希码的计算。本课题的研究可以应用于复杂结构数据的快速聚类，近似重复性检测，相似搜索等方面。该研究具有重要的理论意义和较大的实际应用潜力。

对大规模数据的相似计算和相似搜索是对数据进行进一步挖掘和学习的基础。对于这两个基础问题，哈希方法是一种有力的工具，且已得到了一些应用，比如搜索引擎中的近似重复网页检测等。但目前已有的哈希方法只能适用于简单结构类型的数据，比如向量、集合等。对复杂结构的数据，如树型结构数据等，目前还鲜有相应的哈希方法研究。而实际中有很多类型的数据是可以由这种复杂结构来表示的，比如一些化学结构，XML文档等。. 本项目主要研究对一类复杂结构的数据——树型结构数据，设计相应的哈希方法，从而实现对这类数据的高效的相似计算和相似搜索。此外，本项目研究改进已有的哈希方法，加速哈希码的计算。. 具体来说，针对无序树型结构数据，本项目提出了子路径哈希方法。该方法将哈希计算的复杂度从树节点规模的平方量级降低到线性量级，从而显著提高哈希计算的效率。在理论上，我们证明了在一定条件下，我们所提出的子路径签名可以重构出原始的无序树。另外，我们还在理论上证明了一个子路径签名相同时编辑距离之差的上界。实验表明，该子路径签名可以提供对编辑距离的估计，该哈希方法达到了与已有的嵌入中心哈希方法类似的精度；特别在分叉较少或类似路径结构的数据上，该方法取得了更优的检索精度。在所有实验中，子路径哈希方法的哈希时间均显著低于嵌入中心哈希方法。该方法在大规模XML文档近似重复检测、相似XML文档检索等应用场景中具有应用潜力。..对于已有的符号随机投影哈希，我们提出了快速符号随机投影哈希，将长为K的哈希码的计算时间从O(dK)降低到O(dlogK)，其中d是原始数据向量的维度，从而实现显著的加速。我们在理论上证明了该哈希码间的海明距离仍然提供对向量间角度的无偏估计。角度估计和向量相似搜索实验验证了该方法在时间和精度上能取得有效的折中。这表明，使用具有一定结构的哈希投影矩阵，可以实现哈希码计算上的显著加速，对其他类似的局部敏感哈希方法具有理论和方法上的启发意义。