Elasticsearch: kNN Methods

Elasticsearch의 두 가지 kNN 검색 방법:

• Approximate kNN:
  • 낮은 지연 시간을 제공하지만, 인덱싱이 느리고 완벽한 정확도를 보장하지 않음.
• brute-force kNN:
  • 정확한 결과를 보장하지만, 대규모 데이터셋에서는 확장성이 떨어짐.

 

사용 시 고려사항:

• 데이터셋의 크기
• 요구되는 정확도 수준
• 허용 가능한 검색 지연 시간
• 인덱싱 속도의 중요성

 

브루트 포스 kNN의 활용도 중요하다:

• 데이터를 작은 부분집합으로 필터링할 수 있는 경우, 이 방법으로도 좋은 검색 성능을 얻을 수 있음.

 

 

Approximate kNN:

리소스 요구사항:

• 근사 kNN 검색은 특별한 리소스 요구사항이 있음.
• 모든 벡터 데이터가 노드의 페이지 캐시에 맞아야 효율적이다.
• 구성 및 크기 조정에 대한 튜닝 가이드를 참조하는 것 중요.

 

kNN 쿼리 실행:

• 'knn' 옵션을 사용하여 검색을 실행할 수 있다.
• 검색 파라미터로는 field, query_vector, k, num_candidates 등이 있음.
• 문서의 _score는 쿼리 벡터와 문서 벡터 간의 유사도에 의해 결정된다.

PUT image-index
{
  "mappings": {
    "properties": {
      "image-vector": {
        "type": "dense_vector",
        "dims": 3,
        "similarity": "l2_norm"
      },
      "title-vector": {
        "type": "dense_vector",
        "dims": 5,
        "similarity": "l2_norm"
      },
      "title": {
        "type": "text"
      },
      "file-type": {
        "type": "keyword"
      }
    }
  }
}

// 보면 알겠지만 query 도 vector 로 변환을 해줘야함. 
POST image-index/_search
{
  "knn": {
    "field": "image-vector",
    "query_vector": [-5, 9, -12],
    "k": 10,
    "num_candidates": 100
  },
  "fields": [ "title", "file-type" ]
}

 

 

버전 호환성:

• 근사 kNN 검색 지원은 Elasticsearch 8.0 버전에서 추가되었음.
• 8.0 이전 버전에서 생성된 인덱스의 경우, 근사 kNN 검색을 지원하려면 index: true 옵션으로 데이터를 재인덱싱해야 한다.

 

kNN 검색 과정:

• 각 샤드에서 'num_candidates' 수만큼의 근사 최근접 이웃 후보를 찾는다.
• 이 후보 벡터들과 쿼리 벡터 간의 유사도를 계산한다.
• 각 샤드에서 가장 유사한 k개의 결과를 선택한다.
• 모든 샤드의 결과를 병합하여 전체 상위 k개의 최근접 이웃을 반환한다.

 

num_candidates 파라미터의 역할:

• 이 파라미터는 정확도와 검색 속도 사이의 균형을 조절한다.

 

num_candidates 값 증가:

• 장점: 더 정확한 결과를 얻을 수 있습니다.
• 단점: 검색 속도가 느려집니다.
• 이유: 각 샤드에서 더 많은 후보를 고려하므로, 진정한 상위 k개 최근접 이웃을 찾을 확률이 높아집니다.

 

num_candidates 값 감소:

• 장점: 검색 속도가 빨라집니다.
• 단점: 결과의 정확도가 떨어질 수 있습니다.
• 이유: 각 샤드에서 고려하는 후보 수가 줄어들어 처리 시간이 단축됩니다.

 

 

 

Approximate kNN using byte vectors

바이트 벡터 지원:

• 근사 kNN 검색 API는 float 값 벡터 외에도 바이트 값 벡터를 지원합니다.
• dense_vector 필드에 element_type을 'byte'로 설정하고 인덱싱을 활성화해야 합니다.

PUT byte-image-index
{
  "mappings": {
    "properties": {
      "byte-image-vector": {
        "type": "dense_vector",
        "element_type": "byte",
        "dims": 2
      },
      "title": {
        "type": "text"
      }
    }
  }
}

 

 

