Elasticsearch：在 Elastic Stack 8.0 中引入近似最近邻搜索_elasticsearch ann

作者：Julie Tibshirani

由于新一代机器学习模型可以将各种内容表示为向量，包括文本、图像、事件等，人们对向量搜索的兴趣激增。 通常称为 “嵌入模型（embedding models）”，这些强大的表示可以以超越其表面特征的方式捕获两段内容之间的相似性。

k 最近邻 (kNN) 搜索算法在数据集中查找与查询向量最相似的向量。 与这些向量表示相结合，kNN 搜索为检索开辟了令人兴奋的可能性：

• 查找可能包含问题答案的段落
• 在大型数据集中检测近似重复的图像
• 查找听起来与给定歌曲相似的歌曲

向量搜索有望成为搜索工具箱的重要组成部分，与基于术语的评分等传统技术并驾齐驱。

Elasticsearch 目前支持通过 dense_vector 字段类型存储向量，并使用它们来计算文档分数。 这允许用户通过扫描所有文档来执行精确的 kNN 搜索。 Elasticsearch 8.0 基于此功能构建，以支持快速、近似的最近邻搜索 (ANN)。 这代表了一种更具可扩展性的方法，允许向量搜索在大型数据集上高效运行。

Elasticsearch 中的 ANN

什么是近似最近邻（Approximate Nearest Neighbor - ANN）搜索？

低维向量上的 kNN 有完善的数据结构，如 KD 树。 事实上，Elasticsearch 结合了 KD 树来支持对地理空间和数字数据的搜索。 但现代文本和图像嵌入模型通常会生成 100 - 1000 个元素或更多元素的高维向量。 这些向量表示提出了一个独特的挑战，因为很难有效地找到高维度的最近邻居。

面对这种困难，最近邻算法通常会牺牲完美的精度来提高速度。 这些近似最近邻 (ANN) 算法可能并不总是返回真正的 k 个最近向量。 但它们运行高效，在保持良好性能的同时扩展到大型数据集。

选择 ANN 算法

设计 ANN 算法是学术研究的一个活跃领域，有许多有前途的算法可供选择。 他们经常在搜索速度、实施复杂性和索引成本方面做出不同的权衡。 值得庆幸的是，有一个名为 ann-benchmarks 的伟大开源项目可以针对多个数据集测试领先的算法并发布比较结果。

Elasticsearch 8.0 使用称为分层导航小世界图 (Hierachical Navigable Small World graph - HNSW) 的 ANN 算法，该算法根据向量彼此的相似性将它们组织成图形。 HNSW 在各种 ann-benchmarks 数据集上显示出强大的搜索性能，并且在我们自己的测试中也表现出色。 HNSW 的另一个好处是它在工业中得到广泛应用，已在多个不同的系统中实现。 除了原始学术论文外，还有许多有助于了解算法细节的有用资源。 虽然 Elasticsearch ANN 目前是基于 HNSW 的，但该功能以灵活的方式设计，让我们在未来融合不同的方法。

给我看代码！

要为 ANN 搜索索引向量，我们需要设置 index: true 并指定我们用来比较它们的相似性度量：

PUT index
{
 "mappings": {
   "properties": {
     "image-vector": {
       "type": "dense_vector",
       "dims": 128,
       "index": true,
       "similarity": "l2_norm"
     }
   }
 }
}
 
 
PUT index/_doc
{
 "image-vector": [0.12, 1.34, ...]
}

然后，在添加向量之后，我们可以搜索查询向量的 k 个最近邻居：

GET index/_knn_search
{
 "knn": {
   "field": "image-vector",
   "query_vector": [-0.5, 9.4, ...],
   "k": 10,
   "num_candidates": 100
 }
}

新的 _knn_search 端点使用 HNSW 图来有效地检索相似的向量。 与执行完整数据扫描的精确 kNN 不同，它可以很好地扩展到大型数据集。 下面是一个示例，将 _knn_search 与基于 script_score 查询的精确方法进行比较，该数据集包含 100 万个具有 128 维的图像向量，平均超过 10,000 个不同的查询：

Approach         Queries Per Second    Recall (k=10)
script_score           5.257               1.000
_knn_search          849.286               0.945

有关 Recall 方面的知识点介绍，请参阅之前的文章 “Elasticsearch：理解搜索中的 precision 及 recall”。

在此示例中，ANN 搜索比精确方法快几个数量级。 它的 recall 约为 95%，因此平均而言，它会在 10 个真正的最近邻中找到超过 9 个。

你可以在 Elasticsearch 每晚基准测试中检查 kNN 搜索的性能。 这些基准测试由 es-rally 提供支持，es-rally 是 Elasticsearch 基准测试工具，特别是新的 dense_vector Rally track。 我们计划扩展 Rally 以报告除延迟之外的 Recall，因为跟踪算法的准确性也很重要。 目前，这些基准测试了包含几百万个向量的数据集，但 ANN 搜索肯定可以通过更长的索引时间或添加硬件资源来扩展到超出此范围。

因为它是一种近似算法，所以与其他类型的搜索相比，运行 ANN 有一些特殊的注意事项。 ANN 具有搜索时间和索引时间参数来控制搜索延迟、结果准确性和索引成本之间的权衡。 测量数据集上 ANN 搜索的 Recall 非常重要，以确保配置运行良好。 进入 kNN 搜索时，参考指南可能是一个很有帮助的起点。

由 Apache Lucene 提供支持

Elasticsearch 的许多核心搜索功能都由 Lucene 库提供支持，Lucene 库是一个由 Apache 软件基金会管理的开源项目。 Elasticsearch ANN 也不例外，它建立在一个令人兴奋的新 Lucene 功能之上，用于存储和搜索数字向量。 此功能是涉及不同组织的多个开发人员的良好协作的结果。 从一个大胆的提议开始，它迅速发展为一个可行的（并且快速的）实施。 然后是设计 API 和完善功能的挑战。

从那时起，Lucene 社区继续合作以推动该功能的发展。 一些开发人员对此感兴趣并做出了贡献，从重新设计名称到算法更新、性能改进等等。 在大家的努力下，Lucene 的向量搜索能力正在迅速扩展。

除了富有成效的合作，在 Lucene 中开发 ANN 还带来了其他主要好处。 Lucene 的实现是在低级别设计的，以便与现有功能正确集成，从而允许 ANN 搜索与其他 Elasticsearch 功能无缝交互。 如果我们依赖外部 ANN 库，那么这种深度集成实际上是不可能的。 例如，Lucene ANN 通过在图形搜索期间跳过 “墓碑” 来透明地处理已删除的文档。 它还尊重 Lucene 的所有数据兼容性保证，因此你可以确保向量数据在升级后仍然有效。 最后，Java 编写的实现就像 Elasticsearch 一样，这使我们能够确保其安全性并简化内存管理。

更多阅读：“Elastic：开发者上手指南” 中的 “NLP - 自然语言处理”。

原文：Introducing approximate nearest neighbor search in Elasticsearch 8.0 | Elastic Blog