网站策划ps,网站托管服务怎么收费,上海公司网站制作价格,行业协会网站建设的方案作者#xff1a;来自 Elastic Tommaso Teofili 了解如何使用智能提前终止策略让 HNSW 加快 KNN 搜索速度。 在高维空间中高效地找到最近邻的挑战是向量搜索中最重要的挑战之一#xff0c;特别是当数据集规模增长时。正如我们之前的博客文章中所讨论的#xff0c;当数据集规模…作者来自 Elastic Tommaso Teofili 了解如何使用智能提前终止策略让 HNSW 加快 KNN 搜索速度。 在高维空间中高效地找到最近邻的挑战是向量搜索中最重要的挑战之一特别是当数据集规模增长时。正如我们之前的博客文章中所讨论的当数据集规模有限时强力brute force最近邻搜索可能是最佳选择。另一方面随着向量数据集规模的增加切换到近似最近邻搜索有助于在不牺牲准确性的情况下保持查询速度。
Elasticsearch 通过分层可导航小世界算法Hierarchical Navigable Small World algorithm实现近似最近邻搜索。HNSW 提供了一种有效的向量空间导航方法降低了计算成本同时仍保持了较高的搜索准确性。特别是它的分层结构使得能够访问候选邻居并决定是否将它们包含在最终结果集中同时减少向量距离计算。
然而尽管 HNSW 算法有其优势但它可以进一步优化以适应大规模向量搜索。提高 HNSW 性能的一种有效方法是找到在特定情况下停止访问图的方法这称为提前终止。这篇博文探讨了 HNSW 的提前终止概念以及它们如何优化查询执行。 HNSW 中的冗余
HNSW 是一种近似最近邻算法它构建一个分层图其中节点表示向量边表示向量空间中向量之间的接近度。每层都包含越来越多的图节点。查询时搜索会遍历此图从随机入口点开始然后通过各层导航到最近的邻居。
搜索过程是迭代的随着检查更多节点和向量而扩展。速度和准确性之间的平衡是 HNSW 的核心但它仍然会导致冗余计算尤其是在涉及大型数据集时。
在 HNSW 中冗余计算主要发生在算法继续评估新节点或候选节点时这些节点或候选节点在查找查询的实际邻居方面几乎没有任何改进。发生这种情况的原因是在标准 HNSW 遍历中算法逐层进行探索和扩展候选节点直到所有可能的路径都用尽。
具体来说当数据集包含高度相似或重复的向量、具有密集簇内连接的簇或具有很少内在结构的高维空间中的向量时可能会出现这种冗余。这种冗余会导致访问不必要的边增加内存使用量并可能降低搜索性能而不会提高准确性。在相似度得分快速衰减的高维空间中一些边edges通常无法在图中提供有意义的捷径从而导致导航路径效率低下。
因此如果在遍历图时可以执行大量不必要的计算则可以尝试改进 HNSW 算法以缓解此问题。 提前终止 FTW
导航解决方案空间是优化和搜索算法中的一个基本概念其目标是在一组可能的解决方案中找到最佳解决方案。解决方案空间代表给定问题的所有潜在解决方案导航它涉及系统地探索这些可能性。这个过程可以可视化为通过一个图移动其中每个节点代表一个不同的解决方案目标是确定最符合问题标准的节点。了解如何有效地导航解决方案空间对于解决具有大量解决方案的复杂问题至关重要。提前终止是一种通用的优化策略可以应用于任何此类算法以在特定情况下做出何时停止搜索解决方案的明智决定。
如果任何解决方案被认为 “足够好” 以满足期望的标准则可以停止搜索并且该解决方案可以被视为良好候选或最佳解决方案。这意味着一些潜在的更好的解决方案可能仍未被探索因此很难在最终解决方案的效率和质量之间找到完美的折衷方案。 HNSW 中的提前终止
在 HNSW 中提前终止可用于在完全评估所有潜在候选节点向量之前停止搜索过程。评估候选节点意味着计算查询向量与正在处理的图中节点对应的向量之间的实际相似度因此在遍历每一层时跳过一堆这样的操作可以大大降低查询的计算成本。
另一方面跳过原本会产生真正最近邻居的候选节点肯定会影响搜索结果的质量可能会遗漏一些接近查询向量的候选向量。
因此效率收益和准确度损失之间的权衡需要谨慎处理。提前终止在以下情况下很有用
次线性效率Sublinear Efficiency你希望优化性能以换取略低的召回率。高吞吐量系统High-Throughput Systems更快的响应时间比最高的准确度更有价值。资源限制Resource Constraints计算或内存限制使得无法完全遍历 HNSW 图。
在 HNSW 的上下文中有多种选项可用于实施提前终止策略。
固定候选池大小最简单的提前终止策略之一是限制候选池的大小例如搜索期间评估的节点数。在 HNSW 中搜索过程是迭代的随着搜索的进行会扩展到更多节点。通过设置考虑的候选数限制我们可以提前终止搜索并仅根据整个图的子集返回结果。当然这可以以分层方式实现也可以考虑整个图中的所有节点。基于距离阈值的终止另一种可能有效的提前终止策略是根据查询向量与对应于 HNSW 节点的向量之间的距离计算做出明智的决策。可以根据查询向量与当前最近向量之间的距离设置阈值。如果发现距离低于指定阈值的向量则可以提前停止搜索假设进一步探索不太可能产生更好的结果。这与对节点以智能顺序访问的事实的限制相辅相成以避免遗漏可能相关的邻居。基于质量估计的动态提前终止一种更复杂的方法是根据每次搜索查询期间发现的结果的 “质量” 动态调整终止标准。如果搜索过程快速收敛到高质量邻居例如距离非常近的邻居算法可以提前终止即使没有达到预定义的阈值。
前两种策略属于 “固定配置” 提前终止策略类别即搜索根据固定约束条件终止而不考虑特定查询的复杂性。实际上并非所有查询的难度都是相同的。例如当向量分布不均衡时一些查询需要访问更多候选项。一些查询向量可能落入向量空间中的密集区域因此它们拥有更多的候选最近邻而另一些查询可能落入“稀疏区域”这使得找到其真正的最近邻更加困难。
由于这种情况能够适应向量空间密度从而适应 HNSW 图的连通性的提前终止策略似乎更适合实际场景。因此确定停止搜索每个查询的最佳点更有可能在不影响准确性的情况下大幅减少延迟。这种类型的提前终止策略被称为自适应策略因为它们会适应每个查询实例来决定何时终止搜索过程。
例如自适应提前终止策略可以利用机器学习模型来预测给定查询需要多少搜索工作才能达到所需的准确性。这样的模型会根据单个查询的特征和中间搜索结果动态调整要探索的图的范围。
说到中间搜索结果它们通常是进一步搜索的有力预测因素。如果初始结果已经接近查询则可能很快就会找到最近的邻居从而允许提前终止。相反较差的初始结果表明需要进行更广泛的探索参见本文。
Lucene 可以通过 KnnCollector 接口实现 HNSW 的提前终止该接口公开了 earlyTerminated() 方法但它还为 HNSW 提供了几个固定配置的提前终止策略
TimeLimitingKnnCollector 可以在达到特定时间阈值时停止 HNSW 图遍历。AbstractKnnCollector 是一个基本的 KnnCollector 实现一旦访问了固定数量的图节点它就会停止图遍历。
作为另一个示例为了实现基于距离阈值的终止我们可以依赖 Lucene 在 HNSW 遍历期间记录的最小竞争相似性用于确保只探索竞争节点并在其低于给定阈值时提前退出。
public class MCSEarlyExitCollector implements KnnCollector {private final KnnCollector delegate;private final double mcsThreshold;public MCSEarlyExitCollector(KnnCollector delegate, double mcsThreshold) {this.delegate delegate;this.mcsThreshold mcsThreshold;}Overridepublic boolean earlyTerminated() {return delegate.earlyTerminated() || minCompetitiveSimilarity() mcsThreshold;}...
} 结论
如果正确实施近似 KNN 的提前终止策略可以显著提高速度同时保持良好的准确性。固定策略更容易实施但它们可能需要更多调整并且在不同的查询中效果不佳。另一方面动态/自适应策略更难实施但具有能够更好地适应不同搜索查询的优势。
Elasticsearch 包含新功能可帮助你为你的用例构建最佳搜索解决方案。深入了解我们的示例笔记本以了解更多信息开始免费云试用或立即在你的本地机器上试用 Elastic。 原文Early termination in HNSW for faster approximate KNN search - Elasticsearch Labs