데이터 인덱싱:

• 모든 벡터 값은 -128에서 127 사이의 정수여야 합니다.

 

주요 포인트:

• 바이트 벡터는 float 벡터에 비해 메모리 사용량을 줄일 수 있습니다.
• 값의 범위가 제한되어 있으므로(-128에서 127), 이 범위 내에서 데이터를 적절히 정규화해야 합니다.

 

 

 

Byte quantized kNN search

바이트 양자화의 목적:

• float 벡터를 제공하면서도 바이트 벡터의 메모리 절약 효과를 얻을 수 있습니다.
• float 벡터를 내부적으로 바이트 벡터로 인덱싱하지만, 원본 float 벡터도 인덱스에 유지합니다.

 

기본 인덱스 타입:

• dense_vector의 기본 인덱스 타입은 'int8_hnsw'입니다.

 

인덱스 매핑:

• dense_vector 필드에 'int8_hnsw' 인덱스 타입을 지정합니다.
• element_type은 'float'으로 설정합니다.

PUT quantized-image-index
{
  "mappings": {
    "properties": {
      "image-vector": {
        "type": "dense_vector",
        "element_type": "float",
        "dims": 2,
        "index": true,
        "index_options": {
          "type": "int8_hnsw"
        }
      },
      "title": {
        "type": "text"
      }
    }
  }
}

 

 

'knn' 옵션을 사용하여 검색을 실행할 때 float 벡터가 자동으로 바이트 벡터로 양자화됩니다.

POST quantized-image-index/_search
{
  "knn": {
    "field": "image-vector",
    "query_vector": [0.1, -2],
    "k": 10,
    "num_candidates": 100
  },
  "fields": [ "title" ]
}

 

 

재점수화(Rescoring):

• 원본 float 벡터를 사용하여 상위 결과의 점수를 재계산할 수 있습니다.
• 상위 k개 결과에 대해서만 원본 float 벡터를 사용하여 재점수화합니다.
• 이를 통해 빠른 검색과 정확한 점수 계산의 장점을 모두 얻을 수 있습니다.

POST quantized-image-index/_search
{
  "knn": {
    "field": "image-vector",
    "query_vector": [0.1, -2],
    "k": 15,
    "num_candidates": 100
  },
  "fields": [ "title" ],
  "rescore": {
    "window_size": 10,
    "query": {
      "rescore_query": {
        "script_score": {
          "query": {
            "match_all": {}
          },
          "script": {
            "source": "cosineSimilarity(params.query_vector, 'image-vector') + 1.0",
            "params": {
              "query_vector": [0.1, -2]
            }
          }
        }
      }
    }
  }
}

 

 

Filtered kNN search

필터링된 kNN 검색:

• kNN 검색 API는 필터를 사용하여 검색 범위를 제한할 수 있습니다.
• 검색은 필터 쿼리와 일치하는 문서 중에서 상위 k개의 문서를 반환합니다.

 

검색 요청 예시:

• 'image-vector' 필드에 대해 근사 kNN 검색을 수행합니다.
• 'file-type' 필드를 기준으로 필터링합니다 (이 예에서는 'png' 파일만 검색).

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
}

 

 

필터 적용 방식:

• 필터는 근사 kNN 검색 중에 적용됩니다.
• 이는 k개의 일치하는 문서를 확실히 반환하기 위함입니다.

 

후처리 필터링과의 차이:

• 후처리 필터링은 kNN 검색 완료 후 필터를 적용합니다.
• 후처리 필터링의 단점: 충분한 일치 문서가 있어도 k개 미만의 결과를 반환할 수 있습니다.

 

주의사항:

• 필터가 너무 제한적이면 k개의 결과를 찾지 못할 수 있습니다.
• num_candidates 값을 적절히 설정하여 검색의 정확성과 속도를 조절해야 합니다.

 

 

Approximate kNN search and filtering

일반적인 쿼리와 필터링 쿼리와의 차이:

