聊聊ElasticSearch中的向量检索

简述

ElasticSearch中新增dense_vector type类型，支持向量数据的存储。 ES 向量搜索目前有两种方式:

script_score：精确搜索
_knn_search：近似搜索

对于script_score来说，其实就是暴力搜索，将查询向量与ES文档返回的向量数据集挨个匹配并打分；_knn_search则是基于KNN算法理论，结合相似性算法计算查询向量的K个近邻向量。

KNN 与 ANN

KNN算法理论是：对于一个未知类别的新数据点，在训练集中找到与它最接近的k个数据点，然后基于这k个“邻居”的类别来预测新数据点的类别。如果KNN用于回归任务，则预测值是这些邻居的属性的平均值。

距离计算有多种既定的算法，比如欧几里得距离，cos余弦值，点积等等；而这里的查询逻辑可以是精确查询也可以是近似查询。

而每种查询其内在依赖的算法不一样。对于精确查询，一般都是暴力搜索，即嵌套for循环。

对于近似查询，通过近似近邻算法（Approximate Nearest Neighbors，ANN）来实现；ANN算法是一种用于在高维数据空间中找到近似最近点的算法；

ANN是一个统称，其有多种不同的数据结构或算法组成，如下是常用常见的算法或数据结构：

树方法，如 KD-tree，Ball-tree，Annoy
哈希方法，如 Local Sensitive Hashing (LSH)
矢量量化方法，如 Product Quantization (PQ)
近邻图方法，如 Hierarchical Navigable Small World (HNSW)

因此总结来说，KNN的实现有两种，一种是精确查询，一种是近似查询。精确查询：多重嵌套循环，根据距离算法，精确地比对向量间的距离。近似查询：后者依赖于ANN中的某种特定的数据结构或算法组织数据集（可以理解为是索引过程），再根据距离算法，查找出近似近邻的向量返回。

ES的实现

Lucene 目前使用 hierarchical navigable small world (HNSW) 算法来索引向量，组织数据。

近似KNN查询默认基于此算法实现（Lucence暂时只支持HNSW 相似性算法）。其示例如下：

PUT my-index-knn
{
  "mappings": {
    "properties": {
      "my_vector": {
        "type": "dense_vector",
        "dims": 128,
        "index": true,
        "similarity": "dot_product"
      }
    }
  }
}

添加文档数据，进行索引：

POST my-approx-knn-index/_bulk?refresh=true
{ "index": { "_id": "1" } }
{ "my_vector": [230.0, 300.33, -34.8988, 15.555, -200.0]}
{ "index": { "_id": "2" } }
{ "my_vector": [-0.5, 100.0, -13.0, 14.8, -156.0]}
{ "index": { "_id": "3" } }
{ "my_vector": [0.5, 111.3, -13.0, 14.8, -156.0]}

通过API_knn_search执行KNN搜索：

GET my-index-knn/_knn_search
{
  "knn": {
    "field": "my_vector",
    "query_vector": [0.3, 0.1, 1.2, ...],
    "k": 10,
    "num_candidates": 100
  },
  "_source": ["name", "date"]
}