Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces an adaptive bucket probing technique for cardinality estimation in high-dimensional similarity search using LSH. They improve estimation accuracy by adaptively exploring neighboring buckets based on distance thresholds and enhance online efficiency through progressive sampling and asymmetric distance computation with product quantization. Experiments on both static and dynamic datasets demonstrate accurate cardinality estimation with improved efficiency compared to existing methods.
Accurate cardinality estimation for similarity search in high-dimensional spaces is now faster and more lightweight thanks to adaptive bucket probing.
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.