• ES 에서는 일반적인 쿼리에서는 더 제한적인 필터가 보통 더 빠른 쿼리 실행을 의미합니다.
• 그러나 HNSW 인덱스를 사용한 근사 kNN 검색에서는 필터 적용이 오히려 성능을 저하시킬 수 있습니다.

 

성능 저하의 이유:

• HNSW 그래프 검색 시 필터 기준을 만족하는 num_candidates를 얻기 위해 추가적인 탐색이 필요합니다.
• 추가적인 오버헤드가 있는거지. 일반적인 필터는 탐색 범위를 줄이고 가는 반면에 여기서는 HNSW 탐색 하면서 필터를 적용하다보니까.

 

Lucene의 성능 최적화 전략:

• Lucene은 세그먼트 별로 다음 전략을 구현하여 성능 저하를 방지합니다:
  • 필터링된 문서 수가 num_candidates 이하인 경우:
    • HNSW 그래프 검색을 우회해서, 필터링된 문서에 대해 브루트 포스 검색을 수행합니다.
    • HNSW 그래프 탐색 중 특정 조건 만족 시:
    • 탐색된 노드 수가 필터를 만족하는 문서 수를 초과하면, 그래프 탐색을 중단하고 필터링된 문서에 대해 브루트 포스 검색으로 전환합니다.

 

필터링 + HNSW 그래프 검색 매커니즘:

• 필터링으로 통과한 문서의 집합을 구함.
• num_candidated 수만큼을 구하기 위해서 HNSW 인덱스를 타서 검색을 함. 여기서 마지막 노드가 필터링을 통과하지 못한다면 추가 탐색이 계속적으로 발생할 수 있음. 그래서 필터링이 성능 저하를 일으킴.

 

Lucene 성능 최적화 해석:

• num_candidated 만큼 최소 HNSW 탐색이 이뤄지기 때문에, 필터링 된 문서가 num_candidated 보다 이하라면 브루트 포스 접근을 하는것.
• 필터링된 문서의 수만큼 브루트 포스를 하게 되면 최대 시간 복잡도는 계산할 수 있음. 근데 num_candidate 가 필터링 문서보다 작다면 HNSW 탐색으로 더 빠르게 찾아낼 수도 있는 가능성이 있음. 근데 이게 필터링된 문서 수보다 많이 탐색을 해야한다면 그냥 브루트 포스 접근이 나은 것이었으니 이 방식으로 하는 것.

 

사용 시 고려사항:

• num_candidates 값을 적절히 설정하는 것이 중요합니다.
• 필터의 선택성을 고려하여 쿼리를 설계해야 합니다.
• 대규모 데이터셋에서는 필터링과 kNN 검색의 균형을 잘 맞추어야 합니다.

 

 

Combine approximate kNN with other features

하이브리드 검색:

• kNN 옵션과 일반 쿼리를 함께 사용하여 하이브리드 검색을 수행할 수 있습니다.

 

예시 쿼리:

• 텍스트 매치 쿼리("mountain lake")와 벡터 kNN 검색을 결합합니다.
• 각 부분에 boost 값을 적용하여 가중치를 조절합니다.

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
}

 

 

결과 결합 방식:

• kNN 결과와 쿼리 결과는 disjunction(OR) 방식으로 결합됩니다.

 

점수 계산:

• 각 히트의 점수는 kNN 점수와 쿼리 점수의 가중 합으로 계산됩니다.
• 예: score = 0.9 * match_score + 0.1 * knn_score

 

 

Perform semantic search

의미론적 검색의 개념:

• 검색어의 문자 그대로의 일치가 아닌, 검색 쿼리의 의도와 문맥적 의미에 기반하여 결과를 검색합니다.

 

작동 원리:

• 사전에 배포된 텍스트 임베딩 모델을 사용합니다.
• 입력 쿼리 문자열을 밀집 벡터(dense vector)로 변환합니다.
• 이 벡터를 동일한 모델로 생성된 밀집 벡터가 저장된 인덱스에 대해 검색합니다.

 

의미론적 검색 수행을 위한 요구사항:

