적응형 버킷 탐색을 이용한 고차원 유사성 검색에서의 카디널리티 추정

Cardinality Estimation for High Dimensional Similarity Queries with Adaptive Bucket Probing

본 연구에서는 고차원 공간에서의 유사성 검색을 위한 카디널리티 추정 문제를 다룬다. 우리는 가볍고, 구축이 용이하며, 만족스러운 온라인 효율성을 제공하면서 정확한 추정값을 제공할 수 있는 프레임워크를 설계하는 것을 목표로 한다. 우리는 거리 근접성을 유지하면서 벡터 공간을 분할하기 위해 로컬리티-센시티브 해싱(LSH)을 활용한다. 이를 바탕으로, 다양한 크기의 거리 임계값을 고려하여 인접 버킷을 적응적으로 탐색하기 위해, 기존의 멀티-프로브 LSH의 원리를 적용한다. 온라인 효율성을 향상시키기 위해, 거리 계산 횟수를 줄이기 위해 점진적 샘플링을 사용하고, 고차원 공간에서의 거리 계산 속도를 높이기 위해 프로덕트 양자화에서 비대칭 거리 계산을 활용한다. 또한, 본 프레임워크는 정적 데이터셋뿐만 아니라, 대규모 동적 데이터 업데이트 시나리오에서도 효율적으로 대응할 수 있도록 업데이트 알고리즘을 포함한다. 실험 결과는 제안하는 방법이 유사성 검색의 카디널리티를 정확하게 추정하며, 만족스러운 효율성을 제공함을 보여준다.

In this work, we address the problem of cardinality estimation for similarity search in high-dimensional spaces. Our goal is to design a framework that is lightweight, easy to construct, and capable of providing accurate estimates with satisfying online efficiency. We leverage locality-sensitive hashing (LSH) to partition the vector space while preserving distance proximity. Building on this, we adopt the principles of classical multi-probe LSH to adaptively explore neighboring buckets, accounting for distance thresholds of varying magnitudes. To improve online efficiency, we employ progressive sampling to reduce the number of distance computations and utilize asymmetric distance computation in product quantization to accelerate distance calculations in high-dimensional spaces. In addition to handling static datasets, our framework includes updating algorithm designed to efficiently support large-scale dynamic scenarios of data updates.Experiments demonstrate that our methods can accurately estimate the cardinality of similarity queries, yielding satisfying efficiency.