Elasticsearch - Dense vector field type

개요

유사도 검색은(similarity search) 사용자가 입렵한 데이터에(문서, 이미지, ...) 대하여 가장 유사한 순서로 문서를 조회하여 정렬하는 검색 방식이다.

kNN검색은 Elasticsearch 8.x 부터 제공한다.

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

k-nearest neighbor (kNN) search | Elasticsearch Guide [8.13] | Elastic

 

kNN(k-nearest neighbot)

머신러닝에서 데이터를 가장 가까운 유사 속성에 따라 분류하여 데이터를 분류하는 기법은으로 분류(Classification) 알고리즘이다.

• 자연어 처리(NLP) 알고리즘 기반 관련성 순위 
• 제품 추천 및 추천 엔진
• 이미지, 동영상의 유사성 검색 

유사성 메트릭으로 측정된 쿼리 벡터에 가장 가까운 k개의 벡터를 찾는다.

거리를 측정하기 위해서는 유클리드 거리를(Eunclidean distance) 사용한다.

 

장점	단점
단순하고 효율적이다 기저 데이터 분포에 대한 가정을 하지 않는다. 훈련 단계가 빠르다 수치 기반 데이터 분류 작업에서 서능이 우수하다.	모델을 새성하지 않아 특징과 클래스간 관계를 이해하는데 제한적이다. 적절한 k의 선택이 필요하다. 데이터가 많아지만 분류 단계가 느리다 명목 특징 및 누락 데이터를 위한 추가 처리가 필요하다.

 

Elasticsearch kNN 이미지 검색 기술 검토

kNN 검색을 위해서는 데이터를 의미있는 벡터값으로 변환하여 dense_vector 필드의 값으로 문서를 추가하고, 쿼리는 동일한 차원에 벡터를 사용하여 쿼리한다. (유사성 메트릭을 기반으로 벡처를 디자인한다.)

 

이미지 Vector 변환

이미지의 특징을 뽑아서 해당 특징점을 Vector로 변환한다.

이미지 구분이 가능한 hash값을 사용하여 Vector로 변환한다.

 

https://hackerfactor.com/blog/?/archives/432-Looks-Like-It.html

 

kNN Method

Elasticsearch는 kNN 검색을 위한 두 가지 방법을 지원한다.

• Exact, brute-force kNN : 벡트 함수와 함께 script_score 쿼리를 사용하는 무차별 대입
• Approximate kNN : 대략적인 knn 검색 옵션(HNSW)

대부분의 경우 Approximate kNN을 사용한다. (느린 인덱싱과 불완전한 정확도를 가지지만 응답 속도가 빠르다.)

 

Exact kNN

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

 

Approximate kNN

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

kNN 검색 API는 각 샤드에서 대략적인 가장 가까운 후보의 num_candidates 수를 찾고 검색은 쿼리 벡터에 대한 유효 벡터의 유사성을 계산하여 각 샤드에서 가장 유사한 k개의 결과를 선택하고, 이후 각 샤드의 결과를 병합하여 글로벌 상위 k 개의 결과를 반환한다.

 

인덱싱 고려사항

Approximate kNN 검색을 위해서 Elasticsearch는 각 세그먼트의 벡터 값을 HNSW(검색 속도 향상을 위해서 결과 정확도를 희생하는 근사 방법) 그래프로 저장하는데, 그래프 구축에 비용이 많이 필요하여, 아래 문서를 참고하여 튜닝한다.

 

Tune approximate kNN search

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

 

이미지 검색 Index 생성

PUT image-index
{
	"settings": {
    	"refresh_interval": "10s",
        "number_of_replicas": 0
    },
    "mappings": {
    	"properties":{
        	"image-vector": {
            	"type": "dense_vector",
                "dims": 512,
                "index": true,
                "similarity": "l2_norm"
            },
            "title": {
            	"type": "text"
            }
        }
    }
}

 

Parameters for dense vector fields

• dims : 벡터 차원의 수. (인덱싱 된 경우 1024, 인덱싱되지 않은 경우 2048을 초과할 수 없다.)
• index : kNN search API를 사용하기 위해서는 true로 설정한다.
• similarity: kNN 검색에 사용할 벡터 유사성 메트릭 (https://www.elastic.co/guide/en/elasticsearch/reference/current/dense-vector.html#dense-vector-similarity)
  • l2_norm
  • dot_product
  • cosine

 

이미지를 Vector로 변환하여 저장

POST image-index/_doc
{
	"title": "file_name",
    "image-vector": [
    122.112754821777734,
    181.080654821777738,
    ....
    ]
}

 

 

검색할 이미지의 Vector를 사용하여 이미지를 검색한다.

POST image-index/_search
{
	"knn": {
    	"field": "image-vector",
        "query_vector": [
        	123.112744821777734,
            404.143221234325541,
            ...
         ],
         "k": 10,
         "num_candidates": 100
    },
    "fields": [
    	"file_name"
    ]
}

 

 

검색 성능 참고 자료

벡터 차원이 1280인 이미지 약 100만개를 Elasticsearch에 저장하는데(r5.large instnace) 1시간이 걸렸고, 이미지 검색에는 15초가 걸렸다.

최적화와 instance 변경(r5.xlarge 4 CPU, 32GB) 후 1000개 요청에 대한 평균 응답 시간은 약 14ms이다.

https://medium.com/p/3dd5641b9adb

How to Realize a Practical Similarity Search with Elasticsearch