开放环境多分布特性的局部敏感哈希检索方法
作者:
作者单位:

作者简介:

张仕(1977-),男,博士,副教授,CCF高级会员,主要研究领域为机器学习,流计算,大数据算法研究;
潘淼鑫(1987-),女,讲师,主要研究领域为机器学习,大数据检索;
赖会霞(1975-),女,讲师,主要研究领域为机器学习,大数据检索;
张路路(1996-),男,硕士生,主要研究领域为人工智能技术及应用;
肖如良(1966-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为系统安全工程,机器学习,计算智能,大数据技术;
陈伟林(1996-),男,硕士生,主要研究领域为机器学习,大数据检索.

通讯作者:

肖如良,E-mail:xiaoruliang@fjnu.edu.cn

中图分类号:

基金项目:

国家自然科学基金(61772004);福建省科技重大项目(2020H6011);福建省自然科学基金(2020J01161)


Open Environmental Locality-sensitive Hashing Retrieval for Multiple Distributed Characteristics
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    基于局部敏感哈希的检索方法能够较好地解决高维大规模数据的近似近邻检索问题.但在开放环境下针对多种分布特性时,迄今尚未有令人满意的解决方案.利用Laplacian算子对数据分布剧烈变化敏感的特性,提出一种具有全局性、适用于开放环境下多种分布特性的基于Laplacian算子的局部敏感哈希搜索方法(LPLSH).该方法把Laplacian算子应用于数据投影的概率密度分布,找到数据投影分布的剧烈变化位置作为超平面的偏移量.从理论上证明了精简维度的哈希函数能够保持局部敏感性及低投影密度区间分割的有效性,分析了利用Laplacian算子计算的二阶导数对超平面偏移量设置的指导意义.与其他8种方法对比,LPLSH算法的F1值是其他方法最优值的0.8倍-5倍,耗费时间也大幅减少.通过对具有多种分布特性数据集上的实验验证,结果表明:LPLSH方法能够同时兼顾效率、精度和召回率,可满足开放环境下多分布特性的大规模高维检索的鲁棒性需求.

    Abstract:

    The retrieval methods based-on locality-sensitive hashing (LSH) provide a feasible solution to the problem of approximate nearest neighbor (ANN) search on high-dimensional, multiple distributed characteristics, and massive data. However, there are still some unresolved problems in open environment, such as poor adaptability to the data with multiple distribution characteristics. Based on the fact that Laplacian operator is sensitive to sharp changes in data, an LSH retrieval method based on Laplacian operator (LPLSH) is proposed, which is suitable for data in open environment with a variety of distributed characteristics, and can segment data on global view. By applying Laplacian operator to the probability density distribution of data projection, the position of the sharp change of distribution will found as the offset of the hyperplane. This study proves theoretically that the reduced dimension can keep the local sensitivity characteristics of the hash function, and the global low projection density interval segmentation is helpful to improve the precision. The guiding significance of using Laplacian operator to obtain the second derivative to set the hyperplane offset is also analyzed. Compared with the other 8 methods based on LSH, the F1 value of LPLSH is 0.8-5 times of the optimal value of other methods, and it takes less time. Through the analysis of the distribution characteristics of experimental datasets, the experimental results show that LPLSH can take into account the efficiency, accuracy, and recall rate at the same time, can meet the robustness requirements of large-scale high- dimensional retrieval with multi-distribution characteristics in open environment.

    参考文献
    相似文献
    引证文献
引用本文

张仕,赖会霞,肖如良,潘淼鑫,张路路,陈伟林.开放环境多分布特性的局部敏感哈希检索方法.软件学报,2022,33(4):1200-1217

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-02-18
  • 最后修改日期:2021-07-16
  • 录用日期:
  • 在线发布日期: 2021-10-26
  • 出版日期: 2022-04-06
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号