• 검색 대상 데이터의 밀집 벡터 표현이 포함된 인덱스가 필요합니다.
• 검색에 사용하는 텍스트 임베딩 모델은 입력 데이터의 벡터 생성에 사용한 모델과 동일해야 합니다.
• 텍스트 임베딩 NLP 모델 배포가 시작되어 있어야 합니다.

 

쿼리 구조:

• query_vector_builder 객체를 사용하여 배포된 텍스트 임베딩 모델을 참조합니다.
• 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" 
      }
    }
  }
}

 

 

추가 정보:

• 훈련된 모델을 배포하고 텍스트 임베딩을 생성하는 방법에 대한 자세한 정보는 별도의 예제를 참조
• https://www.elastic.co/guide/en/machine-learning/8.14/ml-nlp-text-emb-vector-search-example.html

 

 

Search multiple kNN fields

여러 kNN(k-Nearest Neighbors) 벡터 필드를 동시에 검색하는 방법

 

다중 kNN 필드 검색:

• 하나 이상의 kNN 벡터 필드를 동시에 검색할 수 있습니다.
• 이는 하이브리드 검색의 확장된 형태입니다.

 

예시 쿼리 구조:

• 텍스트 매치 쿼리("mountain lake")
• 두 개의 kNN 검색 (image-vector와 title-vector)
• 각 부분에 대한 boost 값 지정

 

결과 결합 방식:

• 여러 kNN 엔트리와 쿼리 매치는 disjunction(OR) 방식으로 결합됩니다.
• 각 벡터 필드의 상위 k 결과는 모든 인덱스 샤드에 걸친 전역 최근접 이웃을 나타냅니다.

 

점수 계산:

• 각 문서의 점수는 텍스트 매치 점수와 각 kNN 검색의 점수를 가중 합산하여 계산됩니다.
• 예시: score = 0.9 * match_score + 0.1 * knn_score_image-vector + 0.5 * knn_score_title-vector

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
}

 

 

주요 이점:

• 다양한 유형의 벡터 데이터를 동시에 고려할 수 있습니다.
• 텍스트 기반 검색과 여러 벡터 기반 검색을 결합하여 더 풍부한 검색 결과를 제공합니다.
• 각 검색 구성요소에 대한 가중치(boost)를 조정하여 검색 결과의 우선순위를 세밀하게 제어할 수 있습니다.

 

 

Search kNN with expected similarity

Elasticsearch의 kNN(k-Nearest Neighbors) 검색에서 기대 유사도(expected similarity)를 사용하는 방법에 대해 설명

 

kNN의 한계점:

• kNN은 항상 k개의 최근접 이웃을 반환하려고 합니다.
• 필터와 함께 사용할 때, 관련 없는 문서만 남을 수 있습니다.

 

similarity 파라미터:

• kNN 절에서 사용 가능한 새로운 파라미터입니다.
• 벡터가 매치로 간주되기 위한 최소 유사도를 지정합니다.

 

similarity를 사용한 kNN 검색 흐름:

• 사용자가 제공한 필터 쿼리 적용
• 벡터 공간에서 k개의 벡터 탐색
• 구성된 similarity보다 멀리 있는 벡터는 반환하지 않음

 

similarity와 _score의 관계:

• similarity는 _score로 변환되기 전의 실제 유사도입니다.
• 각 유사도 메트릭에 대한 _score 변환 공식이 제공됩니다.
  • l2_norm: sqrt((1 / _score) - 1)
  • cosine: (2 * _score) - 1
  • dot_product: (2 * _score) - 1
  • max_inner_product:
    • _score < 1: 1 - (1 / _score)
    • _score >= 1: _score - 1

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
}

 

 

주요 이점:

• 관련성 없는 결과를 효과적으로 필터링할 수 있습니다.
• 유사도에 기반한 더 정확한 검색 결과를 얻을 수 있습니다.

 

사용 시 고려사항:

• similarity 값을 적절히 설정하는 것이 중요합니다. (유사도 메트릭도 추가로 고려해야함.)
• 데이터의 특성과 벡터 공간의 분포를 이해해야 합니다.
• 필터와 similarity를 함께 사용할 때 검색 결과가 없을 수 있음을 인지해야 합니다.

 

 

