Juyeong Shin

KHU CSE 19
KHU DKE Lab.

4 분 소요

SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search

About Paper

  • 제목: SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search
  • 저널: ACM Manag. Data, Vol. 2, No. 1 (SIGMOD, Special Interest Group on Management of Data), Article 69. Feb 2024.
  • 저자: Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, Dong Deng

Introduction

ANN Search가 사용되는 분야

  • image, document, graph와 같은 실세계 데이터를 고차원 벡터로 임베딩하는 기술이 계속 발전하고 있음
  • 한편, 이러한 데이터는 timestamps, prices, quantities와 같은 structured data와 함께 연관되어 사용되곤 했음
    • 예시 1: 상품 탐색
      • 200달러 미만의 주어진 이미지와 비슷한 상품 탐색
    • 예시 2: 자동차 탐색
      • 도로 위 카메라는 주어진 이미지를 임베딩하여 벡터 생성
      • 생성된 벡터는 database timestamp에 저장 및 탐색
      • 번호판 없이, (time, space, image) 정보로 차량 특정
  • 그러나, 기존 RDBMS 기반 Filtering과 벡터 탐색을 동시에 수행하는 것은 여전히 데이터공학에서 도전적인 과제
    • 해당 문제 해결을 위한 다양한 질의 최적화 기법, 인덱싱 기법이 연구 중에 있음
    • 아직 많이 미흡한 상황..
    • 한번 떠올려보자. 이미지 검색과 동시에 다양한 필터링 조건을 붙여본 경험이 있던가?
  • 위 설명과 같이, 조건을 붙여 벡터를 탐색하는 기법을 RFANNS(Range-Filtering Approximate Nearest Neighbor Search)라 칭함
  • Range-Filtering ANNS(Approximate Nearest Neighbor Search)는 query range(질의 범위)와 query vector(질의 벡터)로 구성됨
    • 도전적인 과제인 이유는 생각보다 단순하다
    • 전체 벡터에 대한 인덱스는 존재하나, 필터링 된 벡터에 대한 인덱스는 없기 때문
  • 한편, 기존 range-filtering ANNS는 크게 2가지로 분류가 가능하다
    • ANNS-first (vectorDB-first)
      • ANNS-first는 주어진 query range에 부합할 때까지 ANN Search 수행
      • 주어진 query range에 부합하는 vector들을 반환
      • query range가 작은 경우, 조건에 부합하는 vector를 지속적으로 탐색하므로 수행 속도가 느리다
    • range-first (RDBMS-first)
      • 주어진 range에 따른 structured database에서 우선 탐색
      • structured database에서 필터링된 레코드에 대한 vector index가 구축되어 있지 않아 filtering 된 vector들은 naive한 탐색을 수행
      • 특히, range-first는 query range가 클 때, 비효율적
    • 주어진 상황에 어떤 전략을 취해야 할지에 대한 연구는 아래 논문을 참고하자

HNSW(Hierarchical Navigable Small World)

  1. Paper
    • Yu. A. Malkov, D. A. Yashunin. “Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World”. IEEE Transactions on pattern analysis and machine intelligence. 2018.
    • http://arxiv.org/pdf/1603.09320
  2. My Paper Review

Proposing Solution: Segment Graph

  • Half-bounded Range-Filtering ANNS Query: Segment Graph
    • Half-bounded: 주어진 set of vectors를 2개의 subset으로 분할
    • attribute에 따라 n개의 half-bounded hnsw index 생성 가능
    • 분할된 데이터를 통해 n개의 HNSW index 구축
    • 구축된 n개의 HNSW index를 무손실 압축하여 Segment Graph 구축
  • General Range-Filtering ANNS Query: 2D Segment Graph
    • N개의 Segment Graph를 통해 2D Segment Graph 구축

Preliminary

Segment

Segment의 사전적 의미

  • 명사: 부분, 단편, 분절(分節), 구분, 마디(division, section), 계층
  • 동사 전문 용어: (여러 부분으로)나누다, 분할하다

컴퓨터 공학에서 Segment

  • 컴퓨터 공학에서 Segment의 의미도 동일하다.
  • OS에서 Segmentation은 메모리 공간을 프로세스 단위로 나누어 관리하는 기법을 말하고
  • CV에서 Image Segmentation는 이미지에서 특정 개체를 추출(구분, 분할)하는 방법을 말한다
  • 또한, 자료구조에서 Segment Tree는 부분 질의에 대한 집계 결과들을 트리 형태로 관리하는 것을 말한다
    • 결론적인 기능 자체는 범위 질의에 대한 최대, 최소, 합, 곱 연산 결과를 미리 연산하면서 효율적인 접근이 가능한 형태의 트리로 관리하는 것이다

Segment Tree

  • Segment Tree에 대해 잠깐 짚어보고 넘어가자. 이번 포스팅에 꼭 필요한 지식은 아니나 아이디어 자체는 비슷하다고 생각한다
  • 길이가 1000인 array에서 10~100번 idx의 부분합을 구하려면 결국 해당 범위만큼의 복잡도가 따른다
    • 시작 범위를 $i$, 마지막 범위를 $j$라 하면, 시간복잡도는 $T(j-i+1)$ 이다
  • 한편, 아래와 같은 Segment Tree의 형태로 합 연산을 미리 저장해두면 $O(\log N)$ 의 복잡도를 보장해준다
  • 원하는 범위를 적절하게 포함하고 있는 노드 하나를 선택한 후 해당되지 않는 일부 범위를 빼거나 해당되는 일부 범위를 더하는 방식이다

