Efficient k-NN filtering
출처: 문서
본문
효율적인 k-NN 필터링
lucene, faiss, jvector 엔진을 사용하면 효율적인 k-NN 필터링을 수행할 수 있어요.
Lucene k-NN 필터 구현
Lucene 엔진은 HNSW 그래프를 사용하는 k-NN 검색을 위한 Lucene 필터를 지원해요.
k-NN 검색에 Lucene 필터를 지정하면, Lucene 알고리즘은 사전 필터링을 적용한 정확한 k-NN 검색을 수행할지, 아니면 수정된 사후 필터링을 적용한 근사 검색을 수행할지 결정해요. 이 알고리즘은 다음 변수들을 사용해요:
- N: 인덱스에 있는 문서의 수.
- P: 필터가 적용된 후 문서 부분집합에 있는 문서의 수 (P <= N).
- k: 응답에 반환할 벡터의 최대 개수.
다음 플로우 차트는 Lucene 알고리즘의 개요를 보여줘요.
Lucene 필터링 구현과 그 기반이 되는 KnnFloatVectorQuery에 대해 더 자세히 알아보려면 Apache Lucene 문서를 참고하세요.
Lucene k-NN 필터 사용하기
호텔 정보를 담고 있는 12개의 문서로 이루어진 데이터셋이 있다고 해 봐요. 다음 이미지는 모든 호텔을 위치별로 xy 좌표 평면에 나타낸 거예요. 또한 평점이 8에서 10 사이(8과 10 포함)인 호텔은 주황색 점으로, 주차를 제공하는 호텔은 초록색 원으로 표시되어 있어요. 검색 지점은 빨간색으로 표시되어 있어요:
이 예제에서는 인덱스를 만들고, 검색 위치에서 가장 가까우면서 평점이 높고 주차를 제공하는 세 개의 호텔을 검색해 볼 거예요.
1단계: 새 인덱스 생성하기
필터와 함께 k-NN 검색을 실행하려면 먼저 knn_vector 필드가 있는 인덱스를 만들어야 해요. 이 필드에는 매핑에서 엔진으로 lucene을, method로는 hnsw를 지정해야 해요.
다음 요청은 location이라는 knn-filter 필드가 있는 hotels-index라는 새 인덱스를 만들어요:
PUT /hotels-index
{
"settings": {
"index": {
"knn": true,
"knn.algo_param.ef_search": 100,
"number_of_shards": 1,
"number_of_replicas": 0
}
},
"mappings": {
"properties": {
"location": {
"type": "knn_vector",
"dimension": 2,
"method": {
"name": "hnsw",
"space_type": "l2",
"engine": "lucene",
"parameters": {
"ef_construction": 100,
"m": 16
}
}
}
}
}
}
{% include copy-curl.html %}
2단계: 인덱스에 데이터 추가하기
다음으로, 인덱스에 데이터를 추가해요.
다음 요청은 호텔 위치, 평점, 주차 정보를 담고 있는 12개의 문서를 추가해요:
POST /_bulk
{ "index": { "_index": "hotels-index", "_id": "1" } }
{ "location": [5.2, 4.4], "parking" : "true", "rating" : 5 }
{ "index": { "_index": "hotels-index", "_id": "2" } }
{ "location": [5.2, 3.9], "parking" : "false", "rating" : 4 }
{ "index": { "_index": "hotels-index", "_id": "3" } }
{ "location": [4.9, 3.4], "parking" : "true", "rating" : 9 }
{ "index": { "_index": "hotels-index", "_id": "4" } }
{ "location": [4.2, 4.6], "parking" : "false", "rating" : 6}
{ "index": { "_index": "hotels-index", "_id": "5" } }
{ "location": [3.3, 4.5], "parking" : "true", "rating" : 8 }
{ "index": { "_index": "hotels-index", "_id": "6" } }
{ "location": [6.4, 3.4], "parking" : "true", "rating" : 9 }
{ "index": { "_index": "hotels-index", "_id": "7" } }
{ "location": [4.2, 6.2], "parking" : "true", "rating" : 5 }
{ "index": { "_index": "hotels-index", "_id": "8" } }
{ "location": [2.4, 4.0], "parking" : "true", "rating" : 8 }
{ "index": { "_index": "hotels-index", "_id": "9" } }
{ "location": [1.4, 3.2], "parking" : "false", "rating" : 5 }
{ "index": { "_index": "hotels-index", "_id": "10" } }
{ "location": [7.0, 9.9], "parking" : "true", "rating" : 9 }
{ "index": { "_index": "hotels-index", "_id": "11" } }
{ "location": [3.0, 2.3], "parking" : "false", "rating" : 6 }
{ "index": { "_index": "hotels-index", "_id": "12" } }
{ "location": [5.0, 1.0], "parking" : "true", "rating" : 3 }
{% include copy-curl.html %}
3단계: 필터로 데이터 검색하기
이제 필터가 포함된 k-NN 검색을 만들 수 있어요. k-NN 쿼리 절에는 최근접 이웃을 검색하는 데 사용할 관심 지점, 반환할 최근접 이웃의 개수(k), 그리고 제한 조건이 담긴 필터를 포함해요. 필터를 얼마나 엄격하게 만들고 싶은지에 따라 하나의 요청에 여러 개의 쿼리 절을 추가할 수도 있어요.
다음 요청은 좌표 [5, 4] 위치 근처에서 평점이 8에서 10 사이(8과 10 포함)이고 주차를 제공하는 상위 세 개의 호텔을 검색하는 k-NN 쿼리를 만들어요:
POST /hotels-index/_search
{
"size": 3,
"query": {
"knn": {
"location": {
"vector": [
5,
4
],
"k": 3,
"filter": {
"bool": {
"must": [
{
"range": {
"rating": {
"gte": 8,
"lte": 10
}
}
},
{
"term": {
"parking": "true"
}
}
]
}
}
}
}
}
}
{% include copy-curl.html %}
응답은 검색 지점에 가장 가깝고 필터 조건을 만족하는 세 개의 호텔을 반환해요:
{
"took": 47,
"timed_out": false,
"_shards": {
"total": 1,
"successful": 1,
"skipped": 0,
"failed": 0
},
"hits": {
"total": {
"value": 3,
"relation": "eq"
},
"max_score": 0.72992706,
"hits": [
{
"_index": "hotels-index",
"_id": "3",
"_score": 0.72992706,
"_source": {
"location": [4.9, 3.4],
"parking": "true",
"rating": 9
}
},
{
"_index": "hotels-index",
"_id": "6",
"_score": 0.3012048,
"_source": {
"location": [6.4, 3.4],
"parking": "true",
"rating": 9
}
},
{
"_index": "hotels-index",
"_id": "5",
"_score": 0.24154587,
"_source": {
"location": [3.3, 4.5],
"parking": "true",
"rating": 8
}
}
]
}
}
필터를 구성하는 더 많은 방법은 필터 구성하기를 참고하세요.
Faiss k-NN 필터 구현
k-NN 검색에서는 HNSW 알고리즘(OpenSearch 버전 2.9 이상)이나 IVF 알고리즘(OpenSearch 버전 2.10 이상)과 함께 faiss 필터를 사용할 수 있어요.
k-NN 검색에 Faiss 필터를 지정하면, Faiss 알고리즘은 사전 필터링을 적용한 정확한 k-NN 검색을 수행할지, 아니면 수정된 사후 필터링을 적용한 근사 검색을 수행할지 결정해요. 이 알고리즘은 다음 변수들을 사용해요:
- N: 인덱스에 있는 문서의 수.
- P: 필터가 적용된 후 문서 부분집합에 있는 문서의 수 (P <= N).
- k: 응답에 반환할 벡터의 최대 개수.
- R: 필터링된 근사 최근접 이웃 검색을 수행한 후 반환되는 결과의 수.
- FT (filtered threshold): 정확한 검색으로 전환할 시점을 지정하는 인덱스 수준 임계값으로,
knn.advanced.filtered_exact_search_threshold설정에 정의되어 있어요. - MDC (max distance computations):
FT(filtered threshold)가 설정되어 있지 않을 때 정확한 검색에서 허용되는 최대 거리 계산 횟수예요. 이 값은 변경할 수 없어요.
다음 플로우 차트는 Faiss 알고리즘의 개요를 보여줘요.
정확한 검색 폴백 비활성화하기
3.5에 도입됨 {: .label .label-purple }
필터와 일치하는 문서가 k개보다 많은데도(P ≥ k) Faiss 효율적 필터링 ANN 검색이 k개 미만의 결과(R < k)를 반환하면, k개의 결과가 반환되도록 알고리즘은 필터링된 문서 ID를 대상으로 정확한 검색으로 폴백해요.
k개 미만의 결과로도 충분한 지연 시간 민감형 워크로드의 경우, index.knn.faiss.efficient_filter.disable_exact_search 인덱스 설정을 true로 설정해서 이 폴백을 비활성화할 수 있어요. 이 설정이 활성화되면 검색은 근사 결과만 반환하고 추가적인 정확한 검색은 건너뛰어요.
이 설정에 대해 더 자세히 알아보려면 벡터 검색 설정을 참고하세요.
Faiss 효율적 필터 사용하기
전자상거래 애플리케이션을 위해 다양한 셔츠 정보를 담고 있는 인덱스가 있다고 해 봐요. 이미 가지고 있는 셔츠와 비슷하면서 평점이 높은 셔츠를 찾고 싶지만, 결과를 셔츠 사이즈로 제한하고 싶을 거예요.
이 예제에서는 인덱스를 만들고, 제공하는 셔츠와 비슷한 셔츠를 검색해 볼 거예요.
1단계: 새 인덱스 생성하기
필터와 함께 k-NN 검색을 실행하려면 먼저 knn_vector 필드가 있는 인덱스를 만들어야 해요. 이 필드에는 매핑에서 엔진으로 faiss를, method로는 hnsw를 지정해야 해요.
다음 요청은 셔츠의 벡터 표현을 담고 있는 인덱스를 만들어요:
PUT /products-shirts
{
"settings": {
"index": {
"knn": true
}
},
"mappings": {
"properties": {
"item_vector": {
"type": "knn_vector",
"dimension": 3,
"method": {
"name": "hnsw",
"space_type": "l2",
"engine": "faiss"
}
}
}
}
}
{% include copy-curl.html %}
2단계: 인덱스에 데이터 추가하기
다음으로, 인덱스에 데이터를 추가해요.
다음 요청은 벡터 표현, 사이즈, 평점을 포함한 셔츠 정보를 담고 있는 12개의 문서를 추가해요:
POST /_bulk?refresh
{ "index": { "_index": "products-shirts", "_id": "1" } }
{ "item_vector": [5.2, 4.4, 8.4], "size" : "large", "rating" : 5 }
{ "index": { "_index": "products-shirts", "_id": "2" } }
{ "item_vector": [5.2, 3.9, 2.9], "size" : "small", "rating" : 4 }
{ "index": { "_index": "products-shirts", "_id": "3" } }
{ "item_vector": [4.9, 3.4, 2.2], "size" : "xlarge", "rating" : 9 }
{ "index": { "_index": "products-shirts", "_id": "4" } }
{ "item_vector": [4.2, 4.6, 5.5], "size" : "large", "rating" : 6}
{ "index": { "_index": "products-shirts", "_id": "5" } }
{ "item_vector": [3.3, 4.5, 8.8], "size" : "medium", "rating" : 8 }
{ "index": { "_index": "products-shirts", "_id": "6" } }
{ "item_vector": [6.4, 3.4, 6.6], "size" : "small", "rating" : 9 }
{ "index": { "_index": "products-shirts", "_id": "7" } }
{ "item_vector": [4.2, 6.2, 4.6], "size" : "small", "rating" : 5 }
{ "index": { "_index": "products-shirts", "_id": "8" } }
{ "item_vector": [2.4, 4.0, 3.0], "size" : "small", "rating" : 8 }
{ "index": { "_index": "products-shirts", "_id": "9" } }
{ "item_vector": [1.4, 3.2, 9.0], "size" : "small", "rating" : 5 }
{ "index": { "_index": "products-shirts", "_id": "10" } }
{ "item_vector": [7.0, 9.9, 9.0], "size" : "xlarge", "rating" : 9 }
{ "index": { "_index": "products-shirts", "_id": "11" } }
{ "item_vector": [3.0, 2.3, 2.0], "size" : "large", "rating" : 6 }
{ "index": { "_index": "products-shirts", "_id": "12" } }
{ "item_vector": [5.0, 1.0, 4.0], "size" : "large", "rating" : 3 }
{% include copy-curl.html %}
3단계: 필터로 데이터 검색하기
이제 필터가 포함된 k-NN 검색을 만들 수 있어요. k-NN 쿼리 절에는 비슷한 셔츠를 검색하는 데 사용할 셔츠의 벡터 표현, 반환할 최근접 이웃의 개수(k), 그리고 사이즈와 평점에 따른 필터를 포함해요.
다음 요청은 평점이 7에서 10 사이(7과 10 포함)인 스몰 사이즈 셔츠를 검색해요:
POST /products-shirts/_search
{
"size": 2,
"query": {
"knn": {
"item_vector": {
"vector": [
2, 4, 3
],
"k": 10,
"filter": {
"bool": {
"must": [
{
"range": {
"rating": {
"gte": 7,
"lte": 10
}
}
},
{
"term": {
"size": "small"
}
}
]
}
}
}
}
}
}
{% include copy-curl.html %}
응답은 일치하는 두 개의 문서를 반환해요:
{
"took": 2,
"timed_out": false,
"_shards": {
"total": 1,
"successful": 1,
"skipped": 0,
"failed": 0
},
"hits": {
"total": {
"value": 2,
"relation": "eq"
},
"max_score": 0.8620689,
"hits": [
{
"_index": "products-shirts",
"_id": "8",
"_score": 0.8620689,
"_source": {
"item_vector": [2.4, 4, 3],
"size": "small",
"rating": 8
}
},
{
"_index": "products-shirts",
"_id": "6",
"_score": 0.029691212,
"_source": {
"item_vector": [6.4, 3.4, 6.6],
"size": "small",
"rating": 9
}
}
]
}
}
필터를 구성하는 더 많은 방법은 필터 구성하기를 참고하세요.
ACORN 필터링 최적화
3.1에 도입됨 {: .label .label-purple } ACORN 필터링 최적화는 기본 알고리즘을 수정해서 필터링 조건과 일치하는 벡터만 스코어링하고 탐색해요. 필터링 때문에 그래프 희소성이 커지면, 검색은 이웃의 이웃까지 포함하도록 확장돼요. 이 추가 탐색의 범위는 필터링되어 제외된 이웃의 비율에 따라 달라지는데, 필터가 더 엄격할수록 검색 범위가 더 넓어져요.
필터링이 미미할 때는 알고리즘이 이러한 최적화를 아예 건너뛰어요. 기본적으로 이 임계값은 60%예요. 확장된 이웃 탐색은 현재 이웃 중 90% 미만만 필터와 일치할 때만 수행돼요.
메모리 최적화 검색이 활성화되어 있으면, 효율적 필터 프레임워크는 HNSW 내에서 필터링을 계속 적용해요. ACORN 필터링 최적화는 필터링된 문서 수가 HNSW 알고리즘이 현재 고려하고 있는 검색 공간의 전체 문서 수의 60% 이하일 때만 적용돼요.
JVector 효율적 필터 사용하기
opensearch-jvector 플러그인은 disk_ann 메서드와 함께 jvector 엔진을 사용하는 필터링을 지원해요. knn 쿼리 절 안에 인라인 filter를 넣으면 그래프를 순회하는 동안 후보를 제한할 수 있어요. post_filter 파라미터를 사용한 사후 필터링도 지원되지만, 필터가 엄격할 때는 k개 미만의 결과가 반환될 수 있어요.
이 예제에서는 jvector 엔진을 사용해 인덱스를 만들고, 평점이 높고 주차를 제공하는 가장 가까운 세 개의 호텔을 검색해 볼 거예요.
1단계: 새 인덱스 생성하기
knn_vector 필드가 있는 인덱스를 만들고, 엔진으로는 jvector를, 메서드로는 disk_ann을 지정해요:
PUT /hotels-jvector-index
{
"settings": {
"index": {
"knn": true,
"number_of_shards": 1,
"number_of_replicas": 0
}
},
"mappings": {
"properties": {
"location": {
"type": "knn_vector",
"dimension": 2,
"method": {
"name": "disk_ann",
"space_type": "l2",
"engine": "jvector",
"parameters": {
"ef_construction": 100,
"m": 16
}
}
}
}
}
}
{% include copy-curl.html %}
2단계: 인덱스에 데이터 추가하기
호텔 위치, 평점, 주차 정보를 담고 있는 12개의 문서를 추가해요:
POST /_bulk
{ "index": { "_index": "hotels-jvector-index", "_id": "1" } }
{ "location": [5.2, 4.4], "parking" : "true", "rating" : 5 }
{ "index": { "_index": "hotels-jvector-index", "_id": "2" } }
{ "location": [5.2, 3.9], "parking" : "false", "rating" : 4 }
{ "index": { "_index": "hotels-jvector-index", "_id": "3" } }
{ "location": [4.9, 3.4], "parking" : "true", "rating" : 9 }
{ "index": { "_index": "hotels-jvector-index", "_id": "4" } }
{ "location": [4.2, 4.6], "parking" : "false", "rating" : 6}
{ "index": { "_index": "hotels-jvector-index", "_id": "5" } }
{ "location": [3.3, 4.5], "parking" : "true", "rating" : 8 }
{ "index": { "_index": "hotels-jvector-index", "_id": "6" } }
{ "location": [6.4, 3.4], "parking" : "true", "rating" : 9 }
{ "index": { "_index": "hotels-jvector-index", "_id": "7" } }
{ "location": [4.2, 6.2], "parking" : "true", "rating" : 5 }
{ "index": { "_index": "hotels-jvector-index", "_id": "8" } }
{ "location": [2.4, 4.0], "parking" : "true", "rating" : 8 }
{ "index": { "_index": "hotels-jvector-index", "_id": "9" } }
{ "location": [1.4, 3.2], "parking" : "false", "rating" : 5 }
{ "index": { "_index": "hotels-jvector-index", "_id": "10" } }
{ "location": [7.0, 9.9], "parking" : "true", "rating" : 9 }
{ "index": { "_index": "hotels-jvector-index", "_id": "11" } }
{ "location": [3.0, 2.3], "parking" : "false", "rating" : 6 }
{ "index": { "_index": "hotels-jvector-index", "_id": "12" } }
{ "location": [5.0, 1.0], "parking" : "true", "rating" : 3 }
{% include copy-curl.html %}
3단계: 필터로 데이터 검색하기
그래프를 순회하는 동안 후보를 제한하려면 filter를 knn 쿼리 절 안에 넣어요. 다음 요청은 [5, 4] 근처에서 평점이 8에서 10 사이이고 주차를 제공하는 상위 세 개의 호텔을 검색해요:
POST /hotels-jvector-index/_search
{
"size": 3,
"query": {
"knn": {
"location": {
"vector": [5, 4],
"k": 3,
"filter": {
"bool": {
"must": [
{
"range": {
"rating": {
"gte": 8,
"lte": 10
}
}
},
{
"term": {
"parking": "true"
}
}
]
}
}
}
}
}
}
{% include copy-curl.html %}
4단계: 사후 필터링으로 데이터 검색하기
post_filter를 사용하면 ANN 검색 이후에 필터링을 적용할 수도 있어요. post_filter는 ANN 검색으로 결과를 가져온 다음에 실행되기 때문에, 필터가 엄격할 때는 최종 결과 개수가 k개보다 적을 수 있어요. 이를 보완하려면 k를 필요한 결과 개수보다 큰 값으로 설정하면 돼요.
다음 요청은 가장 가까운 20개의 호텔을 가져온 다음, 평점이 8 이상이고 주차를 제공하는 호텔들로 결과를 제한해요:
POST /hotels-jvector-index/_search
{
"size": 3,
"query": {
"knn": {
"location": {
"vector": [5, 4],
"k": 20
}
}
},
"post_filter": {
"bool": {
"must": [
{
"range": {
"rating": {
"gte": 8,
"lte": 10
}
}
},
{
"term": {
"parking": "true"
}
}
]
}
}
}
{% include copy-curl.html %}
필터 구성하기
같은 조건에 대한 필터를 구성하는 방법은 여러 가지가 있어요. 예를 들어 다음 구성 요소를 사용하면 주차를 제공하는 호텔을 반환하는 필터를 만들 수 있어요:
should절 안의term쿼리 절should절 안의wildcard쿼리 절should절 안의regexp쿼리 절parking이false로 설정된 호텔을 제외하기 위한must_not절.
다음 요청은 주차를 제공하는 호텔을 검색하는 이 네 가지 방법을 보여줘요:
POST /hotels-index/_search
{
"size": 3,
"query": {
"knn": {
"location": {
"vector": [ 5.0, 4.0 ],
"k": 3,
"filter": {
"bool": {
"must": {
"range": {
"rating": {
"gte": 1,
"lte": 6
}
}
},
"should": [
{
"term": {
"parking": "true"
}
},
{
"wildcard": {
"parking": {
"value": "t*e"
}
}
},
{
"regexp": {
"parking": "[a-zA-Z]rue"
}
}
],
"must_not": [
{
"term": {
"parking": "false"
}
}
],
"minimum_should_match": 1
}
}
}
}
}
}
{% include copy-curl.html %}