Nested kNN Search

텍스트 청킹(Chunking)의 필요성:

• 텍스트가 특정 모델의 토큰 제한을 초과할 때 청킹이 필요합니다.
• 개별 청크에 대한 임베딩을 생성해야 합니다.

 

기존에 텍스트 청킹 방법:

• 청킹 텍스트에다가 메타 데이터로 상위 문서를 포함시켰음. 그래서 저장 비용이 두 배로 든다.

 

ES 에서는 Nested 와 Dense Vector 의 결합으로 데이터를 저장할 수 있음.

• 문서 내용 전체를 인덱싱하고, 청킹 부분 (Nested, paragraph) 부분만 각각 저장하면 됨.

 

다음과 같이 매핑을 만들어야한다.

• 'passage_vectors' 인덱스를 생성합니다.
• 'full_text', 'creation_time'과 같은 상위 레벨 필드를 포함합니다.
• 'paragraph'라는 nested 타입 필드를 정의합니다.
• 'vector': dense_vector 타입, HNSW 인덱스 옵션 사용
• 'text': 텍스트 필드, 인덱싱되지 않음

PUT passage_vectors
{
    "mappings": {
        "properties": {
            "full_text": {
                "type": "text"
            },
            "creation_time": {
                "type": "date"
            },
            "paragraph": {
                "type": "nested",
                "properties": {
                    "vector": {
                        "type": "dense_vector",
                        "dims": 2,
                        "index_options": {
                            "type": "hnsw"
                        }
                    },
                    "text": {
                        "type": "text",
                        "index": false
                    }
                }
            }
        }
    }
}

 

 

색인도 다음 방법처럼 벌크로 하면 됨.

POST passage_vectors/_bulk?refresh=true
{ "index": { "_id": "1" } }
{ "full_text": "first paragraph another paragraph", "creation_time": "2019-05-04", "paragraph": [ { "vector": [ 0.45, 45 ], "text": "first paragraph", "paragraph_id": "1" }, { "vector": [ 0.8, 0.6 ], "text": "another paragraph", "paragraph_id": "2" } ] }
{ "index": { "_id": "2" } }
{ "full_text": "number one paragraph number two paragraph", "creation_time": "2020-05-04", "paragraph": [ { "vector": [ 1.2, 4.5 ], "text": "number one paragraph", "paragraph_id": "1" }, { "vector": [ -1, 42 ], "text": "number two paragraph", "paragraph_id": "2" } ] }

 

 

검색 방법:

POST passage_vectors/_search
{
    "fields": ["full_text", "creation_time"],
    "_source": false,
    "knn": {
        "query_vector": [
            0.45,
            45
        ],
        "field": "paragraph.vector",
        "k": 2,
        "num_candidates": 2
    }
}

 

 

검색 결과의 특징:

• 총 4개의 벡터가 있지만, 2개의 문서만 반환됩니다.
• Nested dense_vectors에 대한 kNN 검색은 항상 상위 레벨 문서에 대해 결과를 다양화합니다.
• 'k'개의 상위 레벨 문서가 반환되며, 각 문서는 가장 가까운 패시지 벡터에 의해 점수가 매겨집니다.

{
    "took": 4,
    "timed_out": false,
    "_shards": {
        "total": 1,
        "successful": 1,
        "skipped": 0,
        "failed": 0
    },
    "hits": {
        "total": {
            "value": 2,
            "relation": "eq"
        },
        "max_score": 1.0,
        "hits": [
            {
                "_index": "passage_vectors",
                "_id": "1",
                "_score": 1.0,
                "fields": {
                    "creation_time": [
                        "2019-05-04T00:00:00.000Z"
                    ],
                    "full_text": [
                        "first paragraph another paragraph"
                    ]
                }
            },
            {
                "_index": "passage_vectors",
                "_id": "2",
                "_score": 0.9997144,
                "fields": {
                    "creation_time": [
                        "2020-05-04T00:00:00.000Z"
                    ],
                    "full_text": [
                        "number one paragraph number two paragraph"
                    ]
                }
            }
        ]
    }
}

 

 