seg_tree

Range-Filtering

  • 특정 애트리뷰트에 조건을 달거나, 범위를 지정하여 필터링 한 후 다른 애트리뷰트를 다시 탐색하는 것
  • 질의최적화를 설명하라 할 때, 흔히 등장하는 예시이기도 하다(Column Oriented Database)
    • 경기도의 모든 인구(1400만)를 관리하는 테이블이 있다

    • 해당 테이블에서 14세 미만(160만)의 모든 남성(700만)을 찾고싶다

    • 이때, 14세 미만의 인구를 찾은 뒤 남성을 찾는게 빠를까

    • 아니면 남성을 찾은 뒤 그 중에서 14세 미만의 사람을 찾는게 빠를까

    • 전자는 1400만명 중에서 160만명을 찾고 160만명 중에서 80만명을 찾는다
      • 순차탐색을 진행한다 하였을 때, 1400만개의 레코드를 조회한 후 160만개의 레코드를 조회하니 총 1560만번의 조회가 발생했다
    • 후자는 1400만명 중에서 700만명을 찾고 700만명 중에서 80만명을 찾는다
      • 순차탐색을 진행한다 하였을 때, 1400만개의 레코드를 조회한 후 700만개의 레코드를 조회하니 총 2100만번의 조회가 발생했다
    • 결론적으로 전자가 더 효율적인 접근이다!
  • 얘기가 산으로 간 느낌이 강하지만, 결론적으로 위와 같은 상황을 Range-Filtering이라 한다
  • kNN(k-Nearest Neighbors, 최근접 이웃 알고리즘)의 일종이다
  • 인공지능 모델로 임베딩된 벡터들을 다시 조회하고 싶을 때 사용하는 알고리즘이다
    • 비슷한 이미지 찾기, 비슷한 음성 찾기, …
  • 그러나, 기존 kNN의 경우 임베딩 벡터의 차원이 증가함에 따라 복잡도가 선형적으로 증가하여 바로 적용하기 무리인 부분이 존재한다(k-D Tree, Ball Tree)
  • 이에 새로 등장하는 대안이 ANNS이고 대표적인 알고리즘으로는 HNSW, Vamana, NSG, ANNOY, IVFPQ 등이 존재한다
    • Graph-Based ANNS
      • HNSW, Vamana, NSG
      • 자료구조 상에서의 dimension에 따른 penalty를 회피하는 방식
      • Greedy Search를 주로 사용(Approximate Navigating)
      • 이웃 간 거리를 비교하여 당장의 최선의 후보를 선택하는 방식
      • 거리 비교 시에는 dimension에 의존적이나, k-D트리와 같이 구조 자체가 dimension에 의존적이지 않다
    • Tree-Based ANNS
      • ANNOY
      • 트리를 계층적으로 생성하여 비교군의 개수 자체를 줄이는 방식
    • IVFPQ(Inverted File index & Product Quantization)
      • PQ를 통해 클러스터를 나눈 후, 해당 클러스터 내에서 최근접 이웃을 탐색
      • Qunatized Vector를 통해 적절한 Voronoi Cell(클러스터)에 접근, 해당 클러스터 내에서 최근접 이웃을 탐색
      • Qunatized Vector는 원본 벡터의 차원을 손실 압축한 것
      • 즉, PQ는 dimension 자체를 낮춘다
  • kNN과 달리, ANNS 알고리즘은 정확한 k개의 최근접 이웃을 반환하지 않지만, 고차원 벡터 데이터를 보다 효율적으로 접근할 수 있게 한다

Notations with Attribute Filtering

RFANNS with Half-bounded Query Ranges

RFANNS with Arbitrary Query Ranges

Experiment

Conclusion

References

댓글남기기

참고

멀티 쓰레딩 환경에서 캐시 미스에 대해

4 분 소요

멀티 쓰레딩 환경에서 캐시 미스에 대해 CPU 캐시의 구조 이번 포스팅에 앞서, numpy가 더 빠른 이유 - 캐시메모리 입장에서를 먼저 보고 오길 권장한다. CPU 캐시 메모리에 대한 대략적인 이해 후 이번 포스팅을 보는 것이 훨씬 이해에 도움이 될 것이다.

Randomized Quick Sort와 느낀 점

1 분 소요

Randomized Quick Sort와 느낀 점 Quick Sort Quick Sort는 분할정복 알고리즘(Divide & Conquer)으로서, pivot을 잡고 partiton 함수로 pivot보다 작은 item들은 왼쪽에, pivot보다 큰 item들은 오른쪽에...

BST(Binary Search Tree)와 KD트리 그리고 B트리와 R트리

11 분 소요

BST(Binary Search Tree)와 KD트리 그리고 B트리와 R트리 트리를 이용한 인덱싱 기법들.. 근데 이제, 다차원을 곁들인 자료구조를 공부한 적이 있다면 BST(Binary Search Tree, 이진탐색트리)도 배웠을 것이다.