高效估算高维相似查询结果数量，兼顾精度与速度。
Cardinality Estimation for High Dimensional Similarity Queries with Adaptive Bucket Probing
- 基于自适应探查邻近哈希桶，动态调整搜索范围。
- 支持在线高效计算，减少距离计算量，加速高维检索。
- 适用于大规模动态数据更新场景，适合工业级应用。
本文针对高维空间中的相似性搜索问题，提出一种轻量、易构建且在线效率高的基数估计框架。通过局部敏感哈希（LSH）划分向量空间并保持距离相近性，借鉴经典多探针LSH思想，自适应探测邻近桶以应对不同距离阈值。为提升在线效率，采用渐进采样减少距离计算次数，并在乘积量化中引入非对称距离计算，加快高维空间的距离计算。该框架不仅支持静态数据，还设计了高效的数据更新算法，可处理大规模动态数据场景。实验表明，该方法能准确估计相似查询的基数，同时具备良好的效率。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。