rice.upenn.edu

이 이메일 도메인이 관측된 논문 1건

arXiv:2506.06557v3cs.IR

Infinity Search: q-메트릭 공간 투영을 활용한 근사 벡터 검색

Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces

초거리 공간(ultrametric space) 또는 무한대-메트릭 공간(infinity-metric space)은 삼각형의 모든 변이 다른 두 변 중 더 큰 변보다 크지 않다는 강한 삼각 부등식을 만족하는 비유사도 함수로 정의됩니다. 본 연구에서는 밴티지 포인트 트리(vantage point tree)를 사용한 초거리 공간에서의 검색이 트리의 깊이와 동일한 최악 조건 복잡도(worst-case complexity)를 가짐을 보입니다. 관심 대상이 되는 데이터셋은 일반적으로 초거리 공간을 따르지 않으므로, 최근접 이웃(nearest neighbors)을 보존하면서 임의의 비유사도 함수를 초거리 공간으로 변환하는 투영 연산자(projection operator)를 도입합니다. 나아가 쿼리 포인트와 데이터셋 내 포인트 간의 초거리 거리를 효율적으로 계산하기 위해 이 투영 연산자의 근사를 학습합니다. 이어서 삼각형의 변을 $q$제곱한 값이 다른 두 변의 $q$제곱의 합보다 작은 $q$-메트릭 공간에서의 투영을 고려하는 보다 일반적인 문제를 해결합니다. 투영된 $q$-메트릭 거리의 학습된 근사를 사용하면 검색 파이프라인이 근사(approximate) 검색으로 변환된다는 점에 유의해야 합니다. 실험을 통해 $q$ 값이 증가할수록 검색 속도는 빨라지지만 재현율은 낮아짐을 보입니다. 전반적으로 $q$-메트릭 및 무한대-메트릭 공간에서의 검색은 기존 검색 방식과 비교해 경쟁력이 있습니다.