论文部分内容阅读
大数据时代,搜索效率对于图像检索、机器学习、推荐系统、语义文档检索等领域具有重要意义。近年来,基于近邻图的近似最近邻搜索方法(ANNS)相对于基于树、哈希、量化的ANNS具有更高的查询效率,引起了业界的特别关注。基于近邻图的近似最近邻搜索方法有可导航小世界图(NSW)、分层可导航小世界图(HNSW)、NSG等,其中分层可导航小世界图(HNSW)通过采用长距离边缩放和类似于跳表的分层结构表现出突出性能,成为该领域的一个主要研究和比较方法。但是HNSW存在以下几方面的不足:(1)不易进行分布式部署,难以实际应用于大规模数据搜索硬件资源;(2)采用的贪婪算法存在陷入局部最优的问题;(3)不支持动态多属性过滤搜索;(4)由于多层图结构以及连边策略存在搜索时内存开销大的问题。本文将针对HNSW存在的上述不足进行如下研究:(1)研究提出一种基于子图划分的分层可导航小世界图方法GP-HNSW,可支持分布式存储和查询,同时也一定程度优化了 HNSW可能陷入局部最优的问题。基于聚类方法将数据集划分为多个子集,每个子集采用HNSW图结构组织数据并可独立存储;(2)提出了基于子图划分的一种多属性NSW方法MA-NSW,解决了 NSW和HNSW搜索时不能进行动态多属性过滤的问题。MA-NSW通过导航树和多个叠加层相结合的方式构建索引,将特定属性过滤的近似最近邻搜索导向到对应的叠加层;(3)针对MA-NSW内存开销过大问题,提出一种量化编码优化方法SQMA-NSW,实验表明有很好的压缩效果。上述研究成果通过实验验证了比HNSW更为优越的查询速度和召回率,同时还支持动态并行增删结点的易维护优点。最后,基于上述研究成果设计和实现了一个大规模科技文档语义搜索平台,实现了根据多属性筛选和文本内容快速搜索相关文档的功能,验证了研究成果的有效性。本文的研究将对近似最近邻搜索方法的研究和应用提供很好的参考意义。