论文分享
随着大模型的兴起，向量数据库及向量检索技术逐渐从幕后走向台前。然而，对于这个领域初次接触的伙伴来说，可能会感到无从下手。在这个必读论文系列中，我们将根据不同论文的分类为您推荐一些在向量检索领域中备受认可和经典的论文，会将这些论文的内容进行简要概括，方便大家进行筛选，找到学习的方向和路径。无论您是新手还是有一定经验的从业者，希望这个系列能为您提供有价值的知识和见解。
本期分享的论文为综述类论文。
高维数据的近似最近邻搜索
VectorSearch
论文：
Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement
论文链接：
https://arxiv.org/pdf/1610.02455.pdf
本文全面评估了16种最先进算法在不同领域（包括数据库、机器学习、多媒体和计算机视觉）中用于近似最近邻搜索（ANNS）的性能，使用20个数据集和各种评估指标，并提出了一种在大多数数据集上实现高查询效率和召回率的新方法。
实验设置
本文使用各种评估指标和不同的查询工作负载，对20个数据集上的16种最先进的近邻搜索 (ANNS) 方法进行了全面的实验评估。搜索程序以 C 语言实现，并且禁用特定于硬件的优化，例如基于 SIMD 的距离计算，以确保一致性。
实验结果
在第一轮评估中，对每个类别中不同算法的性能进行了比较。
-基于 LSH 的方法，特别是 SRS，在加速和召回率方面优于 QALSH。
-OPQ 是基于编码的方法中性能最好的算法。
-FLANN、Annoy 和 VP-Tree 在基于树的空间分区类别中进行了评估，其中 FLANN-KD 和 FLANN-HKM 的性能最高。
-KGraph 和 HNSW 在基于邻域的类别中表现优于其他算法。
-在基于邻域的方法中，RCT 的索引大小最小。KGraph 和 HNSW 被选为基于社区的方法的代表。
根据第一轮的结果，在第二轮评估中，对七种算法进行了全面的实验：SRS、OPQ、FLANN、Annoy、HNSW、KGraph 和 DPG。
表 6 根据搜索性能、索引大小、索引构建时间和可扩展性对七种算法的性能进行了排名。SRS 是唯一能够在理论上保证搜索质量且易于调整参数的算法。Annoy 的参数调整很简单，而 FLANN 需要更复杂的调整过程。-基于全面评估向用户提出的建议包括使用 DPG 和 HNSW 处理具有足够计算资源的高维数据。推荐使用 Annoy，因为它具有出色的搜索性能，并且在性能和索引大小/构造时间之间进行了权衡。还推荐使用 KGraph，但少数数据集除外，Annoy 的表现更好。对于具有适度计算资源的大型数据集，OPQ 和 SRS 是不错的选择，因为它们的索引大小和构造时间都很小。SRS 因其处理数据点更新的能力和理论保证而脱颖而出，使其与其他算法区分开来。
总结
本文评估了各种最先进的 ANNS 算法，并根据其性能提供了实用建议。但也依旧存在其局限性，作者建议将来的工作使用更大的数据集、高维稀疏数据、调整算法以及考虑其他距离指标，强调了在理解高维真实数据方面需要创新的解决方案。
高维向量相似度搜索的新趋势
VectorSearch
论文：
New trends in high-D vector similarity search: al-driven, progressive, and distributed VLDB 2021
讲解课件：文末获取
这篇论文介绍了高维向量相似性搜索的新趋势，通过应用人工智能、渐进式和分布式方法，解决了高维数据分析中的问题，并取得了一些成果。
实验设置
本文讨论了使用不同访问路径（如串行扫描、跳跃顺序扫描和基于树的索引）来回答相似性搜索查询的方法。将查询的摘要（Q'）与每个候选项的摘要进行比较。使用LB属性来确定是否可以剪枝候选项。比较了索引和扫描在回答相似性搜索查询方面的性能。实验设置和详细信息没有提及。
实验结果
本文比较了查询 Q 和数据集中每个候选项的摘要之间的摘要。将查询Q的摘要与每个候选项的摘要进行比较，如果无法剪枝摘要，则将查询 Q 与原始候选项进行比较。还探讨了回答相似性搜索查询的不同访问路径，包括串行扫描、跳跃顺序扫描和基于树的索引。比较了使用索引和扫描，并提出了扩展方法，如跳跃顺序扫描和索引。还讨论了结果在一定距离内的概率。此外，本文引入了 iSAX Summarization，使用分段聚合逼近（PAA）和符号聚合逼近（SAX）表示数据序列。
总结
高维数据是各种领域和应用程序中的常见数据类型，但由于其复杂性，对其进行分析具有挑战性。数据序列索引技术为精确和近似相似度搜索（包括基于磁盘的数据集）提供了出色的性能。通过并行、渐进和深度学习技术提高性能存在值得深入的研究机会。
基于图的近似近邻搜索
VectorSearch
论文：
A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
论文链接：
https://arxiv.org/pdf/2101.12631v1.pdf
这篇学术论文是一篇关于基于图的近似最近邻搜索算法的综合调查和实验比较的论文。论文介绍了近似最近邻搜索在推荐系统、信息检索和模式识别等多个应用领域的重要性，并提出了多种基于图的近似最近邻搜索算法。论文通过对13种代表性的基于图的近似最近邻搜索算法进行全面比较和实验评估，提供了新的发现和有用的原则，以改进算法的性能。此外，论文还讨论了基于图的近似最近邻搜索算法的适用场景、优化指南、研究方向和挑战。
实验设置
本实验使用了八个真实世界数据集，包括视频、音频、文本和图像数据集。这些数据集具有不同的特征，如元素数量、局部内在维度和难度级别。实验评估了13个代表性的基于图形的 ANNS 算法，并使用各种指标来衡量算法在索引构建和搜索方面的性能。实验在具有特定硬件和软件配置的 Linux 服务器上进行。每个算法的可调参数使用验证数据集进行了优化。
实验结果
本文提供的表格比较了各种基于图形的近似最近邻搜索（ANNS）算法的性能。这些算法根据它们的加速比、每秒查询数（QPS）和候选集大小（CS）进行评估。
结果显示，具有较高加速比的算法通常也能实现较高的 QPS，这表明图形化ANNS算法的搜索效率取决于搜索过程中的距离计算次数。
基于 RNG 和 MST 的算法，如 NSG 和 HCNNG，在各个类别中通常表现出色，特别是在难度较大的数据集上。基于 KNNG 和 DG 的算法，如 EFANNA 和 NSW，在简单数据集上表现良好，但在难度较大的数据集上性能显著下降。SPTAG 的搜索性能随着局部内在维度的增加而降低，可能是由于搜索过程中频繁的树遍历引起的。
候选集大小（CS）与算法类别、数据集和搜索性能有关。大多数算法可以通过适当设置 CS 来实现目标召回率。然而，一些算法，如 SPTAG，在 CS 增加时达到了一个上限，召回率几乎不随 CS 增加而变化。由于缓存容量的限制，CS通常受到限制，特别是在 GPU 环境中。基于 DG 和 RNG 的算法需要较小的 CS，而基于 KNNG 和 MST 的算法的 CS 取决于数据集。搜索性能较差的算法往往具有较大的 CS。
查询路径长度（PL）决定了 I/O 数量并影响搜索效率。具有较高搜索性能的算法通常具有较小的 PL，但具有较小 PL 的算法不一定具有良好的搜索性能。还评估了内存开销，基于 RNG 的算法具有最小的内存开销。具有额外索引结构的算法，如 SPTAG 和 IEH，具有较高的内存开销。较大的 AD 和 CS 值也会增加内存开销。
总体而言，基于改进构建策略的算法往往具有更好的性能。还评估了不同组件（如初始化、候选邻居获取和邻居选择）对搜索性能和构建时间的影响。
总结
本文从一个新的分类中考虑了13种代表性的基于图的ANNS算法并进行深入分析，全面评估和讨论了所有算法在8个真实数据集和12个合成数据集上的性能。还通过一个统一的框架公平地评估每个算法的重要组成部分。在某些方面，这项工作验证了许多以前的经验结论，同时也导致了新的发现，这将有助于未来的研究人员和从业者。本文通过理论分析和实验(例如 HNSW 和 NSG)确认哪些算法的细粒度组件(反映其核心优化)是等效的，还提供了一些有前途的研究方向和有见地的原则来优化算法的经验建议。最后，要指出的是，由于各种限制，本文只研究了基于主存的核心算法。展望未来，将考虑硬件优化(例如，SSD 和 GPU)，部署分布式实现，并为 ANNS 添加结构化属性约束。
向公众号发送【高维数据】获取论文讲解课件，也可以直接到我们的 GitHub 主页获取课件以及更多必读论文目录哦https://github.com/Unstructured-Data-Community/ANN-Papers
向量检索实验室
微信号：VectorSearch
扫码关注 了解更多
