Cardinality Estimation for High Dimensional Similarity Queries with Adaptive Bucket Probing

Zhonghan Chen; Qintian Guo; Ruiyuan Zhang; Xiaofang Zhou

cs.DBApr 6, 2026

Cardinality Estimation for High Dimensional Similarity Queries with Adaptive Bucket Probing

Authors: Zhonghan Chen, Qintian Guo, Ruiyuan Zhang, Xiaofang Zhou

Organizations: The Hong Kong University of Science and Technology, Hong Kong SAR, China · Hong Kong Generative AI Research and Development Center (HKGAI), Hong Kong SAR, China

Abstract

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.

Figures & tables

Figure 1. Motivation of our work:

x

-axis is the distance between the central bucket

\mathcal{B}_{central}

with its

k

-step neighbor

\mathcal{N}_{k}

, where

k\in[0,14]

and

k

is the hamming distance, and

y

-axis is the selectivity in

\mathcal{N}_{k}

. We use

5

datasets, each containing

10

queries, for demonstration. As

\mathcal{N}_{k}

becomes more distant from

\mathcal{B}_{central}

, the selectivity of the neighbor decreases, which means that closer neighbor are more likely to contain points that satisfies the similarity query in context of cardinality estimation.

Notation	Description
$N$	The cardinality / size of dataset
$d$	The dimensionality of dataset
$\mathcal{D}\in\mathbb{R}^{N\times d}$	The dataset
$x,q\in\mathbb{R}^{d}$	query / data point in $d$ -dimensional space
$\tau\in\mathbb{R}$	distance threshold in vector range search
$dist_{s}$	distance function in $s$ space

Table 1. List of Key Notations.

Dataset	Domain	#Objects	Dimension	Test Size
SIFT	image	1M	128	1000
Glove	text	2M	300	2000
FastText	text	1M	300	1000
GIST	image	1M	960	1000
YouTube	video	0.34M	1770	340

Table 2. Statistics of Datasets

Dataset	Method	Mean	90th	95th	99th	Max
SIFT	CE4HD: MRCE 1%	2.11	3.33	4.39	8.25	71
	CE4HD: MRCE 10%	1.59	2.34	2.95	4.56	13.22
	SimCard: GL+	6.2	11.24	18	56.78	537.3
	Sampling 1%	12.3	35	66	158	585
	Dynamic Prober	1.56	2.25	3	6	21.5
	Dynamic Prober-PQ	1.69	2.56	3.6	7.5	51

Table 3. Performance: Q-Error Distribution

Figure 2. Efficiency: Time of Offline Estimator Construction (include all phase of construction of each methods)

Figure 3. Dynamic Prober: Break down time of offline construction, containing all

3

phases

Method	SIFT1M	Glove	FastText	GIST	YouTube
MRCE $1\%$	6.4	4.2	4.2	3.9	4.8
SimCard	49.1	53.4	46.8	66.4	72.3
Sampling $1\%$	89	217	113	206	391
DynamProber	59	235	138	51	77
DynamProber-PQ	46	213	121	33	58

Table 4. Efficiency: Time of Online Estimation (ms)

Figure 4. Dynamic Prober V.S. Dynamic Prober-PQ: Speedup

Figure 5. Parameter Study -

\epsilon

: Accuracy and Efficiency

Figure 6. Dynamic Prober: Dynamic Update Efficiency (

10\%

data for initial framework construction and

90\%

data for framework update)

Figure 7. Dynamic Prober: Dynamic Update Accuracy (The shadowed bars refers to the case of dynamic data updates, where

10\%

data is used for initial framework construction and

90\%

data is used for framework updates.)

Dataset	Method	Mean	90th	95th	99th	Max
SIFT	CE4HD: MRCE 1%	2156	8656	13398	16668	16668
	CE4HD: MRCE 10%	12	22	33	75	784
	Dynamic Prober	1.56	2.25	3	6	33
Glove	CE4HD: MRCE 1%	3800	12479	19971	31957	31957
	CE4HD: MRCE 10%	3801	12479	19971	31957	31957
	Dynamic Prober	2.88	4.67	7	17.4	223

Table 5. Competitors: Dynamic Update Accuracy (

10\%

data for initial framework construction and

90\%

data for update)

MultiCard: Multiple Attribute Cardinality Estimation via Deep Learning
Oct 19, 2026Mobina Koochaknia, Maryam Ramezani, Mohammad Hasan Shafaat
Sharif University of Technology, Tehran, Iran
Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation
Oct 4, 2026Barak Gorodissky, Tal WagnerKernel Methods
Tel Aviv University
Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
Oct 27, 2025Ved Danait, Srijan Das, Sujoy BhoreRandomized Sketching Kernel Density Estimation
Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India. · Department of Computer Science & Engineering and Centre for Machine Intelligence & Data Science (CMINDS), Indian Institute of Technology Bombay, Mumbai, India.

Oct 19, 2026J/K move · Enter open · S save

MultiCard: Multiple Attribute Cardinality Estimation via Deep Learning

Mobina Koochaknia, Maryam Ramezani, Mohammad Hasan Shafaat

Sharif University of Technology, Tehran, Iran

Open paper AskPDF arXiv

Cardinality estimation is essential for query optimization, but most existing learned estimators focus on a single predicate type, such as string LIKE clauses or numerical range filters. In practice, analytical workloads often combine both types, while the accuracy of string estimators tends to decrease with longer patterns. We introduce MultiCard, a comprehensive learned cardinality estimator that unifies LIKE predicates and numerical filters within a single end-to-end architecture. By combining a Transformer for long-range sparse patterns with an LSTM for short, frequent patterns, MultiCard achieves robust pattern modeling. In parallel, a numerical encoder integrates catalog histograms and structural predicate features, enabling the model to dynamically assess histogram estimation accuracy across different operators and data skew conditions. A final Transformer layer captures interactions among heterogeneous predicates before a multilayer perceptron predicts query cardinalities. We also introduce UPCI, a workload generator that produces length-balanced LIKE patterns, multi-column numerical predicates, and exact cardinality labels for training and evaluation. Experiments on five real-world datasets show that, for string-only workloads, MultiCard achieves the best or near-best Q-error across all datasets compared with state-of-the-art methods. For mixed multi-attribute queries, MultiCard reduces PostgreSQL's mean Q-error by up to 16 times while maintaining an inference latency below 5 ms.

Abstract

Explore similar work

MultiCard: Multiple Attribute Cardinality Estimation via Deep Learning

Locality Sensitive Hashing for p-Exponential Kernels with Applications to Density Estimation

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation