k-nearest neighbor (kNN) search

A k-nearest neighbor (kNN) search finds the k nearest vectors to a query vector, as measured by a similarity metric.

Common use cases for kNN include:

Elasticsearch supports two methods for kNN search:

In most cases, you’ll want to use approximate kNN. Approximate kNN offers lower latency at the cost of slower indexing and imperfect accuracy.

Exact, brute-force kNN guarantees accurate results but doesn’t scale well with large datasets. With this approach, a script_score query must scan each matching document to compute the vector function, which can result in slow search speeds. However, you can improve latency by using a query to limit the number of matching documents passed to the function. If you filter your data to a small subset of documents, you can get good search performance using this approach.

To run an exact kNN search, use a script_score query with a vector function.

To run an approximate kNN search, use the knn option to search a dense_vector field with indexing enabled.

The document _score is determined by the similarity between the query and document vector. See similarity for more information on how kNN search scores are computed.

To gather results, the kNN search API finds a num_candidates number of approximate nearest neighbor candidates on each shard. The search computes the similarity of these candidate vectors to the query vector, selecting the k most similar results from each shard. The search then merges the results from each shard to return the global top k nearest neighbors.

You can increase num_candidates for more accurate results at the cost of slower search speeds. A search with a high value for num_candidates considers more candidates from each shard. This takes more time, but the search has a higher probability of finding the true k top nearest neighbors.

Similarly, you can decrease num_candidates for faster searches with potentially less accurate results.

The kNN search API supports restricting the search using a filter. The search will return the top k documents that also match the filter query.

The following request performs an approximate kNN search filtered by the file-type field:

POST image-index/_search
{
  "knn": {
    "field": "image-vector",
    "query_vector": [54, 10, -2],
    "k": 5,
    "num_candidates": 50,
    "filter": {
      "term": {
        "file-type": "png"
      }
    }
  },
  "fields": ["title"],
  "_source": false
}

Unlike conventional query filtering, where more restrictive filters typically lead to faster queries, applying filters in an approximate kNN search with an HNSW index can decrease performance. This is because searching the HNSW graph requires additional exploration to obtain the num_candidates that meet the filter criteria.

To avoid significant performance drawbacks, Lucene implements the following strategies per segment:

You can perform hybrid retrieval by providing both the knn option and a query:

POST image-index/_search
{
  "query": {
    "match": {
      "title": {
        "query": "mountain lake",
        "boost": 0.9
      }
    }
  },
  "knn": {
    "field": "image-vector",
    "query_vector": [54, 10, -2],
    "k": 5,
    "num_candidates": 50,
    "boost": 0.1
  },
  "size": 10
}

This search finds the global top k = 5 vector matches, combines them with the matches from the match query, and finally returns the 10 top-scoring results. The knn and query matches are combined through a disjunction, as if you took a boolean or between them. The top k vector results represent the global nearest neighbors across all index shards.

The score of each hit is the sum of the knn and query scores. You can specify a boost value to give a weight to each score in the sum. In the example above, the scores will be calculated as

score = 0.9 * match_score + 0.1 * knn_score

The knn option can also be used with aggregations. In general, Elasticsearch computes aggregations over all documents that match the search. So for approximate kNN search, aggregations are calculated on the top k nearest documents. If the search also includes a query, then aggregations are calculated on the combined set of knn and query matches.

Elasticsearch shards are composed of segments, which are internal storage elements in the index. For approximate kNN search, Elasticsearch stores the dense vector values of each segment as an HNSW graph. Indexing vectors for approximate kNN search can take substantial time because of how expensive it is to build these graphs. You may need to increase the client request timeout for index and bulk requests.

Force merging the index to a single segment can improve kNN search latency. With only one segment, the search needs to check a single, all-inclusive HNSW graph. When there are multiple segments, kNN search must check several smaller HNSW graphs as it searches each segment after another. You should only force merge an index if it is no longer being written to.

The HNSW algorithm has index-time parameters that trade off between the cost of building the graph, search speed, and accuracy. When setting up the dense_vector mapping, you can use the index_options argument to adjust these parameters:

PUT image-index
{
  "mappings": {
    "properties": {
      "image-vector": {
        "type": "dense_vector",
        "dims": 3,
        "index": true,
        "similarity": "l2_norm",
        "index_options": {
          "type": "hnsw",
          "m": 32,
          "ef_construction": 100
        }
      }
    }
  }
}