Distance Comparison Operations Are Not Silver Bullets in Vector Similarity Search: A Benchmark Study on Their Merits and Limits Zhuanglin Zheng, Yuxiang Zeng, Chenchen Liu, Yunzhen Chi, Binhan Yang, Yongxin Tong
arXiv:2604.02801v1 [cs.DB] 3 Apr 2026
SKLCCSE Lab, BDBC and IRI, Beihang University, Beijing, China {zzlin, yxzeng, 23371020, chiyz, yangbh, yxtong}@buaa.edu.cn Narrow Dimensionality Coverage: They are largely confined to the dimensionality range of 128–960, neglecting lower-dimensional and, particularly, ultra-highdimensional data common in embeddings from LLMs. • Insufficient Direct Comparison: They lack empirical comparisons between the state-of-the-art DCO methods. • Restricted Hardware Configuration: They typically use CPUs with SIMD disabled, which does not reflect the computing capabilities of a modern server. • Limited Application Scenario: They mainly focus on indistribution queries, overlooking practical scenarios like Out-of-Distribution (OOD) queries and index building. These limitations prevent a definitive answer to the previous question and motivate our work. To this end, we conduct a comprehensive benchmark of 8 DCO methods across 10 datasets and diverse hardware. Our evaluation reveals that these methods are not silver bullets. Their effectiveness is highly contingent, and their adoption requires careful consideration. Specifically, we have the following findings: (1) Dimensionality Sensitivity: Their performance is highly sensitive to data dimensionality. While they excel within a moderate range, their advantage degrades significantly outside of it, at times falling behind FDScanning by up to 20%–42%. (2) Robustness Dilemma: Existing methods face a dual challenge. On the one hand, they are vulnerable to OOD queries that are common in applications like multimodal retrieval. On the other hand, their efficiency gains are unstable across hardware. For instance, enabling SIMD can reduce or even reverse their advantage over FDScanning. (3) Benefit Beyond Query: An often-overlooked merit of DCO methods lies in accelerating index construction and data insertions by up to 64% and 63%, respectively. (4) No Universal Winner: There is no single dominant method. Their performance ranking varies drastically with data characteristics, query distribution, and hardware. Contribution. We make the following major contributions: • We present the first comprehensive benchmark for evaluating DCOs in vector similarity search. • Through extensive evaluation, we provide a detailed analysis of the merits and limitations of existing DCO methods. The in-depth analysis leads to the final answer: the recent algorithmic advancements in DCO, while promising, are not yet ready for production deployment.
Abstract—Distance Comparison Operations (DCOs), which decide whether the distance between a data vector and a query is within a threshold, are a critical performance bottleneck in vector similarity search. Recent DCO methods that avoid fulldimensional distance computations promise significant speedups, but their readiness for production vector database systems remains an open question. To address this, we conduct a comprehensive benchmark of 8 DCO algorithms across 10 datasets (with up to 100M vectors and 12,288 dimensions) and diverse hardware configurations (CPUs with/without SIMD, and GPUs). Our study reveals that these methods are not silver bullets: their efficiency is highly sensitive to data dimensionality, degrades under out-ofdistribution queries, and is unstable across hardware. Yet, our evaluation also demonstrates often-overlooked merits: they can accelerate index construction and data updates. Despite these benefits, their unstable performance, which can be slower than a full-dimensional scan, leads us to conclude that recent algorithmic advancements in DCO are not yet ready for production deployment.
•
Index Terms—Vector Database, Similarity Search, Benchmark.
I. I NTRODUCTION Vector similarity search is a fundamental component of modern data-intensive applications, including recommendation systems, search engines, and Retrieval-Augmented Generation (RAG). A central challenge in this domain is improving search efficiency. While the majority of research has focused on designing index structures, a recent and promising line of work optimizes efficiency at a more granular operator level. These studies [1]–[6] identify the Distance Comparison Operation (DCO) (which determines whether the distance between a data vector and a query vector is within a given threshold) as a critical efficiency bottleneck. Traditional vector database systems [7]–[9] often perform DCOs by exhaustively computing the full-dimensional distance, a naive method denoted as Full Dimension Scanning (“FDScanning” as short). In contrast, state-of-the-art methods [1]–[4] leverage techniques like hypothesis testing or prediction to scan only partial dimensions and infer the comparison result. These approaches have been reported to improve query throughput by 2–4× over FDScanning with almost no loss in recall. The impressive results raise a natural yet critical question: Are these new DCO algorithms ready for deployment in production vector databases? To answer this, we analyzed the evaluation protocols of prior research (see Table I) and identified several key limitations in their evaluations [1]–[4]:
1
TABLE I: Comparisons of evaluation setup in prior work on Distance Comparison Operation (DCO) Related #(Dataset) Dimensionality Work [1] 6 256 ∼ 960 [2] 6 256 ∼ 960 [3] 8 128 ∼ 960 6 96 ∼ 4096 [4]
#(Algorithm) Compared Hardware Application Distance OOD Tested Work Environment Scenario Metric Query 5 million 3 N/A (first work) CPU w/o SIMD Query Euclidean × 5 million 3 [1] CPU w/o SIMD Query Euclidean × 100 million 5 [1] CPU w/o SIMD Query Euclidean, IP ✓ 1 million 3 [1] CPU ± SIMD Query Euclidean × CPU ± SIMD Query, Update, Ours 10 96 ∼ 12288 100 million 8 [1]–[4] Euclidean, IP ✓ & GPU Index Construction SIMD: Single Instruction Multiple Data; IP: Inner Product; OOD: Out-of-Distribution, Ref. [3] uses only synthetic data for OOD evaluation. Scalability
TABLE II: Summary of frequently used notations
We derive practical guidelines for selecting the optimal DCO method under different scenarios and highlight future research directions. To foster further work, we have open-sourced the benchmark on GitHub [10]. Road Map. The rest of this paper is structured as follows. Sec. II defines the DCO problem, and Sec. III introduces existing algorithms. Next, Sec. IV and Sec. V detail the benchmark setup and analyze evaluation results. Finally, Sec. VI reviews related work and Sec. VII concludes the paper. •
Notation O S q, k dis(o1 , o2 ) f τ , dis d
Description A dataset O of N vectors, each of dimensionality D Query answer Query vector q and the number k of nearest neighbors Distance between two vectors o1 and o2 A given distance threshold and estimated distance Number of scanned dimensions during performing DCO
Remark. The scalability of exact solutions to vector similarity search is severely limited by the curse of dimensionality [19]. This has led to a rich line of research focused on approximate algorithms that trade exactness for efficiency, with the primary goal of maximizing the recall. The recall of the query answer S against the ground truth S ∗ is defined as:
II. P RELIMINARY This section defines the Distance Comparison Operation (DCO) problem. Table II summarizes the major notations. A. Basic Concepts
|S ∩ S ∗ | k B. Definition of Distance Comparison Operation
Before defining the DCO, we first introduce two basic concepts: vector data and vector similarity search. Definition 1 (Vector Data): A vector data (“vector” as short) o is defined as an ordered sequence (x1 , x2 , · · · , xD ). Here, D is the vector’s dimension, and xi represents the i-th coordinate. The function dis(o1 , o2 ) denotes the distance between two vectors o1 and o2 , which is a measure of their similarity. We use O to denote a dataset containing N vectors, each with D dimensions. In practice, vector datasets can be classified into three kinds based on their dimensionality [11], [12]: • Low-Dimensional Vector Dataset: These are defined by a moderate dimensionality (D ∈ [10, 100]). They are prevalent in classical statistics and traditional machine learning (ML) applications [13], [14]. • High-Dimensional Vector Dataset: These datasets exhibit a large number of dimensions (D ∈ (100, 1000]). They usually consist of embedding vectors generated by deep learning models in domains like computer vision and natural language processing [15], [16]. • Ultra-High-Dimensional Vector Dataset: This kind encompasses datasets with dimensionality on the order of 103 or higher. They often arise from raw sensor data and embedding layers of LLMs [17], [18]. Distance functions are diverse, and commonly used examples include Euclidean distance, inner product, and cosine similarity. For simplicity, we use Euclidean distance as the default distance function in the rest of the paper. Definition 2 (Vector Similarity Search): Given a vector dataset O, a query vector q ∈ RD , and a positive integer k, vector similarity search aims to find the k nearest neighbor (KNN) vectors S ⊆ O to the query vector q satisfying
recall =
(1)
Overview of Vector Distance Operations. Prior research [4], [20], [21] in vector similarity search relies heavily on two types of vector distance operations: distance computation operations and distance comparison operations. • Distance Computation Operation: This operation calculates the exact distance between two vectors. It is computationally intensive but can often be accelerated by hardware like SIMD instructions and GPUs. • Distance Comparison Operation (DCO): This operation determines whether the distance between two vectors exceeds a given threshold. Its efficiency enhancement stems from a key insight: computing exact distance is often unnecessary, since the comparison result can be derived by scanning only a subset of the dimensions. We formally define this operation below. Definition 3 (Distance Comparison Operation (DCO) [1]): Given two vectors o, q and a distance threshold τ , the distance comparison operation (DCO) determines the true value of the statement dis(o, q) ≤ τ . If true, it also returns the exact distance. Otherwise, it returns false alone, without the distance. The distance threshold τ is usually set to the distance of candidate vectors to the query vector. As [1]–[3] identifies, the vast majority of DCOs within a vector search return false. This makes the overall cost of exact distance calculation relatively low, as it is incurred only for the small subset of DCOs that return true. The following example illustrates this operation. Example 1: Fig. 1 shows two instances of DCO with data vectors o1 and o2 , a query vector q, and a distance threshold τ = 11. A naive solution is to scan all dimensions, compute the
|S| = k and ∀v ∈ S, ∀u ∈ (O \ S), dis(v, q) ≤ dis(u, q)
2
Fig. 1: Instances of Distance Comparison Operation (DCO) Euclidean distances dis(o1 , q) = 15 and dis(o2 , q) = 10, and then compare them with τ . However, a full-dimensional scan is not always necessary. For o1 , after scanning just the first 6 coordinates, the partial distance reaches 12, which already exceeds τ . This eliminates the need to scan the remaining dimensions of o1 and thereby reduces computational cost.
Fig. 2: Taxonomy of existing DCO methods Algorithm 1: Simple Scanning Based Framework Input: Two vectors o, q and a distance threshold τ Output: Whether dis(o, q) ≤ τ 1 Initialize the number of currently scanned dimensions d ← 0, partial distance dis′ ← 0; 2 while the number of scanned dimensions d < D do 3 Update partial distance dis′ and increase d; 4 if dis′ > τ then // only for PDScanning 5 return False;
III. E XISTING DCO M ETHODS In this section, we first introduce a taxonomy of existing DCO methods, and categorize them as simple scanning based, hypothesis testing based, and classification based methods. We then review each category and finally present a comparative analysis of these DCO methods. A. Method Taxonomy The design of high-performance DCOs follows two paths: optimized algorithms and dedicated hardware. Hardwarebased approaches usually leverage GPUs [22] for massive thread-level parallelism or SIMD instructions [23] for dimension-level parallelism. However, as recent research focuses on algorithmic optimization strategies [1]–[3], [24], these hardware-centric methods are not our primary concern. As shown in Fig. 2, we categorize these optimization algorithms into three kinds based on their core ideas: simple scanning based, hypothesis testing based, and classification based. These methods are complementary to hardware accelerators like GPUs and SIMD instructions, which will be evaluated later. The subsequent subsections will delve into each of these categories in detail, and Fig. 3 provides a highlevel overview of their respective ideas and workflows.
6
return True and dis ← dis′ ;
they stop: PDScanning quits early as soon as dis′ exceeds the threshold τ , while FDScanning scans all dimensions. Optimization. The efficiency of this framework can be further enhanced by two techniques: Single Instruction Multiple Data (SIMD) and Principal Component Analysis (PCA) [26]. (1) Optimization via SIMD: The partial distance computation can be parallelized at the dimension-level using SIMD. For example, both FDScanning and PDScanning can partition the dimensions of a vector into contiguous blocks that align with the SIMD register width (e.g., 128-bit or wider). This enables the CPU to simultaneously perform arithmetic operations across multiple dimensions within a single instruction cycle. In this way, more than 4 dimensions can be processed together in a batch, which saves computational cost. (2) Optimization via PCA: PCA projects the original vector data into a new coordinate system, where dimensions are ordered by their variance contributions. By rotating the original vector space (rather than performing dimensionality reduction), this transformation preserves the overall Euclidean distances between vectors while prioritizing the dominant influence of the leading dimensions. PDScanning can also leverage this property to enable early termination in lines 4-5 of Alg. 1. We denote this method as PDScanning+ [4] in our work. Despite its simplicity, it has not been considered as a candidate DCO method in prior studies [1]–[3], primarily because FDScanning and PDScanning are prevalent in vector databases. However, we treat it as a distinct baseline, since it offers unique advantages according to our evaluations.
B. Simple Scanning Based Method Simple scanning based methods solve the DCO problem by scanning dimensions of vectors o and q, through two strategies: Full Dimension Scanning (FDScanning) and Partial Dimension Scanning (PDScanning). • FDScanning [23] scans all dimensions to compute the exact distance and then compares it to the threshold τ . • PDScanning [25] scans dimensions incrementally while maintaining a running partial distance. It terminates the scan as soon as the intermediate result proves that dis(o, q) > τ , avoiding unnecessary computation. General Framework. Alg. 1 presents the general framework of these DCOs. It starts scanning dimensions from scratch, keeping track of the partial distance dis′ so far. The main difference between FDScanning and PDScanning lies in when
3
(a) Simple scanning based method
(b) Hypothesis testing based method
(c) Classification based method
Fig. 3: The three categories of DCO methods: core ideas and main workflows Similarly, Deng et al. [2] also propose an error bound on the estimated distance as follows:
C. Hypothesis Testing Based Method The anticipated efficiency gain of PDScanning over FDScanning stems from scanning fewer dimensions. This intuition motivates a class of approximate algorithms that estimate f from a partial distance (dis′ ) the full distance (denoted by dis) to scan even fewer dimensions. Using the estimated distance within a probability inequality, these algorithms then perform a hypothesis test to accept or reject dis(o, q) ≤ τ . They are classified into two kinds based on the estimation strategies: (1) residual distance estimator and (2) cross-term estimator.
(s P P
P
) < α (2)
where λk is the k-th largest eigenvalue of the vector dataset’s covariance matrix, α is the significance level, and ϵd is the error tolerance after scanning d dimensions. Both α and ϵd are user-defined parameters whose values are set empirically. Strategy II. Cross-Term Estimator. This strategy employs an algebraic decomposition of the squared Euclidean distance into a sum of square-terms and cross-terms:
Strategy I. Residual Distance Estimator. This class of algorithms estimates the residual distance (i.e., the distance contributed by unscanned dimensions) based on the partial distance dis′ from the currently scanned dimensions. There are two general methods for such estimators. (1) Assuming Equal Contribution per Dimension. Under this assumption, the full distance can be estimated by simply scaling up the partial distance proportionally to the ratio of total dimensions to scanned dimensions. To enforce this assumption in practice, ADSampling [1] employs a random projection matrix P ∈ Rd×D to map original vectors into a new coordinate system. This work also proves an error bound on the estimated distance as follows: (r
D λk dis(WdT o, WdT q) > (1 + ϵd )dis(o, q) Pk=1 d k=1 λk
dis(o, q) = ∥o∥2 + ∥q∥2 − 2⟨o, q⟩
(3)
2
(4)
2
= ∥o∥ + ∥q∥ − 2⟨od, qd⟩ − 2⟨or, qr⟩
where ∥ · ∥ is the L2 -norm, and ⟨·, ·⟩ is the inner product. The sub-vectors od, qd and or, qr contain the scanned and unscanned dimensions, respectively. In Eq. (4), both ∥o∥ and ∥q∥ can be pre-processed, and ⟨od, qd⟩ can be computed directly from the scanned dimensions. Their collective partial result is denoted by dis′ . This method thus focuses on estimating the remaining cross-term, ⟨or, qr⟩. Yang et al. [3] propose a new method called DDCres to bound this term. DDCres [3] first centers the data vectors to have zero mean. It then assumes that both query and data vectors follow a Gaussian distribution, where σi2 denotes the variance of the i-th dimension. Accordingly, the expectation and variance of the remaining cross-term are derived as:
) 2 D dis(P o, P q) − dis(o, q) ≤ ϵdis(o, q) ≥ 1 − 2e−c·d·ϵ d
q In this inequality, D d dis(P o, P q) is the estimated distance f dis, c is a constant factor, and ϵ is the error tolerance. Thus, f ≤ (1 + ϵ) · dis holds with high the inequality implies that dis −cdϵ2 probability 1 − 2e . Moreover, this estimator ensures that f = dis when all original dimensions are preserved in the dis projection (i.e., d = D). (2) Assuming Differing Contribution per Dimension. In contrast, DADE [2] is designed for scenarios where dimensions contribute differently to the distance, and treats dimensions with different weights. Accordingly, it performs a PCA over the vector dataset to obtain the loading matrix W ∈ RD×D as the projection matrix. This ensures that the initial dimensions capture the largest possible contribution to the distance. Consequently, the result of DCOs can be quickly decided after scanning only a few leading dimensions.
E[⟨or , qr ⟩] =
D X
E[oi · qi ] =
i=d+1
Var[⟨or , qr ⟩] =
D X
(qi · σi )2
D X
E[oi ] · E[qi ] = 0
(5)
i=d+1
(6)
i=d+1
Consequently, the pexact distance dis lies within a confidence interval dis′ ±m·2 Var[⟨or , qr ⟩] with high probability, where m is a deviation multiplier. To test if dis > τ , the lower bound f i.e., of this interval is used as the estimated distance dis, p f = dis′ − m · 2 Var[⟨or , qr ⟩] dis (7) To tighten this lower bound, DDCres leverages PCA to minimize Eq. (6), since PCA reorders data dimensions in descending order of σi2 .
4
Algorithm 2: Hypothesis Testing Based Framework Input: Two vectors o, q and a distance threshold τ Output: Whether dis(o, q) ≤ τ 1 Set the null hypothesis H0 : dis ≤ τ and its alternative hypothesis H1 : dis > τ ; 2 while the number of scanned dimensions d < D do 3 Update partial distance dis′ and increase d; 4 Set significance level α by their parameter settings; // ϵ = ϵd for DADE, ϵ = 0 for DDCres 5 Compute a relaxed distance threshold (1 + ϵ) · τ ; f based on dis′ ; 6 Compute the estimated distance dis f > (1 + ϵ) · τ then 7 if dis 8 Reject H0 with confidence and return False; 9
Algorithm 3: Classification Based Method DDCpca Input: Two vectors o, q and a distance threshold τ Output: Whether dis(o, q) ≤ τ 1 // Offline Phase 2 Sample query vectors from dataset and parameters k; 3 Generate training samples through vector similarity search for sampled queries using a specific index; 4 Train linear models Mk,d , denoting the model for query parameter k after d dimensions are scanned.; 5 // Online Phase 6 while the number of scanned dimensions d < D do 7 Update partial distance dis′ and increase d; 8 if Mk,d predicts dis(o, q) > τ then return False ; 9
return True and dis ← dis′ ;
Variant. Yang et al. [3] propose another classification based method, named DDCopq. Unlike DDCpca, DDCopq trains a single linear model Mk for each query parameter k, using approximate distances derived from Product Quantization (PQ). During a DCO, this model first predicts if dis(o, q) > τ . If the result is negative, it performs a distance computation operation by scanning all dimensions to verify the result.
General Framework. Alg. 2 presents the main workflow of hypothesis testing based methods. Unlike simple scanning based methods, these methods incorporate an extra step (lines 4-6) in which hypothesis testing is used to check if the null hypothesis is valid. Correspondingly, the condition in line 7 is replaced by a verification on whether the estimated distance f exceeds a statistically derived error bound. If it does, the dis null hypothesis is rejected and the loop terminates early.
E. Summary Table III compares DCO methods on the following aspects: (1) Exactness: Simple scanning based algorithms are exact, while the others trade slight accuracy for efficiency. Besides, only DADE provides an unbiased distance estimator. (2) Assumption: DCO methods vary in their assumptions. Most DCO methods are limited to Euclidean distance (or transformable metrics), whereas PDScanning and PDScanning+ also support monotonic distances. DADE, DDCres, DDCpca, and DDCopq assume queries and data follow the same distribution. DDCres further assumes this distribution is Gaussian. Classification based methods require prior knowledge of the query parameter k and are coupled to a specific index. (3) Time Complexity: Only FDScanning, PDScanning, and ADSampling provide explicit time complexity analyses. However, ADSampling underestimates the O(D2 ) time cost of projecting a query vector into a new coordinate system. We categorize this per-query operation as online pre-processing, a cost also incurred by PDScanning+, hypothesis testing based, and classification based methods. Our analysis introduces d to denote the number of dimensions scanned and pi as the probability of a negative prediction. We also include the time cost of offline pre-processing, which includes PCA computation and model training. Our results show that online pre-processing can become the dominant bottleneck at sufficiently high dimensions, a finding that will be validated empirically later.
Beyond Euclidean Distance. The hypothesis testing based methods also support inner product and cosine similarity by transforming them into Euclidean distance. This requires the vector dataset to be normalized first. Then, the inner product ⟨o, q⟩ is derived from the Euclidean distance dis(o, q) as: ⟨o, q⟩ = 1 − 0.5 · (dis(o, q))
2
return True and dis ← dis′ ;
(8)
Since cosine similarity is equivalent to the inner product for normalized vectors, this extension applies to both metrics. D. Classification Based Method Main Idea. Other research [3] formulates the DCO problem as a binary classification task. Given the partial distance dis′ and threshold τ , the goal of this task is to predict whether the full distance satisfies dis ≤ τ . These methods typically assume the query workload is known a priori (e.g., often modeled using the vector dataset’s distribution). Under this assumption, they utilize a fixed vector index and sampled queries (including both an integer k and a query vector q) to generate sufficient training samples. Subsequently, a distinct linear model Mk,d is trained for each combination of the integer k and the number d of scanned dimensions. Representative Algorithm. Alg. 3 illustrates a representative algorithm DDCpca to this kind. In the offline phase, it runs similarity searches with different k values on a fixed vector index to generate training samples. These samples are used to train a set of linear models Mk,d , each corresponding to a query parameter k after d dimensions are scanned. During the online phase, DDCpca feeds the partial distance dis′ and distance threshold τ into the model Mk,d . The process terminates early if the model predicts dis(o, q) > τ .
IV. B ENCHMARK S ETUP This section introduces the detailed benchmark setup. We make our benchmark suite publicly available on GitHub [10]. A. Overview Our benchmark covers the following critical scenarios:
5
TABLE III: Comparisons of existing methods for Distance Comparison Operation (DCO) Time Complexity Breakdown2 Category
Method
Exactness
Assumption1
Offline Pre-Processing
Online Pre-Processing
Online Computation
Simple Scanning
FDScanning [23] PDScanning [25] PDScanning+ [4]
✓ ✓ ✓
None Monotonic Distance Monotonic Distance
N/A N/A O(N D2 )
N/A N/A O(D2 )
O(D) τ2 O(min(D, D dis 2 )) O(d)
Hypothesis Testing
ADSampling [1] DADE [2] DDCres [3]
× × ×
Classification
DDCpca [3] DDCopq [3]
× ×
2
τ log D )) O(min(D, (dis−τ δ )2 O(d) O(d) PD Qj−1 2 2 Euclidean, Index, Query O(N D ) O(D ) O( j=1 i=1 (1 − pi )) Euclidean, Index, Query O(N D(D + 2b )) O(D2 + D · 2b ) O(c + (1 − p)D)
Euclidean Euclidean, Query Euclidean, Data, Query
O(N D2 ) O(N D2 ) O(N D2 )
O(D2 ) O(D2 ) O(D2 )
1 “Euclidean”: only applicable to Euclidean distance or distances that can be transformed into it.; “Data”: data vectors follow a known distribution
(e.g., Gaussian); “Query”: query vectors follow the data distribution; “Index”: requires building a vector index for training. 2 δ: failure probability for (1 + ϵ)-approximation; b, c: product quantization parameters for subvector encoding length and codebook count.
Query Processing: Evaluating how DCOs impact vector similarity search performance across diverse datasets. • Out-of-Distribution (OOD) Queries: Generalization when query distribution differs from the data distribution. • Distance Metrics: Evaluating DCO performance on Euclidean distance, inner product, and cosine similarity. • Index Construction: The efficacy of DCOs in building mainstream vector indexes: HNSW [27] and IVF [28]. • Dynamic Updates: The robustness and effectiveness of DCOs when handling dynamic data. • Diversified Hardware Condition: The performance of DCOs under varied hardware configurations. TABLE IV: Dataset statistics
C. Compared DCO Algorithms and Their Implementations
•
We implement 8 DCO methods from prior research [1]– [4]: FDScanning, PDScanning, PDScanning+, ADSampling, DADE, DDCres, DDCpca, and DDCopq. The first three, serve as baselines, widely adopted in industrial vector databases. The other five are the state-of-the-art algorithms (“SOTA” as short). For a fair comparison, we implement all algorithms from scratch within a unified framework: • Index Selection: Each method is integrated into two indexes using identical data layouts: HNSW [27] and IVF [28], with HNSW running on CPUs and IVF on GPUs. • Target Hardware: We implement SIMD-optimized and GPU-accelerated versions for all algorithms. On CPUs, we evaluate these algorithms with and without SIMD optimizations, which accelerate distance computations via intra-vector parallelism. On GPUs, we pre-loaded IVF into device memory and adopt vector-level parallelism, launching a CUDA kernel for each IVF partition with each thread assigned to process one candidate vector. • Parameter Settings: DCO methods are configured with parameters recommended in their original papers. • Batch Query: Batch queries are processed sequentially. We implement all methods in both Python and C++, following their open-source implementations. Online query processing is written in C++, while offline pre-processing uses both C++ and Python, where Python is mainly employed for model training and PCA computation. By default, we enable SIMD via the SSE instruction set and keep multi-threading disabled. Please refer to [34] for more implementation details.
Dataset Dim. Category Raw Data Cardinality Size (GB) Deep 96 Low-D Image 100,000,000 36 100 Low-D Text 400,000 0.15 GloVe SIFT 128 High-D Image 1,000,000 0.5 Text2Image 200 High-D Multimodal 10,000,000 7.5 Laion 512 High-D Multimodal 1,000,448 2.0 Wikipedia 768 High-D Text 1,000,000 2.9 GIST 960 High-D Image 1,000,000 3.6 OpenAI 1536 Ultra-High-D Text 2,321,096 14 4096 Ultra-High-D Image 99,900 1.6 Trevi XUltra 12288 Ultra-High-D Text 100,000 4.6
B. Dataset and Query Workload Our benchmark employs 10 public datasets [29]–[32] for evaluating vector similarity search with varying dimensions, sizes, and raw data types (see Table IV). Most datasets contain in-distribution queries, which either share a distribution with the dataset or are sampled from it. In contrast, the multimodal datasets (Laion and Text2Image) exhibit an inherent distribution shift, as their data and query vectors are embedded from images and text, respectively, making their queries OOD. To simulate the eXtremely Ultra-high dimensionality of embeddings in modern LLMs (e.g., OpenAI’s davinci-001 model with 12,288 dimensions [33]), we also construct a synthetic dataset named XUltra. It is generated by concatenating token-level embeddings from the real-world dataset MSMARCO [32] until the target dimensionality of 12,288 is reached. In this dataset, each resulting vector represents the aggregation of tokens in a complete text phrase. The ground truth is obtained by exhaustive linear scan of the full dataset.
D. Parameter Setting The benchmark setup involves three types of parameters: Index Parameter. We configure HNSW with maximum node connections M = 16 and construction candidate list size ef Construction = 500, and IVF with 4096 partitions, following recommendations from Faiss [23]. Search Parameter. For HNSW, we vary the search candidate list size ef Search from 100 to 1500 in steps of 100. For IVF, we vary the probed partition count nprobe from 20 to 400 in steps of 20. By default, ef Search = 200 and nprobe = 80.
6
PDScanning