k-nearest neighbor (kNN) searchedit

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:

  • Relevance ranking based on natural language processing (NLP) algorithms
  • Product recommendations and recommendation engines
  • Similarity search for images or videos

Prerequisitesedit

  • To run a kNN search, you must be able to convert your data into meaningful vector values. You can create these vectors using a natural language processing (NLP) model in Elasticsearch, or generate them outside Elasticsearch. Vectors can be added to documents as dense_vector field values. Queries are represented as vectors with the same dimension.

    Design your vectors so that the closer a document’s vector is to a query vector, based on a similarity metric, the better its match.

  • To complete the steps in this guide, you must have the following index privileges:

    • create_index or manage to create an index with a dense_vector field
    • create, index, or write to add data to the index you created
    • read to search the index

kNN methodsedit

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.

Approximate kNNedit

Compared to other types of search, approximate kNN search has specific resource requirements. In particular, all vector data must fit in the node’s page cache for it to be efficient. Please consult the approximate kNN search tuning guide for important notes on configuration and sizing.

To run an approximate kNN search, use the knn option to search one or more dense_vector fields with indexing enabled.

  1. Explicitly map one or more dense_vector fields. Approximate kNN search requires the following mapping options:

    • An index value of true.
    • A similarity value. This value determines the similarity metric used to score documents based on similarity between the query and document vector. For a list of available metrics, see the similarity parameter documentation.
    PUT image-index
    {
      "mappings": {
        "properties": {
          "image-vector": {
            "type": "dense_vector",
            "dims": 3,
            "index": true,
            "similarity": "l2_norm"
          },
          "title-vector": {
            "type": "dense_vector",
            "dims": 5,
            "index": true,
            "similarity": "l2_norm"
          },
          "title": {
            "type": "text"
          },
          "file-type": {
            "type": "keyword"
          }
        }
      }
    }
  2. Index your data.

    POST image-index/_bulk?refresh=true
    { "index": { "_id": "1" } }
    { "image-vector": [1, 5, -20], "title-vector": [12, 50, -10, 0, 1], "title": "moose family", "file-type": "jpg" }
    { "index": { "_id": "2" } }
    { "image-vector": [42, 8, -15], "title-vector": [25, 1, 4, -12, 2], "title": "alpine lake", "file-type": "png" }
    { "index": { "_id": "3" } }
    { "image-vector": [15, 11, 23], "title-vector": [1, 5, 25, 50, 20], "title": "full moon", "file-type": "jpg" }
    ...
  3. Run the search using the knn option.

    POST image-index/_search
    {
      "knn": {
        "field": "image-vector",
        "query_vector": [-5, 9, -12],
        "k": 10,
        "num_candidates": 100
      },
      "fields": [ "title", "file-type" ]
    }

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.

Support for approximate kNN search was added in version 8.0. Before this, dense_vector fields did not support enabling index in the mapping. If you created an index prior to 8.0 containing dense_vector fields, then to support approximate kNN search the data must be reindexed using a new field mapping that sets index: true.

Tune approximate kNN for speed or accuracyedit

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.

Approximate kNN using byte vectorsedit

The approximate kNN search API supports byte value vectors in addition to float value vectors. Use the knn option to search a dense_vector field with element_type set to byte and indexing enabled.

  1. Explicitly map one or more dense_vector fields with element_type set to byte and indexing enabled.

    PUT byte-image-index
    {
      "mappings": {
        "properties": {
          "byte-image-vector": {
            "type": "dense_vector",
            "element_type": "byte",
            "dims": 2,
            "index": true,
            "similarity": "cosine"
          },
          "title": {
            "type": "text"
          }
        }
      }
    }
  2. Index your data ensuring all vector values are integers within the range [-128, 127].

    POST byte-image-index/_bulk?refresh=true
    { "index": { "_id": "1" } }
    { "byte-image-vector": [5, -20], "title": "moose family" }
    { "index": { "_id": "2" } }
    { "byte-image-vector": [8, -15], "title": "alpine lake" }
    { "index": { "_id": "3" } }
    { "byte-image-vector": [11, 23], "title": "full moon" }
  3. Run the search using the knn option ensuring the query_vector values are integers within the range [-128, 127].

    POST byte-image-index/_search
    {
      "knn": {
        "field": "byte-image-vector",
        "query_vector": [-5, 9],
        "k": 10,
        "num_candidates": 100
      },
      "fields": [ "title" ]
    }

Filtered kNN searchedit

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
}

The filter is applied during the approximate kNN search to ensure that k matching documents are returned. This contrasts with a post-filtering approach, where the filter is applied after the approximate kNN search completes. Post-filtering has the downside that it sometimes returns fewer than k results, even when there are enough matching documents.

Combine approximate kNN with other featuresedit

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.

Perform semantic searchedit

kNN search enables you to perform semantic search by using a previously deployed text embedding model. Instead of literal matching on search terms, semantic search retrieves results based on the intent and the contextual meaning of a search query.

Under the hood, the text embedding NLP model generates a dense vector from the input query string called model_text you provide. Then, it is searched against an index containing dense vectors created with the same text embedding machine learning model. The search results are semantically similar as learned by the model.

To perform semantic search:

  • you need an index that contains the dense vector representation of the input data to search against,
  • you must use the same text embedding model for search that you used to create the dense vectors from the input data,
  • the text embedding NLP model deployment must be started.

Reference the deployed text embedding model or the model deployment in the query_vector_builder object and provide the search query as model_text:

(...)
{
  "knn": {
    "field": "dense-vector-field",
    "k": 10,
    "num_candidates": 100,
    "query_vector_builder": {
      "text_embedding": { 
        "model_id": "my-text-embedding-model", 
        "model_text": "The opposite of blue" 
      }
    }
  }
}
(...)

The natural language processing task to perform. It must be text_embedding.

The ID of the text embedding model to use to generate the dense vectors from the query string. Use the same model that generated the embeddings from the input text in the index you search against. You can use the value of the deployment_id instead in the model_id argument.

The query string from which the model generates the dense vector representation.

For more information on how to deploy a trained model and use it to create text embeddings, refer to this end-to-end example.

Search multiple kNN fieldsedit

In addition to hybrid retrieval, you can search more than one kNN vector field at a time:

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
  },
  {
    "field": "title-vector",
    "query_vector": [1, 20, -52, 23, 10],
    "k": 10,
    "num_candidates": 10,
    "boost": 0.5
  }],
  "size": 10
}

This search finds the global top k = 5 vector matches for image-vector and the global k = 10 for the title-vector. These top values are then combined with the matches from the match query and the top-10 documents are returned. The multiple knn entries and the 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 scoring for a doc with the above configured boosts would be:

score = 0.9 * match_score + 0.1 * knn_score_image-vector + 0.5 * knn_score_title-vector

Search kNN with expected similarityedit

While kNN is a powerful tool, it always tries to return k nearest neighbors. Consequently, when using knn with a filter, you could filter out all relevant documents and only have irrelevant ones left to search. In that situation, knn will still do its best to return k nearest neighbors, even though those neighbors could be far away in the vector space.

To alleviate this worry, there is a similarity parameter available in the knn clause. This value is the required minimum similarity for a vector to be considered a match. The knn search flow with this parameter is as follows:

  • Apply any user provided filter queries
  • Explore the vector space to get k vectors
  • Do not return any vectors that are further away than the configured similarity

Here is an example. In this example we search for the given query_vector for k nearest neighbors. However, with filter applied and requiring that the found vectors have at least the provided similarity between them.

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

In our data set, the only document with the file type of png has a vector of [42, 8, -15]. The l2_norm distance between [42, 8, -15] and [1, 5, -20] is 41.412, which is greater than the configured similarity of 36. Meaning, this search will return no hits.

Indexing considerationsedit

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. The approximate kNN tuning guide contains important guidance around indexing performance, and how the index configuration can affect search performance.

In addition to its search-time tuning parameters, 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
        }
      }
    }
  }
}

Limitations for approximate kNN searchedit

  • You can’t run an approximate kNN search on a dense_vector field within a nested mapping.
  • When using kNN search in cross-cluster search, the ccs_minimize_roundtrips option is not supported.
  • Elasticsearch uses the HNSW algorithm to support efficient kNN search. Like most kNN algorithms, HNSW is an approximate method that sacrifices result accuracy for improved search speed. This means the results returned are not always the true k closest neighbors.

Approximate kNN search always uses the dfs_query_then_fetch search type in order to gather the global top k matches across shards. You cannot set the search_type explicitly when running kNN search.

Exact kNNedit

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

  1. Explicitly map one or more dense_vector fields. If you don’t intend to use the field for approximate kNN, omit the index mapping option or set it to false. This can significantly improve indexing speed.

    PUT product-index
    {
      "mappings": {
        "properties": {
          "product-vector": {
            "type": "dense_vector",
            "dims": 5,
            "index": false
          },
          "price": {
            "type": "long"
          }
        }
      }
    }
  2. Index your data.

    POST product-index/_bulk?refresh=true
    { "index": { "_id": "1" } }
    { "product-vector": [230.0, 300.33, -34.8988, 15.555, -200.0], "price": 1599 }
    { "index": { "_id": "2" } }
    { "product-vector": [-0.5, 100.0, -13.0, 14.8, -156.0], "price": 799 }
    { "index": { "_id": "3" } }
    { "product-vector": [0.5, 111.3, -13.0, 14.8, -156.0], "price": 1099 }
    ...
  3. Use the search API to run a script_score query containing a vector function.

    To limit the number of matched documents passed to the vector function, we recommend you specify a filter query in the script_score.query parameter. If needed, you can use a match_all query in this parameter to match all documents. However, matching all documents can significantly increase search latency.

    POST product-index/_search
    {
      "query": {
        "script_score": {
          "query" : {
            "bool" : {
              "filter" : {
                "range" : {
                  "price" : {
                    "gte": 1000
                  }
                }
              }
            }
          },
          "script": {
            "source": "cosineSimilarity(params.queryVector, 'product-vector') + 1.0",
            "params": {
              "queryVector": [-0.5, 90.0, -10, 14.8, -156.0]
            }
          }
        }
      }
    }