# Cardinality Estimation for High Dimensional Similarity Queries with Adaptive Bucket Probing

arXiv: https://arxiv.org/abs/2604.04603 · HTML: https://mlsanity.com/paper/2604.04603/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 36 references that are in the map.
- First posted on arXiv 6 Apr 2026.

## Builds on (most cited first, 9 of 9)

- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [Deep Unsupervised Cardinality Estimation](https://mlsanity.com/paper/1905.04278/) (2019)
- [Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation](https://mlsanity.com/paper/2109.05877/) (2021)
- [Pneuma: Leveraging LLMs for Tabular Data Representation and Retrieval in an End-to-End System](https://mlsanity.com/paper/2504.09207/) (2025)
- [The Design and Implementation of a Real Time Visual Search System on JD E-commerce Platform](https://mlsanity.com/paper/1908.07389/) (2019)
- [Consistent and Flexible Selectivity Estimation for High-Dimensional Data](https://mlsanity.com/paper/2005.09908/) (2020)
- [Local Density Estimation in High Dimensions](https://mlsanity.com/paper/1809.07471/) (2018)

## Abstract (arXiv)

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.