Nested kNN Search with Inner hits

Nested Search 에서 Inner Hits 를 이용하는 법을 다룸.

 

Inner Hits:

• 매치된 문서에서 가장 가까운 패시지(passage)를 추출하기 위해 사용됩니다.

 

Inner Hits 사용 방법:

• kNN 절에 inner_hits를 추가하여 사용합니다.

 

장점:

• 문서 전체가 아닌 가장 관련 있는 패시지를 정확히 식별할 수 있습니다.
• 긴 문서에서 특정 부분을 효과적으로 검색하고 추출할 수 있습니다.
• 상위 레벨 문서 컨텍스트와 함께 세부적인 매치 정보를 얻을 수 있습니다.

 

검색 예시 inner_hits:

• _source: false로 설정하여 nested 객체의 원본을 반환하지 않습니다.
• fields: 반환할 nested 필드를 지정합니다 ("paragraph.text").
• size: 각 문서당 반환할 inner hit의 수를 지정합니다 (여기서는 1).

POST passage_vectors/_search
{
    "fields": [
        "creation_time",
        "full_text"
    ],
    "_source": false,
    "knn": {
        "query_vector": [
            0.45,
            45
        ],
        "field": "paragraph.vector",
        "k": 2,
        "num_candidates": 2,
        "inner_hits": {
            "_source": false,
            "fields": [
                "paragraph.text"
            ],
            "size": 1
        }
    }
}

 

 

Inner hits 검색 결과:

{
    "took": 4,
    "timed_out": false,
    "_shards": {
        "total": 1,
        "successful": 1,
        "skipped": 0,
        "failed": 0
    },
    "hits": {
        "total": {
            "value": 2,
            "relation": "eq"
        },
        "max_score": 1.0,
        "hits": [
            {
                "_index": "passage_vectors",
                "_id": "1",
                "_score": 1.0,
                "fields": {
                    "creation_time": [
                        "2019-05-04T00:00:00.000Z"
                    ],
                    "full_text": [
                        "first paragraph another paragraph"
                    ]
                },
                "inner_hits": {
                    "paragraph": {
                        "hits": {
                            "total": {
                                "value": 2,
                                "relation": "eq"
                            },
                            "max_score": 1.0,
                            "hits": [
                                {
                                    "_index": "passage_vectors",
                                    "_id": "1",
                                    "_nested": {
                                        "field": "paragraph",
                                        "offset": 0
                                    },
                                    "_score": 1.0,
                                    "fields": {
                                        "paragraph": [
                                            {
                                                "text": [
                                                    "first paragraph"
                                                ]
                                            }
                                        ]
                                    }
                                }
                            ]
                        }
                    }
                }
            },
            {
                "_index": "passage_vectors",
                "_id": "2",
                "_score": 0.9997144,
                "fields": {
                    "creation_time": [
                        "2020-05-04T00:00:00.000Z"
                    ],
                    "full_text": [
                        "number one paragraph number two paragraph"
                    ]
                },
                "inner_hits": {
                    "paragraph": {
                        "hits": {
                            "total": {
                                "value": 2,
                                "relation": "eq"
                            },
                            "max_score": 0.9997144,
                            "hits": [
                                {
                                    "_index": "passage_vectors",
                                    "_id": "2",
                                    "_nested": {
                                        "field": "paragraph",
                                        "offset": 1
                                    },
                                    "_score": 0.9997144,
                                    "fields": {
                                        "paragraph": [
                                            {
                                                "text": [
                                                    "number two paragraph"
                                                ]
                                            }
                                        ]
                                    }
                                }
                            ]
                        }
                    }
                }
            }
        ]
    }
}

 

 

Indexing considerations

근사 kNN(k-Nearest Neighbors) 검색을 위한 인덱싱 고려사항에 대해 다룸.

 

HNSW 그래프 저장:

• Elasticsearch는 각 세그먼트의 dense vector 값을 HNSW(Hierarchical Navigable Small World) 그래프로 저장합니다.

 

인덱싱 시간:

• 근사 kNN 검색을 위한 벡터 인덱싱은 상당한 시간이 소요될 수 있습니다.
• HNSW 그래프 구축이 계산 비용이 높기 때문입니다.

 

