arXiv:2604.04603v1 [cs.DB] 6 Apr 2026
Cardinality Estimation for High Dimensional Similarity Queries with Adaptive Bucket Probing Zhonghan Chen
Qintian Guo
The Hong Kong University of Science and Technology Hong Kong SAR, China [email protected]
The Hong Kong University of Science and Technology Hong Kong SAR, China [email protected]
Ruiyuan Zhang
Xiaofang Zhou
Hong Kong Generative AI Research and Development Center (HKGAI) Hong Kong SAR, China [email protected]
The Hong Kong University of Science and Technology Hong Kong SAR, China [email protected]
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.
PVLDB Reference Format: Zhonghan Chen, Qintian Guo, Ruiyuan Zhang, and Xiaofang Zhou. Cardinality Estimation for High Dimensional Similarity Queries with Adaptive Bucket Probing. PVLDB, 14(1): XXX-XXX, 2020. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/OscarC9912/simQ_hd_card_estimator.
1
INTRODUCTION
In relational database systems[9], cardinality estimation[6, 8, 10, 11, 16, 32, 44, 45] is an important component of query optimization[3,
This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 14, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX
13] that has been studied for decades, which provides a fast estimation towards the number of output rows of the query, in order to select the query execution plan of the smallest latency. Recently, with the prevalence of vector database[4, 15, 19, 20, 25, 27– 29, 40, 41, 43] and semantic operators[2, 26], cardinality estimation for similarity query in the high dimensional space (CE4HD) [17, 18, 23, 30, 31, 33, 38, 39, 42], has become popular in database research, where we aim to efficiently estimate the number of points 𝑥 that are within distance threshold 𝜏 ∈ R from query point 𝑞 ∈ R𝑑 , given a range query (𝑥 ∈ R𝑑 , 𝜏 ∈ R). In terms of application, cardinality estimator of similarity query can be used to optimize the execution plan of semantic operators that interacts with large language models[5, 7, 12, 24, 36], where we can efficiently estimate the number of interactions with LLM without actual execution. Recent works on CE4HD[18, 33, 38, 39] primarily utilize deep neural networks (DNN) to predict cardinality given similarity queries. Technically, these approach generates a feature representation derived from the query vector, the distance threshold, and various dataset properties. This representation is then used to train a learned model, which in turn is employed to estimate the cardinality of vector similarity queries. However, learned approach suffers from several key disadvantages in practice. Firstly, the performance of DNN-based predictors relies heavily on the quality of training data, whose performance degrades dramatically if training data is not properly tailored. Secondly, the DNN-based estimators require the offline construction that takes substantial amount of time. For example, SimCard[33] partitions the dataset into smaller clusters (e.g. 100-200 clusters), where the training label is computed with respect to each cluster, and an estimation model will be trained for each of them, in order to derive the estimation for the current local area. For this pipeline, even with performant GPUs, such process is still time-consuming and requires many computational resources. Thirdly, DNN-based estimators suffer from a destitute of explainability, and exhibits instability, demonstrating large performance discrepancies across different datasets. Motivated by the aforementioned disadvantages of using deep neural networks or learning-based frameworks, we aim to design a lightweight solution that can perform well in both static and dynamic scenarios, with theoretical guarantees to support its robustness and effectiveness. Generally speaking, our primary design guideline is that the estimator should be light-weighted and requires little computational
Notation 𝑁 𝑑 D ∈ R𝑁 ×𝑑 𝑥, 𝑞 ∈ R𝑑 𝜏∈R 𝑑𝑖𝑠𝑡𝑠 B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 N𝑘 I Q C P
resources, so that the framework will be efficient for offline construction, online estimation, as well as large-scale dynamic data updates. To achieve these objectives, our framework is built upon the locality sensitive hashing (LSH)[1], which is a light-weighted vector index for approximate nearest neighbor (ANN) search, with extra optimization for improving efficiency with product quantization and progressive sampling. In ANN search, the multi-probe LSH[21] claims that: given a query that is hashed into a particular bucket containing its nearest neighbor, it is highly probable that adjacent buckets also contain the nearest neighbor of the query, which is the result of hard boundary problem in LSH. In cardinality estimation of similarity query in high dimensional space, we observe a similar tendency, which is demonstrated in Figure 1. The overall intuition and motivation illustrated in Figure 1 is that as the neighboring buckets become more distant, the possibility for a neighbor to contain the points within the distance threshold decreases. The intuition here will be formalized and discussed in Section 4.3. Motivated by this observation, we propose a neighboring-based adaptive bucket probing strategy for efficient cardinality estimation for similarity queries. Technically, given a query Q = (𝑥 ∈ R𝑑 , 𝜏 ∈ R), we firstly use LSH functions to find the central hash bucket B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 of the query, and then we adaptively probe the N𝑘 , which is the 𝑘-th step neighbor of B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 , where N𝑘 consists of all hash buckets whose hash code is at 𝑘 distance away in hamming space. In addition, the maximum value of 𝑘 is determined by the number of hash functions in the LSH index. In cardinality estimation for high dimensional similarity queries in high dimensional space, the distance computation is the bottleneck for efficiency. We further mitigate the bottleneck from two perspectives: 1). employing progressive sampling to reduce the number of distance computations, and 2). leveraging asymmetric distance computation in product quantization to improve the efficiency of distance calculation. A primary characteristic of cardinality estimation is that queries are associated with distance thresholds of widely varying magnitudes: some thresholds may yield only a few results, while others can return thousands of qualifying points. In the bucket probing scheme with LSH index, the magnitudes of distance threshold determines if distant neighbors should be probed or estimating within B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 is sufficient. However, the challenge is that 𝜏 is unknown before query arrives, which means we need to efficiently understand the magnitude of 𝜏 online dynamically. To tackle the challenge, we design a selectivity-based early stopping strategy to make our algorithm adaptive to distance thresholds at various magnitudes, where the early stopping conditions are bounded with theoretical guarantee. The major contributions of paper are as follows: • Design: we propose a locality-sensitive hashing (E2LSH) based framework to answer the cardinality estimation problem in high dimensional Euclidean space with problem-specific optimization. • Adaptive Probing: we design an efficient neighboring-based adaptive bucket probing strategy to dynamically probe the hash buckets and adjust the number of buckets to explore given distance thresholds at different magnitudes, according to a selectivity based early termination condition with theoretical guarantee. • Optimization: we integrate problem-specific optimization with two aspects. We develop an adaptive progressive sampling strategy to reduce the number of distance computation needed and apply
Description The cardinality / size of dataset The dimensionality of dataset The dataset query / data point in 𝑑-dimensional space distance threshold in vector range search distance function in 𝑠 space hash bucket that a point being mapped the 𝑘-Step Neighbor to B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 Locality-Sensitive Hashing Index Product Quantization Index An array storing all hash code of hash table Neighbor Lookup Table Table 1: List of Key Notations.
the asymmetric distance in product quantization (PQ) to improve the efficiency of distance computation. • Data Updates: we further leverage the advantage of our framework to support large-scale data updates, where we provide detailed explanation and algorithms for updating each of the component of the framework and experimental evaluations. The paper is organized as follows. Section 2 formally defines the problem and introduces the necessary preliminaries of our framework. Section 3 reviews recent advances in cardinality estimation for similarity search. Section 4 presents the core ideas of our framework along with tailored pseudocode for each component of the proposed algorithms. Section 5 extends the framework to handle dynamic data updates. Section 6 provides an extensive experimental evaluation of the algorithms. Finally, Section 7 concludes the paper and outlines three promising directions for future research.
2 PRELIMINARIES 2.1 Problem Definition Vector similarity search is a fundamental operation in a wide range of machine learning and data analysis applications, such as information retrieval, recommendation systems, and computer vision. Definition 1 (Similarity Search). Given a vector dataset D ∈ R𝑁 ×𝑑 , a range query (𝑞, 𝜏), where 𝑞 ∈ R𝑑 and 𝜏 ∈ R, and a distance function 𝑑𝑖𝑠𝑡, the vector similarity search returns all the 𝑥 ∈ D, whose 𝑑𝑖𝑠𝑡 (𝑞, 𝑥) ≤ 𝜏; that is {𝑥 |𝑑𝑖𝑠𝑡 (𝑥, 𝑞) ≤ 𝜏, 𝑥 ∈ D}. This formulation captures a broad class of similarity search problems under various distance metrics (e.g., Euclidean, cosine, Manhattan). It is often referred to as a range query in geometric or metric space indexing. Definition 2 (Cardinality Estimation for Similarity Search). Given a vector dataset D ∈ R𝑁 ×𝑑 , a range query (𝑞, 𝜏), where 𝑞 ∈ R𝑑 and 𝜏 ∈ R, and a distance function 𝑑𝑖𝑠𝑡 (·, ·), cardinality estimation for similarity search gives the number of data point in D whose distance to 𝑞 are no greater than 𝜏, i.e., |{𝑥 |𝑑𝑖𝑠𝑡 (𝑥, 𝑞) ≤ 𝜏, 𝑥 ∈ D}|. 2
SIFT
0.7
FastText Query 1 Query 2 Query 3 Query 4 Query 5 Query 6 Query 7 Query 8 Query 9 Query 10
0.6
Selectivity
0.5 0.4 0.3 0.2 0.1 0.0
0
2
4
6
8
Neighbor Distance
10
12
14
GloVe300 Query 1 Query 2 Query 3 Query 4 Query 5 Query 6 Query 7 Query 8 Query 9 Query 10
0.06 0.05 0.04 0.03 0.02
GIST Query 1 Query 2 Query 3 Query 4 Query 5 Query 6 Query 7 Query 8 Query 9 Query 10
0.06 0.05 0.04 0.03 0.02
0.06 0.04
0.01
0.01
0.02
0.00
0.00
0.00
0
2
4
6
8
Neighbor Distance
10
12
14
0
2
4
6
8
Neighbor Distance
10
12
14
YouTube Query 1 Query 2 Query 3 Query 4 Query 5 Query 6 Query 7 Query 8 Query 9 Query 10
0.08
Query 1 Query 2 Query 3 Query 4 Query 5 Query 6 Query 7 Query 8 Query 9 Query 10
0.10 0.08 0.06 0.04 0.02 0.00
0
2
4
6
8
Neighbor Distance
10
12
14
0
2
4
6
8
Neighbor Distance
10
12
14
Figure 1: Motivation of our work: 𝑥-axis is the distance between the central bucket B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 with its 𝑘-step neighbor N𝑘 , where 𝑘 ∈ [0, 14] and 𝑘 is the hamming distance, and 𝑦-axis is the selectivity in N𝑘 . We use 5 datasets, each containing 10 queries, for demonstration. As N𝑘 becomes more distant from B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 , 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. In the research of cardinality estimation for similarity search, previous works emphasized on one[23, 30, 42] or multiple[18, 33, 38, 39] distance functions, such as hamming distance, angular distance, edit distance, Jaccard distance, as well as Euclidean distance. In our work, we focus on the estimation in Euclidean space.
hash table, where vectors are assigned a unique hash code, based on distance proximity. Typically, in context of ANNS in Euclidean space, a LSH index contains 𝐿 hash tables, where each uses 𝐾 hash functions, and form a (𝐾 − 𝐿) LSH scheme. After understanding the basic idea of how locality sensitive hashing index works, now let’s define two extended concepts that will be essential for understanding the core of our framework.
Definition 3 (Euclidean Distance). The Euclidean distance, or L2 distance, between two vectors 𝑥, 𝑦 ∈ R𝑑 , is computed by the number of distinct tokens at the corresponding position, which is formally formulated as: 𝑑 ∑︁ 𝑑𝑖𝑠𝑡𝐸𝑢𝑐𝑙𝑖𝑑𝑒𝑎𝑛 (𝑥, 𝑦) = (𝑥𝑖 − 𝑦𝑖 ) 2 .
Definition 5 (Central Bucket B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 ). In a hash table, given a family of LSH functions: {ℎ 1, ℎ 2, ..., ℎ 𝑁 }, a central bucket B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 of a data point 𝑥 ∈ R𝑑 is defined as the hash bucket that the query vector 𝑥 ∈ R𝑑 directly hashed to. The hash code of B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 is:
𝑖=1
B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 = (ℎ 1 (𝑥), ℎ 2 (𝑥), .., ℎ 𝑁 (𝑥)).
2.2
LSH and Product Quantization
Definition 6 (Hamming Distances). The hamming distance, between two vectors 𝑥, 𝑦 ∈ R𝑑 , is computed by the number of distinct tokens at the corresponding position, which is formally formulated as: 𝑑 ∑︁ 𝑑𝑖𝑠𝑡ℎ𝑎𝑚𝑚𝑖𝑛𝑔 (𝑥, 𝑦) = (𝑥 [𝑖] == 𝑦 [𝑖])
Locality-Sensitive Hashing. Locality-Sensitive Hashing (LSH) is a prestigious vector index, which is widely used approximate nearest neighbor search. The core property of LSH is that closer points have larger probability of collision than those distant points. Formally, the property is defined as following:
𝑖=1
Definition 4. [34] Given a distance 𝑟 ≥ 0 and an approximation ratio 𝑐 > 1, a LSH function family H = {ℎ : R𝑑 → R} is considered (𝑟, 𝑐𝑟, 𝑝 1, 𝑝 2 )-sensitive if ∀𝑜 1, 𝑜 2 ∈ D: (1) if ||𝑜 1, 𝑜 2 || ≤ 𝑟 , then 𝑃𝑟 [ℎ(𝑜 1 ) = ℎ(𝑜 2 )] ≥ 𝑝 1 , (2) if ||𝑜 1, 𝑜 2 || > 𝑐 · 𝑟 , then 𝑃𝑟 [ℎ(𝑜 1 ) = ℎ(𝑜 2 )] ≤ 𝑝 2 .
Definition 7 (𝑘-Step Neighbor of B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 ). Given a central bucket B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 , the 𝑘-step neighbor of the central bucket is a set of hash buckets, denoted as N𝑘 = {N𝑘1, N𝑘2, ..., N𝑘𝑖 }, where the hash code of each N𝑘𝑖 is a hash bucket satisfying 𝑑𝑖𝑠𝑡ℎ𝑎𝑚𝑚𝑖𝑛𝑔 (B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 , N𝑘𝑖 ) == 𝑘
Different distance functions, such as L𝑝 , Jaccard distance, uses different LSH functions to represent the distance proximity relations. In this work, we focus on the Euclidean space. A typical LSH family for Euclidean space in E2LSH is defined as follows:
Product Quantization. Product quantization[14] is a popular index used in approximate nearest neighbor search in high dimensional space, whose core idea is to compress vectors of full length into compacted form to make it memory-friendly. Now, we briefly demonstrate the process of product quantization and explain the part that will be utilized in our work. Technically speaking, a vector 𝑥 ∈ R𝑑 will be firstly split into 𝑀 subvectors 𝑥 = (𝑥 1, 𝑥 2, ..., 𝑥 𝑀 ), 𝑑 where each of these subvectors is of dimension 𝑀 and 𝑀 divides 𝑑 should be satisfied; then all vectors in the dataset will be divided in 𝑀 subspace, where each subspace consists of all subvectors of the corresponding index. For each of the 𝑀 subspace, PQ conducts clustering algorithm, like KMeans, to form 𝐾 numbers of centroids of the subspace, where each (sub)vector is assigned with the closest centroid. After deriving the centroids and point assignment of each subspace, each vector can be represented as codebook vector of length 𝑀, like 𝑥 = (3, 2, ..., 8), where each of the 𝑀 value represent the identification of the closest centroid of that subspace.
𝑎® · 𝑜® + 𝑏 ⌋, 𝑊 where 𝑜® is the vector representation of a data point in D, 𝑎® ∈ R𝑑 is a 𝑑-dimensional vector whose entries are sampled independently from 2-stable distribution (standard normal distribution), 𝑊 is a predefined integer, and 𝑏 ∈ R is uniformly sampled from [0,𝑊 ]. ℎ𝑎,𝑏 (𝑜) = ⌊
Basic LSH Indexing. In this part, we will go through the basic index construction process of locality sensitive hashing in approximate nearest neighbor search. Firstly, we have a family of locality sensitive hashing functions H = {ℎ 1, ℎ 2, ..., ℎ 𝑁 }, then 𝑘 numbers of functions will be sampled from H , which forms a composite hash functions 𝑔 and the hash value of vector 𝑣 is computed as 𝑔(𝑣) = (ℎ 1 (𝑣), ℎ 2 (𝑣), ..., ℎ𝑘 (𝑣)). And this process constructs a single 3
Conversely, vectors can also be represented as the concatenation of the series of centroids in each of the 𝑀 subspaces. In PQ, as each vector is compressed and represented by a codebook, the distance computation between different vectors can be more efficient and facilitated. Overall, there are two schemes of distance computation in product quantization, referred to as symmetric distance computation (SDC) and asymmetric distance computation (ADC). Specifically, SDC will compute the distance between two vectors based on their quantized vector, which is mathematically represented as: √︄∑︁ ˆ 𝑑 (𝑥, 𝑦) = 𝑑 (𝑞(𝑥), 𝑞(𝑦)) = 𝑑 (𝑞 𝑗 (𝑥), 𝑞 𝑗 (𝑦)) 2,
which emphasized on the estimation in angular space. It firstly partitions the dataset with hyperplane LSH, then, it uniformly samples from promising buckets, according to the hamming distance of different buckets. Formally, the aforementioned process is formalized Í𝐾
𝑗
SimCard[33]. SimCard is a deep neural network based estimator for high-dimensional spaces that adopts a global–local structure for cardinality estimation. Specifically, it applies K-Means to partition the dataset and employs PCA for dimensionality reduction. For each cluster, a local estimation model is trained to predict the query cardinality within that partition. However, evaluating a query across a large number of local models (e.g., 100) can be computationally expensive. To mitigate this, a global model is introduced to identify the most promising local regions for cardinality estimation. The models take as input a set of features, including the query vector, the distance threshold, and some properties of the dataset. The framework is novel in its global–local architecture; however, it also inherits several common drawbacks of learning-based approaches. In particular, the performance of the estimator is highly dependent on the quantity and quality of training data, and insufficient or low-quality data can significantly degrade accuracy. Moreover, in practice, the framework comprises hundreds of neural networks serving as local estimators, which makes it impractical and inefficient to support large-scale dataset updates.
whose advantage is that, in each subspace, the distance between any two codebook vectors can be precomputed, tackling the challenge that the queries are unknown. Despite the convenience and efficiency in computation, 𝑆𝐷𝐶 suffers from a low accuracy in distance approximation, and it can rarely be used in tasks requiring high precision. On contrast, ADC improves the shortcoming of 𝑆𝐷𝐶 by not quantizing the query vector, which means that the query vector remains with full precision. Mathematically, 𝐴𝐷𝐶 is computed as: √︄∑︁ 𝑑ˆ(𝑥, 𝑦) = 𝑑 (𝑥, 𝑞(𝑦)) = 𝑑 (𝑥 𝑗 , 𝑞 𝑗 (𝑦)) 2 . 𝑗
The tradeoff is that we will not be able to pre-compute a universal distance table for all queries, as queries are unknown, which slightly damages the efficiency. However, we will still be able to compute the distance between each subvectors of the query and codebook vectors of each subspace, so that the further distance computations can still refer to the distance table. Considering the precision requirement in cardinality estimation, as well as approximate nearest neighbor search, 𝐴𝐷𝐶 will be utilized in our work and will be further discussed in the optimization section.
3
𝐶 𝑘 (𝐼 )
𝑞 𝑘 with a random variable: 𝑍 = 𝑘=1 𝐾 ·𝑝 (𝑥 ) , where 𝐶𝑞 (𝐼 ) is the number of points in buckets at distance 𝐼 and 𝐾 represents the number of hash tables. Most importantly, the normalization factor 𝑝 (𝑥) represents the collision probability that some point 𝑥 lands in a bucket at hamming distance 𝐼 from 𝑞 with randomly chosen hash functions. Lastly, the random variable will be sampled for 𝑆 times 𝑍 1, 𝑍 2, ..., 𝑍𝑆 and estimation is taken as the average.
SRCE / MRCE[18]. SRCE and MRCE represent recent advances in cardinality estimation for high-dimensional spaces. SRCE is a simple estimator that exploits fundamental properties of similarity queries, whereas MRCE incorporates machine learning techniques to enhance prediction accuracy. Both methods leverage knowledge of the existing dataset, referring to as reference objects, operating under the assumption that distance function of a given query point may resemble that of certain points already present in the dataset. SRCE estimates cardinality using a single reference object, generating a pool of reference objects while balancing pool size and diversity. During online estimation, SRCE identifies the reference point whose distance function most closely matches that of the query. Computing the distance function online is time-consuming; to address this, SRCE employs a vector index to pre-compute distance functions during the offline phase. Despite this efficiency improvement, the need for pre-computation makes SRCE inherently query-dependent, which is a notable limitation of the algorithm. MRCE employs multiple reference objects to estimate cardinality, aiming to reduce SRCE’s reliance on a vector index for precomputing distance functions. With multiple references, MRCE trains a deep neural network to evaluate the contribution of each reference, and the weighted sum of these contributions produces the final cardinality estimate. In terms of network architecture, the model takes as input a data point 𝑝𝑖 , a reference object 𝑟𝑖 , the distance between 𝑝𝑖 and 𝑟𝑖 , and the distance threshold. During the first training phase, an encoder–decoder model is trained to featurize 𝑝𝑖
EXISTING SOLUTIONS
The cardinality estimation problem is a classic problem in database for decades, where numerous solutions have been proposed in relational database[6, 8, 10, 11, 16, 32, 44, 45]. In vector database, the cardinality estimation problem is to estimate the number of qualified points in a similarity search. We will review several major works that are closely related to this research. Sampling Method. The most naive and trivial approach for solving a cardinality problem for similarity search is uniform sampling, whose convention is to uniformly sample 1% or 10% of the dataset to derive the estimation for the entire dataset. And the method is commonly used as the competitor in most of the recent works on the problem[18, 33, 42]. While sampling-based approaches offer a straightforward means to estimate the cardinality, they suffer from two major limitations. First, the resulting estimates are often coarse and lack accuracy. Second, their efficiency is poor: to achieve accuracy comparable to other methods, sampling based techniques require the evaluation over a substantially larger amount of points, leading to significant efficiency degradation. Hyperplane LSH Approach[42]. It proposed a density estimator using the locality sensitive hashing and importance sampling, 4
4.3
and 𝑟𝑖 , and the resulting embeddings are concatenated with the remaining distance features to compute the final weights for each reference object, which are then combined to produce the cardinality estimate. MRCE reduces its reliance on the vector index; however, obtaining a sufficient amount of diverse training data to achieve satisfactory estimation performance is time-consuming. Moreover, while SRCE and MRCE are novel in leveraging existing dataset knowledge, in practice, dozens of values must be pre-computed to ensure both efficiency and accuracy.
Design Objective. To tackle the cardinality estimation of similarity queries in high dimensional space, we aim to develop a distance threshold aware bucket probing strategy, which takes advantage of the information (like selectivity) of those explored hash buckets, to adaptively adjust the number of buckets to be explored. In terms of efficiency, the goal is that our probing strategy will be able to give an accurate estimation while probing a tiny proportion of the dataset to minimize the number of distance computation required, which is considered as an expensive part during the online estimation. To achieve such objective, we are motivated by the multi-probe LSH[21] in approximate nearest neighbor search (ANNS), which claims that, given a central bucket B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 in a hash table, its neighboring buckets that are at few distance away (measured by the distance between hash codes in hamming space), are also probable to contain the neighbors to the query. In this work, we further explore and utilize this property to tackle the estimation problem, and we will provide detailed reasoning and justification for the design of each component of our framework.
4 OUR FRAMEWORK 4.1 Overview The core idea is to partition the dataset using locality-sensitive hashing (LSH), which enables efficient pruning of unpromising points while quickly identifying candidates in close proximity to a given query (Section 4.2). Beyond the LSH index, we introduce a neighboring-based probing strategy (Section 4.3) to adaptively adjust the number of points explored depending on the magnitude of distance threshold (Section 4.4), thereby enhancing the efficiency of estimation. Furthermore, we introduce two extra optimizations. First, we use the progressive sampling to reduce the number of required distance computations while providing strong probabilistic guarantees on accuracy (Section 4.5). Second, we leverage asymmetric distance in product quantization[14] to further accelerate distance computation in high dimensional space (Section 4.6). The pseudocode of the neighboring probing strategy with progressive sampling is demonstrated in Algorithm 1, where 𝑓 _𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟 (Line 12): Algorithm 2 and 𝑓 _𝑐𝑒𝑛𝑡𝑟𝑎𝑙 (Line 7): Algorithm 3. In addition to static dataset, our framework also supports data updates, where each component of our framework can be updated easily, even with large scale of new data. And we provide the algorithm for updating the framework in Section 5.
4.2
Neighboring-based Probing Strategy.
Challenges: Numerous Hash Buckets. In locality sensitive hashing (LSH), in order to achieve a decent performance in space partitioning while capturing distance proximity among millions of points, it is a common practice to apply multiple LSH functions to better capture the distance distribution[34, 35]. However, the usage of multiple LSH functions give rise to a magnificent amount of hash buckets in the hash table. Example 4.1. Given one hash table, we use 10 hash functions, where each of the function produces around 4 different values, and theoretically, there are around 410 = 1, 048, 576 distinct hash buckets being created in the hash table. Furthermore, if 14 hash functions are used, there will be around 414 = 268, 435, 456 buckets. Therefore, it will be extremely inefficient to probe the neighbors at bucket level for the following reasons: firstly, it is inefficient to probe with single buckets, where the neighbor look-up / indexing time will incur large latency during online estimation and it will be infeasible of estimating a meaningful number of buckets to be explored; secondly, according to our preliminary study, the number of points at each bucket can be highly imbalanced, which means numerous buckets might contain very few points (like 3 or 10) and thus degrades the locality information of the dataset.
Dataset Partitioning
Dataset partitioning, or segmentation, is a common preprocessing strategy in cardinality estimation for high-dimensional vectors. Its necessity can be summarized as follows: (1) Modern vector datasets often contain millions of points, making direct cardinality estimation over the entire space both challenging and prone to significant errors [33]. Consequently, partitioning the dataset into smaller subsets is beneficial for improving estimation accuracy and efficiency. (2) In cardinality estimation, points that are sufficiently distant from the query cannot serve as viable candidates, making their exploration unnecessary. So, partitioning the dataset is advantageous for focusing on the most promising candidates, thereby improving efficiency by pruning unpromising points.
Our Approach. Considering the disadvantages of directly probing across numerous hash buckets, we propose a 𝑘-Step Neighboringbased Probing strategy, whose fundamental notion is from the multiprobe locality sensitive hashing. Firstly, let’s re-clarify the notion of a 𝑘-step neighbor N𝑘 of a hash bucket B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 , which is a set of hash buckets, whose hash codes are at 𝑘 distance away from the B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 in the hamming space. Now, our general probing framework is that, given a query vector 𝑞, we firstly estimate its central hash bucket B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 (Line 7), then we explore those neighboring buckets N1 , N2 , .., N𝐾 ′ (Lines 9–16) and terminates if either met:
Our work utilizes the locality-sensitive hashing (LSH) to partition the dataset. As the work focuses on the Euclidean space, the LSH function is naturally selected as the E2LSH[1]. In addition, in order to support the angular space, the framework can be easily adopted with hyperplane LSH, which is also the choice of a similar work under angular space[42].
• number of points explored meets maximum value (Lines 10–11) • global probing termination flag is triggered (Lines 14–15), where 𝐾 ′ ≤ 𝐾 and the maximum of 𝐾 is the number of hash function (Algorithm 1). 5
points to be explored based on the magnitude of distance threshold, where more points will be explored for larger thresholds, while less points for smaller thresholds. What’s more, as previously discussed, threshold is known only at the online estimation phase and there is no such a golden rule to determine if the threshold is large or small, which even differs between different points in the dataset, as well as datasets with various distributions. In short, our algorithm is expected to efficiently determine the number of points to explore during the online estimation. Now, let’s discuss our general design of adaptive prober in detail.
Algorithm 1: Neighboring Based Probing 𝑑 1 INPUT: Query: (𝑥 ∈ R , 𝜏 ∈ R), LSH Index: I; Fast
Neighbor Lookup Table P, estimation function: 𝑓 ; OUTPUT: Estimated Cardinality |A| 3 |A| ← 0; 4 𝑛𝑉 𝑖𝑠𝑡𝑒𝑑 ← 0; (diff from actual computation) 5 PTF ← 𝑛𝑜𝑛𝑒 (global probe terminate flag); 6 ℎ𝑎𝑠ℎ𝑐𝑜𝑑𝑒 ← I.𝑐𝑜𝑚𝑝𝑢𝑡𝑒𝐻𝑎𝑠ℎ𝐶𝑜𝑑𝑒 (𝑥); 7 |A|+ = 𝑓𝑐𝑒𝑛𝑡𝑟𝑎𝑙 (𝑥, 𝜏, I, ℎ𝑎𝑠ℎ𝑐𝑜𝑑𝑒); 8 𝑛𝐻𝑎𝑠ℎ𝐹𝑢𝑛𝑐𝑠 ← I.𝑛_𝑙𝑠ℎ_𝑓 𝑢𝑛𝑐𝑠; 9 for 𝑛𝐷𝑒𝑔𝑟𝑒𝑒 ∈ 𝑟𝑎𝑛𝑔𝑒 (1, 𝑛𝐻𝑎𝑠ℎ𝐹𝑢𝑛𝑐𝑠) do 10 if 𝑛𝑉 𝑖𝑠𝑡𝑒𝑑 ≥ 𝑚𝑎𝑥𝑉 𝑖𝑠𝑡 then 11 break; 2
nDeg_card, PTF = 𝑓𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟 (𝑛𝐷𝑒𝑔𝑟𝑒𝑒, ℎ𝑎𝑠ℎ𝑐𝑜𝑑𝑒, 𝑥, 𝜏, P); |A|+ = nDeg_card; if PTF then break;
12 13 14 15
update 𝑛𝑉 𝑖𝑠𝑡𝑒𝑑;
16 17
A Naive Approach. As aforementioned, one of the objective is to achieve accurate estimation while exploring a tiny proportion (like 1%) of dataset. A straightforward approach is to explore from the central bucket B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 , and then consecutively proceed to 𝑘th neighbor N𝑘 at farther distances, until 𝑥% · |𝐷 | numbers of points are explored. Considering points in the same hash buckets have similar proximity distribution, instead of explicitly computing distances of all points from the query, we uniformly sample 𝑥1 %·|N𝑘 | points to compute the distance. In order to enable the prober aware of the magnitude of distance threshold, we determine if further neighborhood N𝑘+1 should be explored based on the selectivity of the current neighborhood, where the termination condition is triggered if selectivity is under some threshold. Comment: The uniform sampling and selectivity-based termination strategy partially tackles the challenges in efficiency and being adaptive to deal with thresholds at various magnitudes. However, the sampling strategy and termination condition is highly heuristic, which cannot provide any rigorous theoretical guarantee regarding the confidence of error bound in estimation; and there is still noticeable error in estimation. To reduce the estimation error and reduce the number of point computations, we propose our first optimization that utilizes progressive sampling, with theoretical guarantee, to adaptively adjust the number of points for exploration within a neighbor N𝑘 , which is discussed in Section 4.5. As dimensionality increases, the complexity of distance computation increases. In order to mitigate the impact from the dimensionality of vectors, the second optimization is to apply asymmetric distance computation (ADC) to estimate the real distance between two points, which is discussed in Section 4.6.
return |A|;
Example 4.2. Given a query vector 𝑞 ∈ R𝑑 , it is easy to compute the hash code of the central bucket B𝑐 = [0, 2, 1, 3], where we use one hash table with four hash functions. In our hash table, there are a set of distinct hash buckets: • N1 : [1, 2, 1, 3], [0, 2, 1, 4] • N2 : [2, 3, 1, 3], [0, 1, 2, 3], [1, 2, 1, 4] • N3 : [0, 3, 2, 4], [1, 2, 2, 2], [1, 1, 0, 3] • N4 : [1, 1, 2, 2], where each hash bucket contains points sharing the hash code, and we sort these hash codes by its distance to the hash code of central bucket. In our probing strategy, points in the same N𝑘 are grouped together as a whole. Then, our strategy is to derive the estimation with N𝑘 by increasing 𝑘 until certain stopping conditions are met.
4.4
Adaptive Bucket Probing
Challenges: Adaptiveness of Threshold. Designing an efficient and accurate probing strategy is inherently challenging. In the context of cardinality estimation, exploring too many or too few points can result in poor efficiency or inadequate accuracy, respectively, making it crucial to balance this trade-off. As previously discussed, a similarity search query includes not only a vector point but also a distance threshold. The threshold can be large enough to encompass over 10% of the dataset, necessitating the exploration of many neighbors or buckets, or it can be very small, covering only a few points—e.g., 2 or 5—where examining a single bucket suffices. Furthermore, for datasets with complex distance distributions, exploring too few buckets can cause a significant drop in accuracy, as the cardinality may increase dramatically with even a slight increase in the distance threshold. Therefore, determining the appropriate number of points to explore is of critical importance. Given this challenges, our probing algorithm is expected to be adaptive to distance thresholds at different magnitude, which means that our algorithm is expected to automatically adjust the number of
4.5
Adaptive Progressive Sampling with Guarantee
Progressive sampling is an adaptive sampling method, comparing with uniform sampling. The motivation is that some neighborhoods N𝑘 might contain a large amount of points, where a small proportion of them is representative enough to reflect its distribution and sampling more points is unnecessary. What’s more, progressive sampling allows sampling for multiple times, which better avoids outlier cases and further improves accuracy. Besides the progressive sampling, we design our algorithm to be adaptive to thresholds of different magnitudes, where we design two termination conditions, the first of which terminates sampling with greater sample size of the current N𝑘 and the second of which terminates the entire neighbor probing process. Both termination 6
conditions can be formulated as a function of the sampling parameters and selectivity in neighbor N𝑘 , and we will explain these concepts in detail with following section and Algorithm 2. Given a 𝑘-th step neighbor containing 𝑁 points, we define a sampling schedule as 𝑠 1, 𝑠 2, 𝑠 3, .., 𝑠𝑇 , where 𝑠𝑖+1 = 2 · 𝑠𝑖 (Line 28), and we denote the number of sampled points to be 𝑤 = 𝑠𝑖 · 𝑁 . In practice, we also set an upper bound for the maximum sampling rate as 𝑠𝑚𝑎𝑥 , where 𝑠𝑇 ≤ 𝑠𝑚𝑎𝑥 , to avoid exploring infinitely (Line 11). To achieve a theoretical bound for the confidence of estimation, we derive the upper bound of error as (Line 19): √︂ √︂ 𝑎 𝑎 2 𝜇𝑢𝑝𝑝𝑒𝑟 = ( 𝑝ˆ + + ) , 2𝑤 2𝑤 and derive the lower bound as follows (Line 20): √︂ √︂ ! 2 𝑎 2𝑎 𝑎 − 𝑝ˆ + − }. 𝜇𝑙𝑜𝑤𝑒𝑟 = 𝑚𝑎𝑥 {0, 9𝑤 2𝑤 18𝑤
Algorithm 2: 𝑓𝑛𝑒𝑖𝑔ℎ𝑏𝑜𝑟 : Estimate the cardinality of N𝑘 with Progressive Sampling INPUT: nDegree (distance w. B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 ), Query: (𝑥 ∈ R𝑑 , 𝜏 ∈ R), LSH Index: I; Neighbor Lookup Table P; 2 PARAMS: Initial Sampling Rate: 𝑠 1 , Max Sampling Rate: 𝑠𝑚𝑎𝑥 , Error bound: 𝜖; Confidence Param: 𝑎 = 𝑙𝑛(1000) 3 OUTPUT: Estimated Cardinality |A| 4 |A| ← 0; 5 ℎ𝑎𝑠ℎ𝑐𝑜𝑑𝑒 ← I.𝑐𝑜𝑚𝑝𝑢𝑡𝑒𝐻𝑎𝑠ℎ𝐶𝑜𝑑𝑒 (𝑥); 6 C ← P.𝑓 𝑖𝑛𝑑 (𝑛𝐷𝑒𝑔𝑟𝑒𝑒, ℎ𝑎𝑠ℎ𝑐𝑜𝑑𝑒); (Hashcode of Neighbors); 7 O ← I.𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒 (𝐶); (nDegree Neighbor IDs); 8 𝐶𝑆𝑅 = 𝑠 1 ; (current sampling rate); 9 𝑃𝑇 𝐹 ← 𝑓 𝑎𝑙𝑠𝑒; (global probing termination flag); 10 𝑄 𝑎𝑙𝑙 , 𝑄 𝑞𝑢𝑎𝑙𝑖 𝑓 𝑖𝑒𝑑 ← 0, 0; 11 while 𝐶𝑆𝑅 ≤ 𝑠𝑚𝑎𝑥 do 12 O ′ ← 𝑠𝑎𝑚𝑝𝑙𝑒𝑟 (O, 𝐶𝑆𝑅); (sampled points) 13 𝑤, 𝑤 ′ ← |O ′ |, 0; (current sample size, sample qualified) 14 for 𝑝 ∈ O ′ do 15 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒𝑐𝑢𝑟𝑟 ← 𝑑𝑖𝑠𝑡 L2 (𝑥, 𝑝); 16 if 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒𝑐𝑢𝑟𝑟 ≤ 𝜏 then 17 𝑤 ′ + +; 1
where 𝑤 denotes the number of sampled points. And 𝑝ˆ (Line 18) represent the selectivity of the current round of sampling, formally, it is defined as: 𝑤′ , 𝑝ˆ = 𝑤 ′ where 𝑤 represent the number of points that are qualified within distance threshold, which is evaluated iteratively (Lines 14–17), and 𝑤 = 𝑠𝑖 · 𝑁 refers to sample size (Line 13). Additionally, in Lines 14–17, 𝑑𝑖𝑠𝑡 L2 computes the distance between two points in L2 space. In our framework, 𝑑𝑖𝑠𝑡 L2 can be calculated as Definition 3 or approximate it with asymmetric distance in PQ[14], which will be discussed in Section 4.6. Now, let 𝜖 denote the error bound parameter 𝜖. For example, 𝜖 = 0.0001. In our probing scheme, we terminate from sampling more points at the current neighborhood if the first condition (1) met, which means we are already confident regarding the error bound of our estimation (Lines 26–27) and there is no need to increase the sample size; and the second condition (2) is even stronger, which indicates that there is no need to explore neighbors at further (hamming) distances (Lines 23–25): 𝜇 upper − 𝑝ˆ ≤ 𝜖 ∧ 𝑝ˆ − 𝜇lower ≤ 𝜖 𝜇 upper < 𝜖
′
18 19 20 21 22 23 24 25
𝑄 𝑎𝑙𝑙 + = 𝑤; 𝑄𝑞𝑢𝑎𝑙𝑖 𝑓 𝑖𝑒𝑑 + = 𝑤 ′ ; if 𝜇𝑢𝑝𝑝𝑒𝑟 < 𝜖 then 𝑃𝑇 𝐹 ← 𝑡𝑟𝑢𝑒; break;
27
if 𝜇𝑢𝑝𝑝𝑒𝑟 − 𝑝ˆ ≤ 𝜖 ∧ 𝜇𝑙𝑜𝑤𝑒𝑟 − 𝑝ˆ ≤ 𝜖 then break;
28
𝐶𝑆𝑅 ← 2 · 𝐶𝑆𝑅;
26
𝑄
(1)
𝑓 𝑖𝑒𝑑 |A| = |O| · 𝑞𝑢𝑎𝑙𝑖 ; 𝑄𝑎𝑙𝑙 30 return |A|, 𝑃𝑇 𝐹 ;
29
(2)
Lastly, we provide reasoning of the termination conditions. Firstly, we assume that, the probability of failure (larger than the error bound) for our estimation to be 𝑃𝑅 𝑓 𝑎𝑖𝑙 (say 0.1%), which means that the probability of success is 𝑃𝑅𝑠𝑢𝑐𝑐𝑒𝑠𝑠 = 1 − 𝑃𝑅 𝑓 𝑎𝑖𝑙 and we denote the constant 𝑎 = ln( 𝑃𝑅 1 ). And we may interpret two stopping 𝑓 𝑎𝑖𝑙 conditions (1) (2) as the upper and lower bound of the error for our estimation, which provides a guarantee with confidence 𝑃𝑅𝑠𝑢𝑐𝑐𝑒𝑠𝑠 . The formula is deduced with Chernoff bound.
4.6
𝑝ˆ ← 𝑤𝑤 ; √︁ √︁ 𝑎 2 𝑎 𝜇𝑢𝑝𝑝𝑒𝑟 = ( 𝑝ˆ + 2𝑤 + 2𝑤 ) ; √︃ √︁ 𝑎 2 2𝑎 𝑎 𝜇𝑙𝑜𝑤𝑒𝑟 = 𝑚𝑎𝑥 {0, 𝑝ˆ + 9𝑤 − 2𝑤 − 18𝑤 };
Algorithm 3: 𝑓𝑐𝑒𝑛𝑡𝑟𝑎𝑙 : Estimate in Central Bucket The algorithm describes how the estimation is executed in the central bucket: B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 . 2 The algorithm is in naive brute force manner, where it iteratively computes the distance between query and point, and the point is counted if the distance is no greater than the query threshold. 1
PQ-based Distance Estimation
As previously introduced, product quantization[14] is an efficient and memory-friendly vector index that is popular in approximate nearest neighbor search. In our work, we leverage the asymmetric distance computation (ADC) in PQ to further accelerate the distance computation, which is a costly part in the online estimation process. When query arrives, we firstly compute the distance between each (sub)vector of the query with the centroid of codebook vectors,
where we store all these values in a fast lookup table T (Algorithm: 4); then, for all future distance computation, we directly refer to the table for better efficiency (Algorithm 5). It is expected that ADC accelerates distance computation, especially for high dimensional vectors, while introducing little estimation errors. 7
Algorithm 4: PQ-ADC: Construct Fast Lookup Table
Algorithm 6: Construct Neighbor Lookup Table
𝑑 1 INPUT: PQ Index: Q, Query Vector 𝑥 ∈ R ;
1
PARAMS: 𝑀: number of subspaces, 𝐾: number of clusters; 3 OUTPUT: Query Specific Fast Lookup Table T ; 4 Initialize fast lookup table T ; 5 𝑥 1 , 𝑥 2 , ..., 𝑥 𝑀 = 𝑑𝑖𝑣𝑖𝑑𝑒_𝑠𝑢𝑏𝑠𝑝𝑎𝑐𝑒 (𝑥); 6 for 𝑠𝑝𝐼 𝐷 ∈ [1, 2, ..., 𝑀] do 7 for 𝑐𝐼 𝐷 ∈ [1, 2, ..., 𝐾] do 𝑠𝑝𝐼 𝐷 8 Retrieve the centroid vector: 𝑣𝑒𝑐𝑐𝐼 𝐷 ; 9 Compute the distance: 𝑠𝑝𝐼 𝐷 𝑑𝑖𝑠𝑡 = 𝑙2_𝑑𝑖𝑠𝑡 (𝑥𝑠𝑝𝐼 𝐷 , 𝑣𝑒𝑐𝑐𝐼 𝐷 ); 10 T [𝑠𝑝𝐼 𝐷] [𝑐𝐼𝐷] = 𝑑𝑖𝑠𝑡;
2
INPUT: C: Array of unique hash codes; PARAMS: 𝑀: distance greater than it will not be stored; 3 OUTPUT: T : Efficient Neighbor Lookup Table; 4 for 𝑖 ∈ [0, C.𝑠𝑖𝑧𝑒) do 5 for 𝑗 ∈ [0, C.𝑠𝑖𝑧𝑒) do 6 𝑑 = 𝑑𝑖𝑠𝑡ℎ𝑎𝑚𝑚𝑖𝑛𝑔 (C [𝑖], C [ 𝑗]); 7 if 0 < 𝑑 ≤ 𝑀 then 8 T [𝑖].update{(𝑑, 𝑗)};
2
11
9
the problem will become more challenging for large scale data updates, where the data distribution will change significantly. Existing frameworks are primarily learned frameworks[18, 33], where they train DNNs with various types of labeled data, and the model will be used for the cardinality estimation. In terms of data update, current frameworks often applies the following strategies:
return T ;
Algorithm 5: PQ-ADC: Distance Estimation INPUT: PQ Index: Q, Fast Lookup Table: T , Point ID: 𝑝𝑖𝑑 (data points whose distance to be computed with query); 2 PARAMS: 𝑀: number of subspaces, 𝐾: number of clusters; 3 COMMENT: Refer to our GitHub repository for a more compiler friendly and efficient implementation.; 4 𝑑𝑖𝑠𝑡𝑎𝑑𝑐 ← 0; 5 for 𝑠𝑝𝐼 𝐷 ∈ [1, 2, ..., 𝑀] do 6 𝑑𝑖𝑠𝑡𝑎𝑑𝑐 + = T [𝑠𝑝𝐼𝐷] [Q.𝑐𝑜𝑑𝑒𝑏𝑜𝑜𝑘.𝑝𝑖𝑑];
1
7
(1) Directly use the original trained model for estimation. (2) Re-compute labels of training data, and re-train the model. However, both data update scheme suffers from some disadvantages. For the first approach, the model performance degrades little when few new data is added, but the performance degrades significantly as the scale updates increase, because the training labels are no longer valid under the updated dataset. The second approach is rigorous, however, it is time-consuming to re-compute the training labels and re-train the deep neural networks for each update. For example, in SimCard [33], we need to firstly re-compute the cluster-wise training labels, and then we need to re-train over 100 deep neural networks (each data partition has a local DNN for estimation) to achieve satisfying results; in [18], it re-generates all or partial of training labels, which contain magnificent amount of intermediate data, to retrain the model to support updates. Fortunately, leveraging the advantage of locality sensitive hashing, we are able to efficiently support large scale of data updates without significant accuracy degradation with the updated framework. Overall, there are three major components of the framework to be updated: 1. locality sensitive hashing index I; 2. product quantization index Q (optional); 3. neighboring bucket lookup table P. Now, I will provide algorithm for updating each of component, and performance of updated framework will be reported in Section: 5.
return 𝑑𝑖𝑠𝑡𝑎𝑑𝑐 ;
4.7
Efficient Bucket Neighbor Look-Up
The estimation is expected to be efficient. However, in our neighboring based probing paradigm, one of the efficiency bottleneck is to efficiently retrieve all the hash buckets / points, whose hash code is at certain distance from B𝑐𝑒𝑛𝑡𝑟𝑎𝑙 . The challenge is that a hash table usually contains magnificent amount of buckets, like over 100, 000, and it is costly to iteratively retrieve them during the online estimation. A natural solution is to pre-compute it offline. Specifically, we construct a neighbor lookup table P, where each index (position) of P stores the neighboring information of corresponding hash code in C. At each index 𝑖 ∈ [0, C.𝑠𝑖𝑧𝑒) of P, a dictionary structure is used, where we use the distances between hash codes as the key and the hash code id will be stored as the value. For example, P [𝑖] [𝑘] returns the index of all hash codes, which are 𝑘 distance away from the hash code C [𝑖]. The process is described in Algorithm 6. Additionally, according to our preliminary study, we observe that it is unnecessary to store the neighbor information with large distance, which might not be accessed in our probing scheme. To reduce the cost of storage, we store neighbor with distance no greater than 𝑀 at each index.
5
return T ;
Update LSH Index. (Algorithm 7) We firstly iteratively compute the hash code of newly added points with original hash functions. However, a negligible but beneficial step is to re-calculate the value of 𝑊 (refer to Definition: 2.2) of the LSH function, which is determined by the minimum and the maximum value of all hash codes. If 𝑊 is not properly updated, quality of updated hash table degrades. Update PQ Index. (Algorithm 8) With those initial data, a product quantization (PQ) index has already been constructed. For newly added data, identifying the codebook of new points and iteratively updated the centroids, of affected cluster, at each subspace is sufficient for updating the product quantization index. In other words, such a simple updating method is efficient and achieves little degradation in terms of estimation. The index update rule applies for
DYNAMIC DATA UPDATES
Supporting data updates is practical but challenging in modern vector database, where it requires dynamically updating the constructed index as rebuilding from scratch is inefficient. Technically, 8
Algorithm 7: Dynamic Updates: LSH Index
Algorithm 9: Dynamic Updates: Neighbor Lookup Table
INPUT: Existing LSH Index: I, New Points: V = {𝑣𝑖 }; OUTPUT: Updated LSH Index: I; 3 H ← I.𝑙𝑠ℎ_𝑓 𝑢𝑛𝑐𝑡𝑖𝑜𝑛𝑠; (division excluded) 4 𝐻𝑎𝑠ℎ𝐶𝑜𝑑𝑒𝑠_𝑛𝑒𝑤 ← []; 5 𝐻𝑎𝑠ℎ𝐶𝑜𝑑𝑒𝑠_𝑝𝑟𝑒𝑣 ← I.𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒 (); (division excluded) 6 for 𝑣 𝑖 ∈ V do 7 𝐻𝑎𝑠ℎ𝐶𝑜𝑑𝑒𝑠.𝑎𝑑𝑑 (𝑣𝑖 );
INPUT: Constructed table: T , Array of existing hash codes: C, Array of new hash codes: C1 ; 2 PARAMS: 𝑀: distance greater than it will not be stored; ′ 3 OUTPUT: T : Updated Neighbor Lookup Table; 4 𝑠 1 , 𝑠 2 = C.size(), C1 .size(); 5 𝑠𝑎𝑙𝑙 = 𝑠 1 + 𝑠 2 6 C ← C + C1 ; ′ 7 T ← T .extend(C1 ); 8 for 0 ≤ 𝑖 < 𝑠 1 do 9 for 𝑠 1 ≤ 𝑗 < 𝑠𝑎𝑙𝑙 do 10 𝑑 = 𝑑𝑖𝑠𝑡ℎ𝑎𝑚𝑚𝑖𝑛𝑔 (C [𝑖], C [ 𝑗]); 11 if 0 < 𝑑 ≤ 𝑀 then 12 T ′ [𝑖].update{(𝑑, 𝑗)}; 13 T ′ [ 𝑗].update{(𝑑, 𝑖)};
1
1
2
𝐻𝑎𝑠ℎ𝐶𝑜𝑑𝑒𝑠 ← 𝐻𝑎𝑠ℎ𝐶𝑜𝑑𝑒𝑠_𝑛𝑒𝑤 + 𝐻𝑎𝑠ℎ𝐶𝑜𝑑𝑒𝑠_𝑝𝑟𝑒𝑣; ′ ← 𝑛𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒𝑊 (𝐻𝑎𝑠ℎ𝐶𝑜𝑑𝑒𝑠); ′ 10 𝐻𝑎𝑠ℎ𝐶𝑜𝑑𝑒𝑠 ← 𝑑𝑖𝑣𝑖𝑑𝑒 (𝐻𝑎𝑠ℎ𝐶𝑜𝑑𝑒𝑠,𝑊 ); 11 Hash Table: 𝑇 ← 𝑐𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡 (𝐻𝑎𝑠ℎ𝐶𝑜𝑑𝑒𝑠); ′ 12 update I: 𝑇 , 𝑊 ; 8
9 𝑊
Algorithm 8: Dynamic Updates: PQ Index
for 𝑠 1 ≤ 𝑖 < 𝑠𝑎𝑙𝑙 do for 𝑠 1 ≤ 𝑗 < 𝑠𝑎𝑙𝑙 do 16 𝑑 = 𝑑𝑖𝑠𝑡ℎ𝑎𝑚𝑚𝑖𝑛𝑔 (C [𝑖], C [ 𝑗]); 17 if 0 < 𝑑 ≤ 𝑀 then 18 T ′ [𝑖].update{(𝑑, 𝑗)};
14
INPUT: Existing PQ Index: Q, New Points: V = {𝑣𝑖 }; 2 OUTPUT: Updated PQ Index: Q; 3 for 𝑣 ∈ V do 4 𝑣 1, 𝑣 2, ..., 𝑣 𝑀 = divide_subspace(v); 5 for 𝑠𝑝𝐼 𝐷 ∈ [1, 2, ..., 𝑀] do 6 𝑣𝑠𝑝𝐼 𝐷 assigned to closest cluster;
1
7 8
15
19
Update Q; 1. In each subspace, update centroid of updated cluster;
queries[18, 31, 33, 39]. All of these datasets are acquired from the original source without extra processing.
most of the datasets, however, for some datasets whose cardinality explodes for a tiny increase in distance threshold, the simple update rule aforementioned brings extra estimation error.
Dataset SIFT Glove FastText GIST YouTube
Update Neighbor Lookup Table. (Algorithm 9) Let’s quickly review the functionality of neighbor look-up table P. Technically, given a B𝑐𝑒𝑛𝑡𝑎𝑙 and a distance 𝑘, P enables the framework to efficiently retrieve all the hash buckets whose distance are at 𝑘 from B𝑐𝑒𝑛𝑡𝑎𝑙 in hamming space. Specifically, the process is just to compute the hamming distance between new hash codes and original hash codes, as well as the pair-wise distance among those new hash codes, which will be updated in the neighbor look-up table.
6
Domain image text text image video
#Objects 1M 2M 1M 1M 0.34M
Dimension 128 300 300 960 1770
Test Size 1000 2000 1000 1000 340
Table 2: Statistics of Datasets Our Methods. Dynamic Prober and Dynamic Probe-PQ are our methods involved in the evaluation, where dynamic prober-PQ is a version utilizing asymmetric distance computation in product quantization for point-wise distance computation.
EXPERIMENTS
We conduct extensive experiments on real world dataset for evaluation and analysis of our methods. We implement the Dynamic Prober 1 in C++ and compiled with g++ using -Ofast optimization. All experiments are conducted on a Ubuntu sever with Intel(R) Xeon(R) Gold 6248 CPU (160 threads) and 1.5 TB RAM. For model training requiring GPU, we use ×1 NVIDIA A100 GPU (80GB, PCIE).
6.1
return T ′ ;
Competitors. We compare the following approaches: • SimCard [33]: a learning based cardinality estimation framework for similarity query featuring space segmentation and query segmentation. We adopt author’s source code and follow the default settings for data generation and model training. • MRCE [18]: a learning based framework utilizing the knowledge of existing data called reference objects for cardinality estimation. In order to comprehensively evaluate the performance of MRCE, we apply two settings by using 1% · |D| and 10% · |D | number of reference objects. We adopt author’s source code and follow the default settings for data generation and model training. • Sampling 1%: We uniformly sample 1% of the data for estimation. Though simpleness, it is an effective approach and are widely used in the research of cardinality estimation problem, where
Experimental Settings
Datasets. We conduct the evaluation with 5 real-world vector dataset, whose statistics are shown in Table 2. All of these datasets are commonly used in the research of approximate nearest neighbor search[22, 34, 35, 37] and cardinality estimation of similarity 1 https://github.com/OscarC9912/simQ_hd_card_estimator
9
[18, 33] utilize uniform sampling of 1% data as the competitor for sampling approach as well.
Dataset
Evaluation Metrics. For accuracy, we follow the convention in recent research [18, 33], where we report the mean Q-Error as well as its distributions (90%, 95%, 99%, and 100% percentile). The Q-Error is defined as following:
SIFT
ˆ 𝑐) = 𝑄-𝑒𝑟𝑟𝑜𝑟 (𝑐,
ˆ 𝑐) 𝑚𝑎𝑥 (𝑐, , ˆ 𝑐) 𝑚𝑖𝑛(𝑐,
Glove
where 𝑐 and 𝑐ˆ are real / estimated cardinality, respectively. Query Selection. In general, we generate the queries for evaluation following the conventions in recent works [18, 33, 39], where we partially adopted the code for data preprocessing from [18, 39]. Specifically, for each dataset, we uniformly sample 𝐾 = 𝑚𝑖𝑛{0.1% · |D |, 1000} of points as query vector, and for each of the query vector, we sample from a geometric sequence of 40 values within the range of [1, 𝑚𝑖𝑛(20000, 1% · |D|)] as the ground truth cardinality, which bounds the smallest and largest cardinality. For each of the ground truth cardinality 𝑐, we find the minimum distance threshold 𝜏 that yields 𝑐 results, where 𝜏 is the distance threshold in the query.
6.2
FastText
GIST
Estimation Accuracy
YouTube
Table 3 shows the Q-Error distribution of our methods as well as those competitors. The best results are highlighted in bold. Overall, we make the following observations: 1). Our method and reference CE4HD: MRCE are the most performant algorithms in terms of accuracy, and our dynamic prober achieves the best performance for the vast majority of evaluations. 2). Dynamic Prober (w./w.o PQ) outperforms all baseline methods (CE4HD: MRCE, SimCard, Sampling) in terms of mean and 90% Q-error. 3). As for the 95%, 99%, and maximum Q-error, the dynamic prober outperforms other method except for two datasets: SIFT and FastText, where our Q-error is slightly higher than the optimal. 4). The product quantization accelerated dynamic prober achieves similar or even better accuracy than the method without acceleration across most of the dataset. However, for GloVe and FastText, we can observe some degradation in terms of accuracy when distance is estimated with product quantization. The degradation in performance can be attributed to property of dataset, where the dataset suffers from a sudden and significant change in distance distribution, as revealed by previous work[18]; and the estimation will bring some more noticeable degradation in Q-error for a slight error in distance estimation. 5). SimCard and Sampling 1% achieves the worst performance for all the time. Despite sampling 1% of the dataset introduced significant error, its performance is relatively more stable than SimCard.
6.3
Method CE4HD: MRCE 1% CE4HD: MRCE 10% SimCard: GL+ Sampling 1% Dynamic Prober Dynamic Prober-PQ CE4HD: MRCE 1% CE4HD: MRCE 10% SimCard: GL+ Sampling 1% Dynamic Prober Dynamic Prober-PQ CE4HD: MRCE CE4HD: MRCE 10% SimCard: GL+ Sampling 1% Dynamic Prober Dynamic Prober-PQ CE4HD: MRCE 1% CE4HD: MRCE 10% SimCard: GL+ Sampling 1% Dynamic Prober Dynamic Prober-PQ CE4HD: MRCE 1% CE4HD: MRCE 10% SimCard: GL+ Sampling 1% Dynamic Prober Dynamic Prober-PQ
Mean 2.11 1.59 6.2 12.3 1.56 1.69 4.92 4.45 242.9 11.2 2.9 4.19 2.31 2.06 50.6 12.87 1.99 2.59 10.62 14.42 17.5 12.43 4.4 4 3.82 3.89 7.72 13.3 2.56 2.08
90th 3.33 2.34 11.24 35 2.25 2.56 9.26 9.05 417.1 27 4.78 7.37 4.18 3.46 86.8 35 3 4.82 9.64 9.59 37.8 35 8.2 7.53 7.67 8.16 15.69 36 4.31 3.5
95th 4.39 2.95 18 66 3 3.6 12.31 11.84 1040 54 7 11.77 5.18 4.33 197 66 5 7.5 18.64 18.57 72.4 66 14 10.71 9.5 10.39 30.25 63 6 5
99th 8.25 4.56 56.78 158 6 7.5 34.33 27.67 5920 138 19.4 27 8.14 7.25 728 158 11.5 15 158.87 244.36 213.5 158 33 20.8 15.72 17.11 92 163 12.5 10.2
Max 71 13.22 537.3 585 21.5 51 742.67 587.67 899691 565 223 282.5 32.41 40.42 10000 585 235.5 98.5 2200.85 2699.32 2471.8 728 378 728 70.62 49.33 423 512 26 26
Table 3: Performance: Q-Error Distribution
of our method is much lower than that of all other approaches, making it the most efficient in terms of offline construction. For our method, the offline construction latency stems from three components: (i) building the LSH index, (ii) generating the neighbor look-up table, and (iii) optionally constructing a product quantization (PQ) index for asymmetric distance estimation. Importantly, no additional overhead is incurred in processing the dataset itself. As shown in Figure 3, the time required for both LSH index construction and neighbor look-up table generation is indeed small, while the optional PQ index constitutes the dominant portion of the offline construction latency for our method.
6.4
Efficiency: Online Estimation
Table 4 reports the latency of online estimation for our method and the baselines. We highlight three key observations. 1). Among learning-based approaches, CE4HD: MRCE achieves the lowest latency by leveraging both the efficiency of neural networks and reference objects. 2). Among non-learning-based approaches, Dynamic Prober demonstrates competitive latency, performing comparably to sampling-based methods while offering superior efficiency in high-dimensional datasets such as GIST (960D) and YouTube (1770D). 3). The incorporation of asymmetric distance computation further enhances efficiency of our method, contributing additional acceleration during online estimation.
Efficiency: Offline Data Preparation and Model Construction
Learning-based methods require substantial time both for constructing training datasets and for the training phase itself, even when leveraging modern GPUs. In short, building a learned model for prediction is highly time-consuming. By contrast, our estimator—based on locality sensitive hashing (LSH)—can be constructed with significantly less overhead. We quantitatively demonstrate this advantage in Figure 2, which clearly shows that the offline processing latency 10
Dynamic Prober-PQ
Ratio of Speedup 1.5
200
20000 15000
Ratio of Speedup
25000
Latency (ms)
Offline Processing Time (s)
Dynamic Prober
Data Preparation Model Training CE4HD-1% CE4HD-10% SimCard Dynamic Prober-PQ
30000
1.4
150
1.3
100
10000
1.2
50
5000
0 0
SIFT
GloVe
FastText
GIST
Datasets
SIFT
YouTube
GloVe
SIFT PQ Index Construction (Optional)
1.1
YouTube
GIST
GloVe
YouTube
250
35
1000 800
200
30
Latency (ms)
1200
25 20 15 10 5
600
200
150 100 50
0
8.0
400
0
FastText
40
Mean Q-Error
Segmented Processing Time (s)
1400
Neighbor Lookup Table
GIST
Figure 4: Dynamic Prober V.S. Dynamic Prober-PQ: Speedup
Figure 2: Efficiency: Time of Offline Estimator Construction (include all phase of construction of each methods) LSH Index Construction
FastText Dataset (ms)
4.0
2.0
0.8
0.6
Epsilon x1000
0.4
0.2
0.1
8.0
4.0
2.0
0.8
0.6
Epsilon x1000
0.4
0.2
0.1
Figure 5: Parameter Study - 𝜖: Accuracy and Efficiency SIFT
GloVe
FastText
GIST
Datasets
YouTube
SIFT1M 6.4 49.1 89 59 46
Glove 4.2 53.4 217 235 213
FastText 4.2 46.8 113 138 121
GIST 3.9 66.4 206 51 33
Segmented Latency (s)
Method MRCE 1% SimCard Sampling 1% DynamProber DynamProber-PQ
Initial Consutrction Update Consutrction
500
Figure 3: Dynamic Prober: Break down time of offline construction, containing all 3 phases YouTube 4.8 72.3 391 77 58
400 300 200 100 0
SIFT
GIST
GloVe
Datasets
FastText
YouTube
Table 4: Efficiency: Time of Online Estimation (ms)
6.5
Figure 6: Dynamic Prober: Dynamic Update Efficiency (10% data for initial framework construction and 90% data for framework update)
Efficiency: Asymmetric Distance Estimation
In this section, we present an ablation study evaluating the benefits of asymmetric distance computation with a product quantization index, with results shown in Figure 4. As illustrated, asymmetric distance computation improves computational efficiency, achieving a speedup of approximately ×1.6. Furthermore, the benefits of distance estimation increase with the dimensionality of the dataset, indicating that this approach is particularly advantageous for highdimensional datasets.
6.6
in progressive sampling; 2). necessity of exploring neighboring buckets that are most distant. In Figure 5, a larger value of 𝜖 demonstrates better efficiency, but the error can be more significant, as the estimator neither samples sufficient amount of points nor exploring neighbors that are distant enough. On the contrary, a smaller 𝜖 gives better accuracy but higher latency. However, it is worthwhile noticing that there is no need for the 𝜖 to be arbitrarily small. As we can observe from Figure 5, the mean Q-error no longer improves after some turning point, which varies among datasets and can be tuned for each dataset.
Parameter Study: Error Tolerance Value 𝜖
In this section, we investigate into how the hyperparameter 𝜖 influences the trade off between efficiency and accuracy, whose result is demonstrated with Figure 5. Before getting into the experimental result, let’s briefly review the functionality of the 𝜖. Theoretically, the parameter 𝜖 reflects the estimation error allowed. More practically, in our neighboring-based probing scheme, the 𝜖 controls the following features: 1). necessity of estimating with larger samples
6.7
Evaluation: Data Updates
In this section, we evaluate the performance of data update scheme. Generate Dynamic Dataset: In this experiment, different from updating hundreds of points in a million level dataset, we conduct the evaluation under a large-scale data update. Specifically, the 11
4 2 0
Q-Error Distribution
5
Static Dynamic
Mean Q-Error
Static Dynamic
90th Q-Error
Static Dynamic
95th Q-Error
Static Dynamic
99th Q-Error
Static Dynamic
Max Q-Error
is infeasible for practical purposes. To tackle this, in this evaluation, we directly use original models to estimate on the updated dataset. Evaluation of Efficiency: For dynamic prober, we use the algorithm update algorithms discussed in Section 5 to support data updating scheme, where we evaluate the accuracy and efficiency of data update. Specifically, Figure 6 demonstrates the efficiency of updating of our method, where we can make the following observations: 1). the initial construction of our framework takes very small amount of time, as the initial data is merely 10% of the dataset; and the time to update the constructed framework on 90% of the dataset takes higher but acceptable amount of time. In short, our approach takes a reasonable amount of time for updating large scale dataset based on the initial framework constructed with initial dataset.
0 10 0 40 20 0 400 200 0
SIFT
GIST
GloVe
FastText
Dataset
Evaluation of Accuracy: We conduct the evaluation for accuracy by comparing our dynamic update scheme with the static one, where we construct the framework with all the dataset, as well as our competitors aforementioned. Figure 7 demonstrates the comparison of Q-error distribution between static dataset and two stages update scheme, where we can observe that there is little degradation in accuracy with our updating scheme. What’s more, we can also observe some slight improvement in Q-error with the two stages construction, potentially due to better index construction. In short, our data updating algorithm will not incur noticeable degradation in the accuracy of estimation. Table 5 demonstrates how our competitors performs with a largescale dynamic data update scheme, whose prediction is estimated with the original model constructed by initial dataset. We can make the following observations: 1). overall, the Q-error is significantly higher than the static case, indicating that utilizing original model cannot provide accurate estimation under a large-scale data updating scheme; 2). utilizing a larger amount of reference objects (from 1% to 10%) cannot always guarantee a better performance for all the datasets, as the extra data included might contribute little to the training data and thus model performance, which also demonstrates that the performance of learning based model relies heavily on the quality of training data.
YouTube
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 SIFT
Glove
FastText
GIST
YouTube
Method CE4HD: MRCE 1% CE4HD: MRCE 10% Dynamic Prober CE4HD: MRCE 1% CE4HD: MRCE 10% Dynamic Prober CE4HD: MRCE 1% CE4HD: MRCE 10% Dynamic Prober CE4HD: MRCE 1% CE4HD: MRCE 10% Dynamic Prober CE4HD: MRCE 1% CE4HD: MRCE 10% Dynamic Prober
Mean 2156 12 1.56 3800 3801 2.88 48 27 1.99 2055 2055 4.51 840 840 2.0
90th 8656 22 2.25 12479 12479 4.67 156 82 3 6958 6958 8.22 3251 3251 3
95th 13398 33 3 19971 19971 7 237 115 5 10769 10770 14 4766 4766 4
99th 16668 75 6 31957 31957 17.4 361 172 11.5 16668 16668 37.8 5769 5769 8.5
Max 16668 784 33 31957 31957 223 515 482 122.5 16668 16668 292.5 5769 5769 31.5
Table 5: Competitors: Dynamic Update Accuracy (10% data for initial framework construction and 90% data for update)
7
CONCLUSION
In this paper, we study the problem of cardinality estimation for similarity search in high dimensional space. Leveraging the localitysensitive hashing index in approximate nearest neighbor search, we propose a new concept dynamic prober to adaptively probe the neighboring buckets to estimate the cardinality of similarity queries. What’s more, we further optimize the efficiency of algorithm by applying progressive sampling and the asymmetric distance computation in product quantization. We conduct extensive experiments demonstrating the superiority in performance of our approach. To conclude, we propose three potential future directions of our work: (1). explore a more unified non-learning framework supporting the estimation in different distance spaces; (2). apply our method to support optimization tasks in downstream tasks related to semantic operators or vector database; (3). explore other potential trainingless methods to estimate the cardinality of similarity queries.
dynamic dataset is constructed entirely based on previous static datasets D, where we uniformly sample 10% of D as the initial dataset, and use the rest of 90% of dataset for updating. In addition, queries are completely the same as queries in the static case. Select Competitors: In the evaluation of data updates, we select the MRCE1% and MRCE10%, which is most competitive framework in static scenario, as our major competitors. As a learning-based cardinality estimator, supporting a dynamic data update scheme can be mainly achieved by two approach: 1). directly utilize the original estimation model for updated data; 2). re-generate the training data (partial or complete) and re-train the model. In the evaluation for the offline construction time, we observed that constructing a new model can be time-consuming, and it is easy to infer that the reconstruction of a updated model is also time-consuming, which 12
REFERENCES
[30] Jianbin Qin, Yaoshu Wang, Chuan Xiao, Wei Wang, Xuemin Lin, and Yoshiharu Ishikawa. 2018. GPH: Similarity Search in Hamming Space. In ICDE. IEEE Computer Society, 29–40. [31] Jianbin Qin and Chuan Xiao. 2018. Pigeonring: A Principle for Faster Thresholded Similarity Search. Proc. VLDB Endow. 12, 1 (2018), 28–42. [32] Suraj Shetiya, Saravanan Thirumuruganathan, Nick Koudas, and Gautam Das. 2020. Astrid: Accurate Selectivity Estimation for String Predicates using Deep Learning. Proc. VLDB Endow. 14, 4 (2020), 471–484. [33] Ji Sun, Guoliang Li, and Nan Tang. 2021. Learned Cardinality Estimation for Similarity Queries. In SIGMOD Conference. ACM, 1745–1757. [34] Yao Tian, Xi Zhao, and Xiaofang Zhou. 2022. DB-LSH: Locality-Sensitive Hashing with Query-based Dynamic Bucketing. In ICDE. IEEE, 2250–2262. [35] Yao Tian, Xi Zhao, and Xiaofang Zhou. 2024. DB-LSH 2.0: Locality-Sensitive Hashing With Query-Based Dynamic Bucketing. IEEE Transactions on Knowledge and Data Engineering 36, 3 (2024), 1000–1015. https://doi.org/10.1109/TKDE. 2023.3295831 [36] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023. LLaMA: Open and Efficient Foundation Language Models. CoRR abs/2302.13971 (2023). [37] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search. Proc. VLDB Endow. 14, 11 (2021), 1964–1978. [38] Yaoshu Wang, Chuan Xiao, Jianbin Qin, Xin Cao, Yifang Sun, Wei Wang, and Makoto Onizuka. 2020. Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach. In SIGMOD Conference. ACM, 1197–1212. [39] Yaoshu Wang, Chuan Xiao, Jianbin Qin, Rui Mao, Makoto Onizuka, Wei Wang, Rui Zhang, and Yoshiharu Ishikawa. 2021. Consistent and Flexible Selectivity Estimation for High-Dimensional Data. In SIGMOD Conference. ACM, 2319–2327. [40] Weaviate. [n.d.]. Weaviate: An Open-Source Vector Database. https://weaviate. io/. Accessed: 2024-12-05. [41] Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data. Proc. VLDB Endow. 13, 12 (2020), 3152–3165. [42] Xian Wu, Moses Charikar, and Vishnu Natchu. 2018. Local Density Estimation in High Dimensions. In ICML (Proceedings of Machine Learning Research), Vol. 80. PMLR, 5293–5301. [43] Wen Yang, Tao Li, Gai Fang, and Hong Wei. 2020. PASE: PostgreSQL UltraHigh-Dimensional Approximate Nearest Neighbor Search Extension. In SIGMOD Conference. ACM, 2241–2253. [44] Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen, and Ion Stoica. 2020. NeuroCard: One Cardinality Estimator for All Tables. Proc. VLDB Endow. 14, 1 (2020), 61–73. [45] Zongheng Yang, Eric Liang, Amog Kamsetty, Chenggang Wu, Yan Duan, Xi Chen, Pieter Abbeel, Joseph M. Hellerstein, Sanjay Krishnan, and Ion Stoica. 2019. Deep Unsupervised Cardinality Estimation. Proc. VLDB Endow. 13, 3 (2019), 279–292.
[1] Alexandr Andoni. [n.d.]. LSH Algorithm and Implementation (E2LSH). https: //www.mit.edu/~andoni/LSH/. Accessed: 2025-08-28. [2] Muhammad Imam Luthfi Balaka, David Alexander, Qiming Wang, Yue Gong, Adila Krisnadhi, and Raul Castro Fernandez. 2025. Pneuma: Leveraging LLMs for Tabular Data Representation and Retrieval in an End-to-End System. Proc. ACM Manag. Data 3, 3 (2025), 200:1–200:28. [3] Surajit Chaudhuri. 1998. An Overview of Query Optimization in Relational Systems. In PODS. ACM Press, 34–43. [4] Chroma. [n.d.]. Chroma: The Open-Source AI Application Database. https: //www.trychroma.com/. Accessed: 2024-12-05. [5] DeepSeek-AI. 2024. DeepSeek-V3 Technical Report. CoRR abs/2412.19437 (2024). [6] Amol Deshpande, Minos N. Garofalakis, and Rajeev Rastogi. 2001. Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data. In SIGMOD Conference. ACM, 199–210. [7] Rohan Anil et al. 2023. Gemini: A Family of Highly Capable Multimodal Models. CoRR abs/2312.11805 (2023). [8] Lise Getoor, Benjamin Taskar, and Daphne Koller. 2001. Selectivity Estimation using Probabilistic Models. In SIGMOD Conference. ACM, 461–472. [9] PostgreSQL Global Development Group. 2024. PostgreSQL: The World’s Most Advanced Open Source Relational Database. https://www.postgresql.org/. Accessed: 2024-11-28. [10] Dimitrios Gunopulos, George Kollios, Vassilis J. Tsotras, and Carlotta Domeniconi. 2005. Selectivity estimators for multidimensional range queries over real attributes. VLDB J. 14, 2 (2005), 137–154. [11] Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, Zhengping Qian, Jingren Zhou, Jiangneng Li, and Bin Cui. 2021. Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. Proc. VLDB Endow. 15, 4 (2021), 752– 765. [12] al. Hugo Touvron et. 2023. Llama 2: Open Foundation and Fine-Tuned Chat Models. CoRR abs/2307.09288 (2023). [13] Yannis E. Ioannidis. 1996. Query optimization. ACM Comput. Surv. 28, 1 (March 1996), 121–123. https://doi.org/10.1145/234313.234367 [14] Hervé Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Trans. Pattern Anal. Mach. Intell. 33, 1 (2011), 117–128. [15] al. Jianguo Wang et. 2021. Milvus: A Purpose-Built Vector Data Management System. In SIGMOD Conference. ACM, 2614–2627. [16] Martin Kiefer, Max Heimel, Sebastian Breß, and Volker Markl. 2017. Estimating Join Selectivities using Bandwidth-Optimized Kernel Density Models. Proc. VLDB Endow. 10, 13 (2017), 2085–2096. [17] Kyoungmin Kim, Jisung Jung, In Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong. 2022. Learned Cardinality Estimation: An In-depth Study. In SIGMOD Conference. ACM, 1214–1227. [18] Hai Lan, Shixun Huang, Zhifeng Bao, and Renata Borovica-Gajic. 2024. Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects. Proc. VLDB Endow. 18, 3 (Nov. 2024), 544–556. https://doi.org/10.14778/3712221.3712224 [19] lancedb. [n.d.]. Developer-friendly, database for multimodal AI. https://lancedb. com/. Accessed: 2024-12-05. [20] Jie Li, Haifeng Liu, Chuanghua Gui, Jianyu Chen, Zhenyun Ni, and Ning Wang. 2019. The Design and Implementation of a Real Time Visual Search System on JD E-commerce Platform. arXiv:1908.07389 [cs.IR] [21] Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. 2007. MultiProbe LSH: Efficient Indexing for High-Dimensional Similarity Search. In VLDB. ACM, 950–961. [22] Yury A. Malkov and Dmitry A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Trans. Pattern Anal. Mach. Intell. 42, 4 (2020), 824–836. [23] Michael Mattig, Thomas Fober, Christian Beilschmidt, and Bernhard Seeger. 2018. Kernel-Based Cardinality Estimation on Metric Data. In EDBT. OpenProceedings.org, 349–360. [24] OpenAI. 2023. GPT-4 Technical Report. CoRR abs/2303.08774 (2023). [25] James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Survey of vector database management systems. VLDB J. 33, 5 (2024), 1591–1615. [26] Liana Patel, Siddharth Jha, Parth Asawa, Melissa Pan, Carlos Guestrin, and Matei Zaharia. 2024. Semantic Operators: A Declarative Model for Rich, AI-based Analytics Over Text Data. arXiv:2407.11418 [cs.DB] https://arxiv.org/abs/2407. 11418 [27] pgvector contributors. 2024. pgvector: Open-source extension for vector similarity search in PostgreSQL. https://github.com/pgvector/pgvector. Accessed: 2024-11-28. [28] pinecone. [n.d.]. Build knowledgeable AI. https://www.pinecone.io/. Accessed: 2024-12-05. [29] Qdrant. [n.d.]. Qdrant: High-Performance Vector Search at Scale. https://qdrant. tech/. Accessed: 2024-12-05. 13
8
APPENDIX
8.1
Definition: Chernoff Bound
Consider tossing an unfair coin for 𝑛 times, we have: • Observation: 𝑋𝑖 – The outcome of the 𝑖 th toss – 1 for Heads, 0 for Tails • True Probability: 𝑝 – The actual probability of obtaining Heads • Error parameter: 𝜖 – The margin of error for our estimation. The Chernoff Bounds are represented as following: ∑︁ 2 1 𝜖 𝑛 𝑃𝑟 𝑋𝑖 < 𝑝 − 𝜖 ≤ 𝑒𝑥𝑝 − 𝑛 2𝑝 ! ∑︁ 𝜖 2𝑛 1 𝑋𝑖 > 𝑝 + 𝜖 ≤ 𝑒𝑥𝑝 − 𝑃𝑟 𝑛 2𝑝 + 2𝜖3
14
8.2
Proof: Pr(𝑝 > 𝜇𝑢𝑝𝑝𝑒𝑟 ) ≥ 1 − 𝛿
Notation: • 1 − 𝛿: probability of bounding the upper bound of 𝑝 with 𝜇𝑢𝑝𝑝𝑒𝑟 • 𝑎 = ln 𝛿1 Want to Show: Pr(𝑃 < 𝜇 upper ) ≥ 1 − 𝛿 Prove the other side: Pr(𝑃 > 𝜇 upper ) ≤ 𝛿 √︂ 2 ! √︂ 𝑎 𝑎 𝑝ˆ + + 2𝑤 2𝑤
(1)
√︂ √︂ 𝑎 𝑎 𝑎 𝑎 = Pr 𝑝 > 𝑝ˆ + + +2 · 𝑝ˆ + 2𝑤 2𝑤 2𝑤 2𝑤
(2)
√︂ √︂ 𝑎 𝑎 2𝑎 𝑎 + > 𝑝ˆ + ≤ Pr 𝑝 − 2 𝑝ˆ + 2𝑤 2𝑤 2𝑤 2𝑤
(3)
√︂ 2𝑎 𝑎 √ 𝑎 ≤ Pr 𝑝 − 2 > 𝑝ˆ + 𝑝+ 2𝑤 2𝑤 2𝑤
(4)
Pr(𝑝 > 𝜇 upper ) = Pr 𝑝 >
" ≤ Pr
√ 𝑝−
√︂
𝑎 2𝑤
2
2𝑎 > 𝑝ˆ + 2𝑤
#
√︂ √ 𝑎 𝑎 2𝑎 = Pr 𝑝 − 2 𝑝 + > 𝑝ˆ + 2𝑤 2𝑤 2𝑤 "
√︂
≤ Pr 𝑝 − 2 "
√︂
= Pr −2 "
√︂
≤ Pr −2
≤ exp −
𝑎𝑝 𝑎 > 𝑝ˆ + 2𝑤 2𝑤
(6)
#
𝑎𝑃 𝑎 − > 𝑝ˆ − 𝑝 2𝑤 2𝑤 𝑎𝑝 > 𝑝ˆ − 𝑝 2𝑤
(5)
(7) # (8)
# (by Chernoff Bound)
! 𝑎𝑝 4 · 2𝑤 · 𝑤 1 = exp(𝑎) = exp(ln( )) = 𝛿 2·𝑝 𝛿
(10)
Therefore, we have shown that: Pr(𝑝 > 𝜇 upper ) ≤ 𝛿 which is equivalent to: Pr(𝑝 < 𝜇 upper ) ≥ 1 − 𝛿 To conclude, according to what we have proved, we are 1 − 𝛿 confident that the upper bound of real selectivity 𝑝 can be bounded by 𝜇𝑢𝑝𝑝𝑒𝑟 .
15