SeRF: 범위 필터링 근사 최근접 이웃 검색을 위한 세그먼트 그래프

효과적인 벡터 표현 모델, 예를 들어 word2vec 및 node2vec는 이미지를 비롯한 실제 객체와 문서를 고차원 벡터 공간에 임베드합니다. 이와 동시에 객체는 종종 타임스탬프 및 가격과 같은 속성과 연관됩니다. 많은 시나리오는 객체의 벡터 표현과 이들의 속성을 함께 쿼리해야 합니다. 이러한 쿼리는 범위 필터링 근사 최근접 이웃 검색(ANNS) 쿼리로 공식화될 수 있습니다. 구체적으로, 속성 값이 전총서에 따라 정렬된 데이터 벡터의 모음이 주어졌을 때, 범위 필터링 ANNS는 쿼리 범위와 쿼리 벡터로 구성됩니다. 이는 쿼리 벡터의 근사 최근접 이웃을 찾는데, 속성 값이 쿼리 범위에 해당하는 모든 데이터 벡터 중에서 찾아냅니다. 기존 접근법은 쿼리 범위의 폭이 변할 때 쿼리 성능이 급격히 저하되는 문제를 겪습니다. 쿼리 성능은 가능한 모든 쿼리 범위에 대해 ANNS 인덱스를 구축하는 솔루션으로 최적화될 수 있습니다. 하지만 이 경우 인덱스 시간과 인덱스 크기가 막대한 비용을 초래하게 됩니다. 쿼리 범위의 수는 데이터 벡터 수 n에 대해 제곱에 비례합니다. 이러한 문제를 극복하기 위해 사용자가 제공한 임계점보다 작은 모든 속성 값을 포함하는 쿼리 범위에 대해 우리는 세그먼트 그래프라는 구조를 설계했습니다. 이 구조는 인덱스 시간과 크기가 단일 ANNS 인덱스와 동일하면서 n개의 ANNS 인덱스를 무손실로 압축하여 인덱싱 비용을 Ω(n)만큼 줄입니다. 일반 범위 쿼리를 처리하기 위해, 우리는 n개의 세그먼트 그래프를 압축하는 평균 케이스 인덱스 크기가 O(n log n)인 2D 세그먼트 그래프를 제안하며, 이는 제곱 장벽을 깨는 것입니다. 실제 데이터셋에서 수행된 광범위한 실험 결과, 우리가 제안한 구조가 기존 방법들에 비해 현저히 우수하다는 것을 보여줍니다. 우리의 인덱스 또한 뛰어난 확장성을 보입니다.