클라이언트 요청 타임아웃:

• 인덱스 및 벌크 요청에 대한 클라이언트 요청 타임아웃을 증가시켜야 할 수 있습니다.

 

성능 튜닝 가이드:

• 인덱싱 성능과 검색 성능에 영향을 미치는 인덱스 구성에 대한 중요한 지침이 있습니다.
• 참고: https://www.elastic.co/guide/en/elasticsearch/reference/current/tune-knn-search.html

 

HNSW 알고리즘 파라미터:

• 검색 시간 튜닝 파라미터 외에도 인덱스 시간 파라미터가 있습니다.
• 이 파라미터들은 그래프 구축 비용, 검색 속도, 정확도 사이의 균형을 조절합니다.

 

index_options 설정:

• dense_vector 매핑 설정 시 index_options 인자를 사용하여 이러한 파라미터를 조정할 수 있습니다.
• type: HNSW 알고리즘 사용을 지정
• m: 그래프의 각 노드가 가질 수 있는 최대 연결 수 (높을수록 더 정확하지만 인덱싱이 느려짐) (기본값은 16)
• ef_construction: 그래프에 새로운 노드를 추가할 때 고려해야하는 후보 노드의 수임. (높을수록 더 정확하지만 인덱싱이 느려짐) (기본값은 100)

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

 

 

Limitations for approximate kNN search

근사 kNN(k-Nearest Neighbors) 검색의 제한사항에 대해 다룸.

 

크로스 클러스터 검색 제한:

• kNN 검색을 크로스 클러스터 검색에서 사용할 때, 'ccs_minimize_roundtrips' 옵션은 지원되지 않습니다.
• 이는 크로스 클러스터 검색 최적화의 일부 기능이 kNN 검색과 호환되지 않음을 의미합니다.

 

HNSW 알고리즘의 특성:

• Elasticsearch는 효율적인 kNN 검색을 위해 HNSW(Hierarchical Navigable Small World) 알고리즘을 사용합니다.
• HNSW는 근사 방법으로, 대부분의 kNN 알고리즘과 마찬가지로 결과의 정확성을 일부 희생하여 검색 속도를 향상시킵니다.
• 이는 반환된 결과가 항상 진정한 k개의 가장 가까운 이웃이 아닐 수 있음을 의미합니다.

 

 

Exact kNN

여기서는 Elasticsearch에서 정확한 kNN(k-Nearest Neighbors) 검색을 수행하는 방법을 다룸. 이전까지는 근사 kNN 에 대해 다루었다면.

 

 

정확한 kNN 검색 방법:

• script_score 쿼리와 벡터 함수를 사용합니다.

 

인덱스 매핑:

• dense_vector 필드를 명시적으로 매핑합니다.
• 근사 kNN을 사용하지 않을 경우, index 옵션을 false로 설정하여 인덱싱 속도를 향상시킵니다.

PUT product-index
{
  "mappings": {
    "properties": {
      "product-vector": {
        "type": "dense_vector",
        "dims": 5,
        "index": false
      },
      "price": {
        "type": "long"
      }
    }
  }
}

 

 

검색 쿼리 구조:

• script_score 쿼리를 사용합니다.
• 벡터 함수(여기서는 cosineSimilarity)를 스크립트에 포함시킵니다.

 

성능 최적화:

• filter 쿼리를 사용하여 벡터 함수에 전달되는 문서 수를 제한합니다.
• 모든 문서를 매치하는 것은 검색 지연 시간을 크게 증가시킬 수 있습니다.

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]
        }
      }
    }
  }

 

 

주요 특징:

• 정확성: 근사 방법과 달리 정확한 kNN 결과를 제공합니다.
• 유연성: 다양한 벡터 함수와 필터링 조건을 조합할 수 있습니다.
• 성능 고려: 대규모 데이터셋에서는 느릴 수 있으므로 적절한 필터링이 중요합니다.

 

 

References:

• https://www.elastic.co/guide/en/elasticsearch/reference/current/knn-search.html#knn-semantic-search