极大似然minwise哈希估计子研究

The data of document similarity detection is massive and diversity, Minwise hash can effectively solve the problem of high time complexity and space complexity for searching similarity of the huge amount of data, is cutting-edge research in the field of information retrieval, has potential and value. To break through the current low bottleneck problem of efficiency and precision in similarity estimation, based on the work of document similarity detection, we deeply study most core Minwise hash estimation theory, and strive to resolve two key scientific and technological issues: 1) Break through the limit of random permutation, research fingerprint generation of without random permutation to improve the efficiency of the hash process; 2 ) Establish high-precision maximum likelihood estimation of minwise hash, test, validate and evaluate the estimator to achieve high availability and high accuracy of similarity detection mechanism. The research achievements of this project will provide new estimators and new tools, greatly improve the efficiency and accuracy of document similarity detection.

文档相似性检测的数据具有海量性和多样性的特点，Minwise哈希能有效解决海量数据相似性求解的时间、空间复杂度高的问题，是信息检索的前沿研究领域，具有研究潜力和应用价值。为突破目前相似性检测中指纹生成效率和估计精度较低的瓶颈难题，本项目在已有文档相似性检测的研究基础上，研究最为核心的Minwise哈希估计理论，着力解决两个关键科学问题：1）突破随机排列的限制，研究无需随机排列的指纹生成方法，提高哈希过程的效率；2）建立高精度极大似然minwise哈希估计子以及对所构建的估计子模型进行测试、验证和评价，实现高有效性与高准确性的相似度检测机制。本项目研究成果将为文档相似性检测提供新的估计方法和工具，较大提高文档相似性检测的效率和精度。

文档相似性检测的数据具有海量性和多样性的特点，Minwise哈希能有效解决海量数据相似性求解的时间、空间复杂度高的问题，是信息检索的前沿研究领域，具有研究潜力和应用价值。为突破目前相似性检测中指纹生成效率和估计精度较低的瓶颈难题，本项目在已有文档相似性检测的研究基础上，研究最为核心的Minwise哈希估计理论，着力解决两个关键科学问题：1）突破随机排列的限制，研究无需随机排列的指纹生成方法，提高哈希过程的效率；2）建立高精度极大似然minwise哈希估计子以及对所构建的估计子模型进行测试、验证和评价，实现高有效性与高准确性的相似度检测机制。.本项目的主要结果体现在1）提高相似性估计精度方面，提出极大似然的估计子，准确率和召回率都高于Minwise估计。2）提高相似性估计效率方面，提出连接位三者估计子；提出Minwise Hash动态双重阈值过滤器，大幅减少比对次数；在阈值过滤器的基础上，发展了一种连接位极大似然动态过滤算法；提出无需随机排列的指纹生成方法，解决特征指纹提取的低效问题。3)在相似性检索方面，提出FGBC-iDistance: 细粒度位码过滤的高维索引，减少检索过程中距离计算次数；提出了一种聚类分离的分布式索引方法，提高分布式相似性检索算法的性能。本项目研究成果也为文档相似性检测提供新的估计方法和工具，较大提高文档相似性检测的效率和精度。以本项目成果为核心的《项目相似性检查系统》在国家自然科学基金委和湖南省科技厅等部门单位应用示范。