arXiv CSopen access

BBC: Improving Large-k Approximate Nearest Neighbor Search with a Bucket-based Result Collector

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

databases, sql, data management, storage

BBC: Improving Large-𝑘 Approximate Nearest Neighbor Search with a Bucket-based Result Collector Ziqi Yin1 , Gao Cong1 , Kai Zeng2 , Jinwei Zhu2 , Bin Cui3 1 Nanyang Technological University, Singapore

2 Huawei Technologies Co., Ltd

3 Peking University, China

[email protected],[email protected],{zhujinwei,kai.zeng}@huawei.com,[email protected]

arXiv:2604.01960v1 [cs.DB] 2 Apr 2026

ABSTRACT Although Approximate Nearest Neighbor (ANN) search has been extensively studied, large-𝑘 ANN queries that aim to retrieve a large number of nearest neighbors remain underexplored, despite their numerous real-world applications. Existing ANN methods face significant performance degradation for such queries. In this work, we first investigate the reasons for the performance degradation of quantization-based ANN indexes: (1) the inefficiency of existing top-𝑘 collectors, which incurs significant overhead in candidate maintenance, and (2) the reduced pruning effectiveness of quantization methods, which leads to a costly re-ranking process. To address this, we propose a novel bucket-based result collector (BBC) to enhance the efficiency of existing quantization-based ANN indexes for large-𝑘 ANN queries. BBC introduces two key components: (1) a bucket-based result buffer that organizes candidates into buckets by their distances to the query. This design reduces ranking costs and improves cache efficiency, enabling high-performance maintenance of a candidate superset and a lightweight final selection of top-𝑘 results. (2) two re-ranking algorithms tailored for different types of quantization methods, which accelerate their re-ranking process by reducing either the number of candidate objects to be re-ranked or cache misses. Extensive experiments on real-world datasets demonstrate that BBC accelerates existing quantizationbased ANN methods by up to 3.8× at recall@𝑘 = 0.95 for large-𝑘 ANN queries. PVLDB Reference Format: Ziqi Yin1 , Gao Cong1 , Kai Zeng2 , Jinwei Zhu2 , Bin Cui3 . BBC: Improving Large-𝑘 Approximate Nearest Neighbor Search with a Bucket-based Result Collector. PVLDB, 14(1): XXX-XXX, 2026. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/Heisenberg-Yin/BBC.

INTRODUCTION

Driven by the rapid process of large-scale machine learning and generative AI techniques, efficient vector search has become a critical capability in modern data systems [55, 62, 66, 88]. Vector databases [59, 60, 80, 81] now serve as the foundation for querying embeddings generated by deep learning models, where Approximate Nearest Neighbor (ANN) search is the core computational primitive [59, 83], trading off minor accuracy for significantly improved efficiency [29, 85]. In practice, ANN algorithms are typically 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

extended to retrieve approximate 𝑘-nearest neighbors to meet the demands of real-world applications. Although ANN queries have been extensively studied, most existing studies design and evaluate their methods under small 𝑘 settings, which are typically in the range of a few tens to a few hundreds [12, 44]. This setting is well-suited for some applications such as retrieval-augmented generation (RAG) [41], where an ANN index retrieves the top-10 relevant documents for a large language model to generate the final responses. However, many real-world applications involve large 𝑘 scenarios (e.g., 𝑘 ≥ 5,000), where a large number of nearest neighbors need to be retrieved for each query. We refer to such queries as large-𝑘 ANN queries and next present several of their applications. (1) In model training or fine-tuning scenarios, it is often necessary to efficiently retrieve a large set of highly relevant data samples to construct the training dataset. These samples typically number in the tens of thousands in many real-world applications, such as retrieving videos or images that capture specific types of dangerous driving behavior. In such cases, the initial query is often ambiguous, such as an image representing a driving behavior. Data engineers usually need to perform multiple iterations of search, refining the query by selecting better examples from the retrieved results before identifying an effective query and obtaining a satisfactory set of results. (2) In document retrieval, state-of-the-art methods often adopts a retrieve-and-rerank pipeline [39]. Documents are encoded into embeddings using pre-trained language models [93]. An ANN index built on these embeddings retrieves tens of thousands of candidate documents for each query. Subsequently, a more sophisticated model, such as ColBERT [37], which encodes queries and documents into token embeddings and computes similarity by aggregating token-level similarities, re-ranks the candidates to obtain the final results. (3) In industrial recommendation systems [21, 36], hundreds of thousands of candidates are first retrieved via an ANN index and then re-ranked using more computationally expensive models to produce the final recommendations. However, existing ANN methods face significant performance degradation when handling large-𝑘 ANN queries, as demonstrated in our evaluation on four representative ANN indexes: the IVF [35], the popular graph-based method HNSW [48], and two quantizationbased methods IVF+RaBitQ [20] and IVF+PQ [32]. An example result on the C4 dataset is shown in Figure 1 and similar trends are observed across other datasets. We observe that at recall@𝑘 = 0.95, when 𝑘 increases from 100 to 5,000, the throughput of IVF+RaBitQ drops from 227 queries per second (QPS) to 47 QPS, a 4.8 × slowdown; HNSW’s throughput falls from 113 QPS to 20 QPS, showing a larger 5.7× slowdown. In this work, we focus on optimizing

IVF

HNSW

QPS (1/s)

103 102

IVF+PQ

103

IVF+RaBitQ

Distance Computation FastScan Heap Other

102

IVF+RaBitQ

IVF+PQ

HNSW

15% 23%

25% 59% 31%

10% 26% 34%

54% 30%

101 101 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00

Recall@100

Recall@5000

Figure 1: Querying Performance of IVF, HNSW, IVF+PQ, and IVF+RaBitQ on the C4 dataset at 𝑘 = 100 and 𝑘 = 5000.

27% 40%

32% 42%

k=100 k=5000

66% 56% k=100 k=5000

IVF

98% 95%

k=100 k=5000

Figure 2: Time Overhead Breakdown of four methods at different 𝑘, where “Distance computation” denotes exact distance computation, “FastScan” denotes estimated distance computation, “Heap” denotes heap operations, and “Other” covers the remaining costs.

quantization-based methods for large-𝑘 ANN queries for two reasons: 1) quantization-based methods exhibit superior performance for large-𝑘 ANN queries; and 2) our empirical results and analysis1 show that quantization-based methods are more robust to increase of 𝑘 compared with graph-based methods such as HNSW. Challenge 1. Quantization-based methods often face significant slowdowns in large-𝑘 ANN queries due to two primary challenges. The first stems from the inefficiency of existing top-𝑘 collectors when handling large 𝑘. These collectors are responsible for maintaining the 𝑘 nearest candidates by storing each candidate’s ID and distance to the query. Whenever a closer candidate is found, it replaces the farthest one, whose distance serves as the comparison threshold. Existing ANN studies commonly employ a binary-heap priority queue as the top-𝑘 collector. However, when 𝑘 is large, the heap becomes inefficient under modern memory hierarchies consisting of L1, L2, L3 caches and main memory. The inefficiency arises because the heap size exceeds the capacity of the fastest L1 cache. For example, when 𝑘 = 100, the distance–ID pairs occupy only 800 bytes, which is well within the 32 KB L1 cache capacity, allowing the heap reside entirely in the L1 cache and achieve low latency. However, when 𝑘 = 5,000, the heap grows to 40,000 bytes, exceeding the L1 cache capability and causing frequent L1 cache misses that significantly increase latency. For example, in IVF+RaBitQ, its share of runtime rises from 2% at 𝑘 = 100 to 23% at 𝑘 = 5,000 under recall@𝑘 = 0.95, as shown in Figure 2. This observation is consistent with prior findings [38] that link priority queue performance to L1 cache misses. Challenge 2. As 𝑘 increases, the pruning effectiveness of quantization methods drops. These methods accelerate ANN search by estimating distances to quickly prune distant objects and can be grouped into two categories: (1) unbounded methods that prune solely by estimated distances (e.g., PQ), and (2) bounded methods that provide probabilistically guaranteed distance bounds (e.g., RaBitQ). Although they differ in querying strategies, both types of approaches require re-ranking a growing number of candidates as 𝑘 increases. In bounded methods, the candidate set is maintained by a top-𝑘 collector, and any object whose estimated bounds overlap with the current threshold is re-ranked. As 𝑘 grows, the number of such objects increases, leading to higher re-ranking overhead. For example, in IVF+RaBitQ, the runtime share of exact distance computation rises from 27% at 𝑘 = 100 to 40% at k = 5,000, as shown in Figure 2. Similarly, unbounded methods retrieve and re-rank a candidate set whose size is typically several times larger than 𝑘, to

maintain high recall. Consequently, as 𝑘 increases, the re-ranking cost grows roughly linearly, resulting in a significant slowdown. Our Method. To address the first challenge, we observe that existing collectors typically maintain an exact top-𝑘 set, where each stored candidate may be accessed and replaced. When 𝑘 is large and the stored distance-id pairs exceed the L1 cache capacity, this results in frequent L1 cache misses and high maintenance overhead. To overcome this, we propose a novel bucket-based result buffer (BBC) that reorganizes candidate storage to maximize cache efficiency, preserving exact results without maintaining exact top-𝑘 order. Specifically, it partitions the estimated distance range between the query and data objects into non-overlapping sub-ranges through one-dimensional quantization. Each sub-range corresponds to a bucket consisting of two linear buffers that sequentially store the IDs and distances of candidates falling within this sub-range. This design offers two key benefits: (1) it lowers ranking complexity by organizing candidates into buckets based on distance, maintaining ordering across buckets while avoiding ordering within each bucket; (2) it reduces L1 cache misses, as the sequential insertion pattern within each bucket enables the hardware prefetching mechanism to proactively prefetch relevant memory blocks into the L1 cache for subsequent candidate insertions. Leveraging both bucket-level ranking and the number of objects stored in each bucket, we efficiently identify the buckets that contain the exact top-𝑘 results and the threshold bucket that holds boundary candidates near the threshold distance. Together, these buckets form a candidate superset. The upper bound distance of the threshold bucket serves as a relaxed threshold. Both the candidate superset and the relaxed threshold can be maintained at low cost, since only a small number of buckets are involved. This design eliminates per-object access and replacement by operating only on bucket-level structures, where distant buckets are implicitly pruned once they become irrelevant. When the exact top-𝑘 set is required, the final selection is restricted to the threshold bucket, as the bucket-level ranking guarantees that all preceding buckets contain only closer candidates. Leveraging the distance concentration phenomenon [29, 85], we further show that under an equal-depth partition of the distance range, the error between the relaxed and exact thresholds are on the order of 10−2 , keeping the selection cost negligible, as supported by both theoretical guidance (Section 3.2) and empirical evaluation (Section 4.2). To address the second limitation, we design two new re-ranking algorithms tailored to different quantization methods. For bounded methods, we aim to skip re-ranking objects that are guaranteed to be either within or outside the top-𝑘 based on their estimated distance bounds, and re-rank only uncertain ones. We first formulate

1 The suboptimal performance of HNSW at large 𝑘 arises from the fact that graph-based ANN indexes are designed for small 𝑘 . These methods construct a proximity graph during indexing and use it to navigate queries toward nearby objects to reduce search space. However, when 𝑘 is large, the graph traversal inevitably expands to a larger portion of the graph, incurring significant additional overhead, as shown in Figure 2.

an minimal re-ranking scenario that minimizes the number of reranked objects without sacrificing accuracy and design a solution to achieve it. However, this approach incurs substantial heap overhead that offsets its benefits. To address this, we design a greedy re-ranking algorithm that integrates seamlessly with the proposed result buffer, significantly reducing the number of re-ranked objects with a small extra cost. For unbounded methods, the number of re-ranked objects cannot be reduced since their estimated distances lacking guaranties. Instead, we propose an early re-ranking strategy that tightly couples re-ranking with the result buffer. It computes exact distances for objects predicted to enter the re-ranking pool when their data are accessed, thus effectively reducing cache misses during exact distance computation. Building on these techniques, we develop a novel bucket-based result collector (BBC) that substantially enhances the efficiency of existing quantization-based methods for large-𝑘 ANN queries without compromising accuracy. BBC integrates the proposed result buffer to gather candidates efficiently and incorporates the newly designed re-ranking algorithms to produce the final results. The main contributions of this work are summarized as follows: (1) We identify and analyze two major limitations of quantizationbased methods for large-𝑘 ANN queries: inefficiency of top-𝑘 collectors and declined pruning effectiveness, both of which cause substantial performance degradation. To our knowledge, these findings have not been reported in prior work. (2) We propose a novel bucket-based result collector (BBC), which introduces a bucket-based result buffer serving as a cacheefficient top-𝑘 collector and two new re-ranking algorithms tailored to bounded and unbounded quantization methods. To the best of our knowledge, this is the first framework explicitly designed for large-𝑘 ANN queries. (3) Extensive experiments on real-world datasets show that: (1) BBC accelerates existing quantization-based methods on large𝑘 ANN queries by up to 3.8× speedup at recall@𝑘 = 0.95; (2) the proposed result buffer reduces the overhead of the top-𝑘 collector by an order of magnitude; and (3) the new re-ranking algorithms speed up the re-ranking efficiency by up to 1.8×.

L1 cache, located closest to the CPU core, provides the fastest access speed but has the smallest capacity, typically 32 KB. It stores the most frequently accessed data and instructions to minimize access latency. The L2 and L3 caches are located farther from the CPU cores, offering slower access than L1 but faster than main memory. Although main memory is much larger, typically ranging from several tens to hundreds of gigabytes (GB), its high access latency makes it slower. Therefore, the data required by the CPU are loaded into the L1 cache before processing. The transfer of data from main memory or from the L3/L2 caches to the L1 cache results in L1 cache misses, which introduce high latency, as shown in prior experimental evaluations [38]. To reduce L1 cache misses, modern hardware automatically prefetches memory blocks adjacent to the currently accessed data into the L1 cache, while evicting less frequently used blocks to lower cache levels or main memory. Top-𝑘 Collector. Most ANN studies employ a binary-heap priority queue to maintain the 𝑘 nearest neighbors. Despite the binary heap achieving low latency when 𝑘 is small, it incurs frequent L1 cache misses and significantly higher latency at larger values of 𝑘, as discussed in Section 1. Although modern hardware supports L1 cache prefetching, it is only effective for data structures with regular memory access patterns, such as sequentially stored linear buffers. For data structures with irregular and unpredictable access patterns, such as binary heaps, its applicability is much more limited [46]. Quantization. Quantization methods accelerate ANN search by efficiently estimating distances to prune distant candidates. During indexing, they construct a quantization codebook, assign each data vector to their nearest codebook vector, and store the codebook ids as compact quantization codes. At query time, they (1) pre-compute distances between the query and the codebook vectors, and (2) use these pre-computed distances to efficiently estimate query-object distances from the stored quantization codes, also known as quantized distances. In practice, these methods are often integrated with an inverted file (IVF) index [35] to improve querying performance, with IVF+RaBitQ [20] and IVF+PQ [32] being representative methods. The IVF index partitions the data vectors into 𝑛𝑐𝑙𝑢𝑠𝑡𝑒𝑟 clusters using the k-means algorithm during indexing and routes each query to the 𝑛𝑝𝑟𝑜𝑏𝑒 nearest clusters at query time, thereby reducing the search space. Within these clusters, quantization methods execute their querying algorithm to obtain the final results. Based on their pruning mechanisms and query processing strategies, quantization methods can be categorized into two types. In particular, bounded methods such as RaBitQ [19, 20] provide an estimated distance range with a high probabilistic guarantee (e.g., 99%) and leverage these bounds for pruning. Specifically, it employs a top-𝑘 collector to maintain the currently found 𝑘 nearest neighbors and re-ranks any objects whose lower bounds fall below the collector’s current threshold, as they may potentially enter the top-𝑘 results. Because the objects stored in the collector often change rapidly during the early stage, the number of re-ranked objects is typically several times larger than 𝑘, as shown in Section 4.2. When 𝑘 increases, this results in a significantly higher re-ranking cost, as shown in Figure 2. Unbounded methods such as Product Quantization (PQ) [32] generally preset a hyperparameter 𝑛𝑐𝑎𝑛𝑑 ≫ 𝑘 (e.g., 𝑛𝑐𝑎𝑛𝑑 =3,000 and 𝑘=100) to determine how many candidates are retrieved based on their estimated distances. When a query arrives, these methods employ a top-𝑘 collector to gather

BACKGROUND AND MOTIVATIONS

Problem Statement. Given a dataset 𝐷 of 𝑁 data objects, each represented by a vector in 𝑑 dimensional Euclidean space, the Approximate Nearest Neighbor (ANN) query involves two phases: indexing and querying. In the indexing phase, it constructs a data structure based on the data vectors. In the querying phase, given a query 𝑞, it aims to efficiently retrieve the 𝑘 nearest vectors using the data structure under a similarity metric. Typically, the majority of existing studies [31, 32, 47, 81] focus on the setup where 𝑘 is small (e.g., 𝑘 = 100). However, as discussed in Section 1, the query with large 𝑘 (e.g., 𝑘 ≥ 5, 000) is important in many applications and introduces new challenges in algorithm design. In this study, we aim to develop an efficient solution for the large-𝑘 ANN queries (𝑘 ≥ 5,000) that is applicable to commonly used similarity metrics, including Euclidean distance, cosine similarity, and inner product. Unless otherwise specified, we use Euclidean distance as the default metric and also discuss inner product and cosine similarity. Modern Memory Hierarchy. The modern memory hierarchy typically consists of L1, L2, and L3 caches and main memory. The 3

Bucket-based Result Collector Result Buffer Dist Range: [3.0, 3.5) Dist 3.1

Dist Range: [3.5, 4.0)

3.2

12 32 Bucket 1

Dist Range: [5, 6]

3.6

Dist 4.5

4.2

Dist 4.8

4.9

Dist 5.1

Bucket 2

IVF+RaBitQ: Rerank lower bound < threshold

Bucket 3

Bucket 4

4 ≤ threshold bucket 5

Compute Bucket ID: 4

Update: k = 8, update after scanning each cluster

update Compute the heap distance ReRank Too Many Objects

Dist Range: [4.5, 5.0)

Dist 3.5

Push: k = 8, insert (4.9, 9) pair

Object with lower bound

Dist Range: [4.0, 4.5)

42 Bucket 5

Push to the bucket sequentially

update threshold bucket: Bucket 4

IVF+RaBitQ+BBC: Rerank

IVF+PQ: Rerank

Bucket 1 Without ReRank

Bucket 2 Without ReRank Bucket 3 Later ReRank

IVF+PQ+BBC: Rerank 6

Bucket 1

Early ReRank

Bucket 2

Early ReRank

Bucket 3

Later ReRank

Bucket 4 Later ReRank Random Memory Access Reduced Random Memory Access

Bucket 4 Later ReRank Reduced Reranked Objects

Figure 3: Illustration of the Proposed Bucket-based Result Collector. 𝑛𝑐𝑎𝑛𝑑 candidates according to their estimated distances, which are then re-ranked to produce the final results. Here, 𝑛𝑐𝑎𝑛𝑑 is typically several times larger than 𝑘 to achieve high recall. As 𝑘 increases, the number of re-ranked objects increases linearly, leading to a significant increase in the re-ranking cost, as shown in Figure 2. Motivations. While many ANN methods have been developed, no prior work has specifically investigated large-𝑘 ANN queries. Therefore, we evaluate several representative ANN methods on large-𝑘 ANN queries, where the top-𝑘 collector is implemented using a binary-heap priority queue. We present the evaluation results on the C4 dataset in Figure 1, which contains over 14 million passages. Figure 2 further presents a breakdown of time overheads under different 𝑘 based on VTune profiling. Details of the experimental setup are given in Section 4.1. The experimental results reveal the performance degradation of these methods on large-𝑘 ANN queries, and we have highlighted two major limitations of existing quantization-based methods in the Introduction. This motivate us to design a new algorithm for large-𝑘 ANN queries.

Leveraging both bucket-level ranking and the number of objects stored in each bucket, we can efficiently identify the buckets that contain the exact top-𝑘 results and the threshold bucket that holds boundary candidates near the threshold distance. For example, in Figure 3, when 𝑘 = 8, bucket 5 serves as the threshold bucket because the cumulative number of objects in the first five buckets reaches 8 (before inserting the object 9 with distance 4.9). The candidates within these buckets together form a candidate superset. The upper bound distance of the threshold bucket serves as the relaxed threshold, which is 6 in this case. At query phase, both can be efficiently updated. For example, when inserting a new object (e.g., object 9 with distance 4.9 in Fig. 3), we compute its bucket ID based on its distance to the query, compares it with the threshold bucket ID (e.g., Bucket 5), and appends the distance and ID to its corresponding bucket (e.g., pushing object 9 to Bucket 4). After insertion, the threshold bucket can be updated by traversing buckets in order until the accumulated number of candidates reaches 𝑘, as the buckets are organized by distance range. In Figure 3, when 𝑘 = 8, the threshold bucket shifts from bucket 5 to bucket 4 after inserting object 9. The more distant buckets (e.g., Bucket 5) are no longer visited and are implicitly dropped without incurring additional cost. Finally, we only need to select a subset of objects from the threshold bucket and combine them with the objects in the preceding buckets to obtain the exact top-𝑘 results. Second, two re-ranking algorithms are designed for different types of quantization approaches to accelerate their re-ranking process, as illustrated in Figure 3. For bounded methods, we establish a minimal re-ranking scenario that minimizes the number of re-ranked objects without accuracy loss and propose a solution to achieve it. However, this solution incurs considerable heap overhead. To mitigate this, we propose a greedy re-ranking algorithm built on our result buffer. It skips re-ranking objects that are definitely either inside (those in near buckets, e.g., Buckets 1-2) or outside the top-𝑘 (those in distant buckets) and re-ranks only the uncertain ones near the threshold bucket (e.g., Buckets 3-4). For unbounded methods, we propose a novel early re-ranking algorithm that re-ranks many objects predicted to enter the re-ranking pool when accessing their data (those in the near bucket, e.g., Buckets 1-2), reducing L1 cache misses from random memory access. In the rest of this section, we present the two components of BBC: (1) the result buffer (Section 3.2) and (2) the two re-ranking algorithms, along with the improved search algorithm (Section 3.3).

3 THE BBC METHOD 3.1 Overview In this section, we propose a novel bucket-based result collector (BBC), composed of two new components: a bucket-based result buffer serving as the top-𝑘 collector and two re-ranking algorithms tailored for different types of quantization methods. We proceed to give an overview of the two components. First, the result buffer partitions the estimated distance range between the query and data objects into non-overlapping sub-ranges using one-dimensional quantization, as shown in Figure 3. Each sub-range corresponds to a bucket that contains two linear buffers, which sequentially store the IDs and distances of candidates. As presented in the Introduction, this design (1) provides bucket-level ranking of candidates based on their distances to the query, where candidates are ordered across buckets but remain unordered within each bucket (e.g., objects in Bucket 1 always have smaller distances to the query than those in Bucket 2). This design differs from binary heaps, which maintain a strict bucket-level order throughout, thereby reducing the ranking cost; and (2) exploits the hardware prefetching mechanism to reduce L1 cache misses. This is because only the tail of the recently accessed linear buffer typically resides in the L1 cache, while the preceding elements are evicted, substantially alleviating L1 cache pressure. 4

3.2

Result Buffer

Algorithm 1: The Workflow of Result Buffer Input: Result buffer 𝐵; a set of clusters to be scanned 𝑐𝑙; number of objects to retrieve 𝑘; Output: The result buffer 𝐵 1 Function Push(𝑞, 𝑜 𝑖 , 𝜏, 𝐵): 2 Compute Dist(𝑞, 𝑜𝑖 ) and bucket ID 𝑗; 3 if 𝑗 ≤ 𝜏 then 4 Append (dist, 𝑜𝑖 ) to the tail of 𝐵 [ 𝑗 ];

We now describe how the result buffer partitions the estimated distance range between the query and objects into 𝑚 non-overlapping sub-ranges, as defined by the codebook 𝐶: 𝐶 = {𝑐 1, 𝑐 2, . . . , 𝑐𝑚+1 },

𝑐𝑖 < 𝑐𝑖+1 .

(1)

Accordingly, the sub-ranges are formally defined, each corresponding to a bucket 𝐵 [𝑖]: 𝐵 [𝑖] = [𝑐𝑖 , 𝑐𝑖+1 ),

𝑖 = 1, 2, . . . , 𝑚.

Function Update(𝐵, 𝑘): 𝑠 ← 0; 7 foreach 𝐵 [𝑖 ] ∈ 𝐵 do 8 𝑠 ← 𝑠 + |𝐵 [𝑖 ] |; 9 if 𝑠 > 𝑘 then 10 return 𝑖; 5

(2)

For each input distance–ID pair, the result buffer determines the corresponding bucket by locating the interval in which the distance falls. Specifically, an object 𝑜𝑖 is assigned to bucket 𝐵 [ 𝑗] if its distance from the query, Dist(𝑞, 𝑜𝑖 ), satisfies 𝑐 𝑗 ≤ Dist(𝑞, 𝑜𝑖 ) < 𝑐 𝑗+1 . The distance Dist(𝑞, 𝑜𝑖 ) can refer to either the exact distance Distexact or the estimated distance Distquant . Next we turn to the three core operations of the result buffer: Push, Update, and the Collect function, which are used to collect the top-𝑘 results. The Push function in Algorithm 1 (lines 1-4) details the procedure for inserting an object into the result buffer. Specifically, when a new object is inserted, the result buffer first computes its distance to the query and determines the corresponding bucket ID (line 2). It then compares this bucket index with the threshold bucket ID (line 3) and appends the distance–ID pair to the assigned bucket if the index does not exceed the threshold bucket ID (line 4). Here, using the threshold bucket ID for comparison essentially treats the upper bound of the threshold bucket’s distance range as the relaxed threshold. In addition, bucket ID comparisons can benefit from fast SIMD-based integer comparison instructions, enabling simultaneous comparison of batches of objects. The quantization code computation can also be accelerated using SIMD instructions, as discussed later. The update function in Algorithm 1 (lines 5-11) describes the process of updating the threshold bucket. In particular, the buckets in the result buffer are arranged in ascending order of distance range, as shown in Figure 3. We accumulate the number of candidates in buckets in order until the total number reaches or exceeds 𝑘 (lines 6-9). Once this condition is met, the visited bucket is identified as the threshold bucket and returned (line 10). If the total number of objects stored in the result buffer is less than 𝑘, the threshold bucket is set to ∞, allowing all objects to be accepted (line 11). Since only dozens of buckets are involved, the update cost is negligible. Once the threshold bucket is updated, the more distant buckets are no longer accessed and are implicitly dropped, thus incurring no additional time cost for candidate maintenance. The collect function in Algorithm 1 describes the workflow of collecting top-𝑘 results based on (estimated) distance in IVFbased ANN methods. Specifically, we first initialize the threshold bucket to ∞ and construct the codebook 𝐶 for the result buffer, whose generation will be discussed later (lines 13–14). Objects are then inserted into the result buffer 𝐵 within each cluster using the Push function (lines 15–17). The threshold bucket is updated after processing each cluster using the Update function (line 18). This update is performed once per cluster because the relaxed threshold is very close to the exact threshold (as will be discussed later), and updating once per cluster helps to reduce the update cost. Once all clusters have been processed, the objects in the buckets

return ∞;

Function Collect(𝑞, 𝑐𝑙, 𝐵, 𝑘): 13 Initialize threshold bucket 𝜏 ← ∞; 14 Construct codebook 𝐶 for 𝐵; 15 foreach 𝑐𝑟 ∈ 𝑐𝑙 do 16 foreach 𝑜𝑖 ∈ 𝑐𝑟 do 17 Push(𝑞, 𝑜𝑖 , 𝜏, 𝐵);

𝜏 ← Update(𝐵, 𝑘 );

𝑅𝑒𝑠 ← ∅; for 𝑖 ← 0 to 𝜏 − 1 do 𝑅𝑒𝑠 ← 𝑅𝑒𝑠 ∪ 𝐵 [𝑖 ];

20 21 22 23 24

𝑠 ← 𝑘 − |𝑅𝑒𝑠 |; Select the top-𝑠 candidates from 𝐵𝜏 and append to 𝑅𝑒𝑠 ; return 𝑅𝑒𝑠;

preceding the threshold bucket are inserted into the result set 𝑅𝑒𝑠 (lines 19-21). This is because the bucket-level ranking of candidates ensures that these objects are closer to the query than those in the subsequent buckets, thus falling within the top-𝑘 candidates. Finally, we compute the number of objects 𝑠 that need to be selected from the threshold bucket (line 22), choose the top-𝑠 objects from it, and add them to 𝑅𝑒𝑠 (line 23). 𝑅𝑒𝑠 now contains the exact top-𝑘 results and is returned (line 24). This design substantially reduces the cost of maintaining exact top-𝑘 results, as the selection operation is performed only once in the final stage within a single bucket. Deciding the Number of Buckets 𝑚. A key consideration is how to determine the number of buckets 𝑚. If 𝑚 is too large, the increased number of vectors to be written raises the L1 cache miss rate. If 𝑚 is too small, objects are concentrated in just a few vectors, resulting in a costly final selection process (as shown in Section 4.2). To balance these factors, we aim to maximize 𝑚 based on the L1 cache capacity 𝐶𝐿1 , while accounting for the space required by quantization codes 𝐶𝑞𝑢𝑎𝑛𝑡 and lookup tables 𝐶𝑙𝑢𝑡 . Accordingly, the number of buckets 𝑚 is given by the following equation: 𝑚=

𝐶𝐿1 − 𝐶𝑞𝑢𝑎𝑛𝑡 − 𝐶𝑙𝑢𝑡 , 256

(3)

𝑑 × 𝐵8 represents the space for quantization where 𝐶𝑞𝑢𝑎𝑛𝑡 = 2 × 32 × 𝑀 codes of the current and subsequent processed batches. Here, 𝑑 is the dimensionality, 𝑀 is the number of sub-vectors, and 𝐵 denotes 5

PDF of Distances

0.5 𝑑 × 2𝐵 is the size of the lookup the bits per sub-vector. 𝐶𝑙𝑢𝑡 = 𝑀

0.4

𝑁 ∑︁

𝑐 𝑎𝑖+1 − Dist(𝑞, 𝑜𝑖 ) ,

Density

table. The denominator 256 reflects hardware prefetching considerations: since our proposed result buffer maintains two separate linear buffers for IDs and distances, and modern hardware typically prefetches two 64-byte cache lines for sequential access, we reserve 𝑚 × 2 × 2 × 64 = 256𝑚 bytes to ensure the active tails of all buckets reside in the L1 cache. Notably, since not all buckets are accessed frequently, many buckets are implicitly dropped at query phase. As a result, small variations in 𝑚 do not result in a noticeable increase in latency (as shown in Exp-6). Deciding the Codebook 𝐶. We now describe how to construct the codebook 𝐶 = {𝑐 1, 𝑐 2, . . . , 𝑐𝑚+1 }. The codebook is designed to satisfy two critical properties: (1) Precision, ensuring that the relaxed threshold (e.g., 𝑐𝑖 ) remains close to the precise value. This is crucial because it affects the efficiency of the final selection, and significant deviations could make the process time-consuming; (2) Efficiency, ensuring low latency in both codebook generation and quantization code computation. Since the result buffer serves as the top-𝑘 collector in the ANN search, slow generation and computation would offset its benefits. Note that the codebook requires dynamic generation for each query, rather than pre-computation, as queryobject distance distributions vary across queries. To quantify precision, we formalize it as the total quantization error. Given a query 𝑞, for each object 𝑜𝑖 ∈ 𝐷, let Dist(𝑞, 𝑜𝑖 ) denote its distance to the query and 𝑎𝑖 denote its assigned quantization code. Each code corresponds to a bucket whose upper boundary is 𝑐 𝑎𝑖+1 . The precision objective 𝐶𝑜𝑠𝑡 (𝐶, 𝐷) is then defined as: 𝐶𝑜𝑠𝑡 (𝐶, 𝐷) =

0.3 0.2 0.1 0.0 3

Distance

Figure 4: The probability density function (PDF) of distances between the query and data vectors on the C4 dataset. shows the distances from the query to the top-100,000 and top-100 data vectors are very close (3.83 vs. 3.02), indicating that the error introduced by equal-depth quantization is minimal and satisfies the precision requirements. We provide (1) a quantitative analysis in the technical report [90] and (2) experimental validation on many real-world high-dimensional datasets, as demonstrated in our experiments (as shown in Exp-5). To maintain computational efficiency, we follow the approach of [56], which first computes 𝑛𝑒𝑤 equal-width buckets and then reassigns these buckets into 𝑚 equal-depth buckets, where a lookup table map is used to preserve the correspondence between them. Codebook Generation Based on Estimated Distance. We now detail how to construct the codebook 𝐶 for the result buffer. Since the result buffer is used to collect the top-𝑘 results, we aim to estimate the distance range between the query and the top-𝑘 data vectors. To this end, we sample a subset of the dataset, denoted as 𝐷 sample , which typically consists of tens of thousands of objects, and quickly compute their estimated distances. In practice, 𝐷 sample is formed using objects from the 5–10 nearest clusters. We then perform a partial sort on the estimated distances to obtain the top-𝑘 results. Since the partial sort is performed only once, its computational cost is negligible. Afterwards, we derive the minimum distance 𝑑 min and maximum distance 𝑑 max from the sample, and compute the width 𝛿 for the equal-width method. Finally, the equalwidth buckets are reassigned to form 𝑚 equal-depth buckets, as described above. A concern is inaccurate distance range estimation, which we address via boundary control, as described below. Quantization Code Computation. For newly inserted objects, we first compute their equal-width codes and subsequently clamp those outside the range [0, 𝑚] to prevent boundary overflow, and then obtain the corresponding mapping ID via the lookup table, as formulated below: Dist(q, oi ) − 𝑑 min , 0, 𝑚 (6) 𝑎𝑖 = map clamp 𝛿 where clamp(𝑥, 𝑦, 𝑧) = max(𝑦, min(𝑥, 𝑧)). SIMD j instructionsk can

(4)

𝑖=1

The corresponding optimal solution {𝐶, 𝐷 } is given by: {𝐶, 𝐷 } = arg min 𝐶𝑜𝑠𝑡 (𝐶, 𝐷).

Top-100 (dist=3.0292) Top-10000 (dist=3.5069) Top-100000 (dist=3.8324)

(5)

{𝐶,𝐷 }

The problem is then to find a centroid codebook 𝐶 that minimizes Equation 4. Because computing the distance for all objects is impractical, an exact solution to this problem becomes infeasible. The two common approximate methods for one-dimensional quantization are equal-depth partition and equal-width partition, which are described as follows: • Equal-depth partition [57]: This method divides the data range into intervals with equal data points, resulting in non-uniform intervals based on the data distribution. While it maximizes bucket utilization and has higher precision, it involves a slower generation and computation process. • Equal-width partition [65]: This method divides the data range into intervals of equal width, regardless of the data distribution. While it enables faster codebook generation and code computation, it suffers from lower precision because it does not adapt to the data distribution. First, we demonstrate that the precision level of equal-depth quantization meets our requirements. In particular, in high-dimensional space, the distance concentration phenomenon [29, 85] causes distances between vectors to concentrate around their mean value with only a small deviation. We illustrate this using the C4 dataset, where the probability distribution function (PDF) of distances between the query and data vectors is shown in Figure 4. The figure

Dist(q,o ) −𝑑

i min be employed to accelerate the computation of , en𝛿 abling the batch processing of dozens of objects. We fix 𝑛 ew to 256, so that the mapping can be stored using uint8. This has two advantages: (1) The mapping requires only 256 bytes in total, allowing it to reside in L1 cache with minimal memory overhead; (2) AVX instructions can process 4× as many uint8 values per instruction as float32 values, which speeds up batch comparison. Complexity Analysis. The time complexity of the Push operation is 𝑂 (1), including bucket ID computation, which is significantly more efficient than the 𝑂 (log(𝑘)) complexity of a binary heap. The

Algorithm 2: Minimal Re-ranking Solution of IVF+RaBitQ

Algorithm 3: Improved Search Algorithm of IVF+RaBitQ

Input: The number of objects to be retrieved 𝑘; the set of objects to be scanned 𝑂. Output: Top-𝑘 results. 1 Initialize a max-heap 𝐻𝑢 and a min-heap 𝐻𝑙 ; 2 foreach 𝑜 ∈ 𝑂 do 3 Compute estimated lower/upper bounds 𝑜𝑙𝑏 /𝑜𝑢𝑏 of 𝑜; 4 if 𝑜𝑢𝑏 < 𝐻𝑢 .top( )𝑢𝑏 then 5 Insert (𝑜, 𝑜𝑙𝑏 , 𝑜𝑢𝑏 ) into 𝐻𝑢 , using 𝑜𝑢𝑏 as the key; 6 if 𝐻𝑢 .size() > 𝑘 then ′ , 𝑜 ′ ) ← 𝐻 .pop( ); 7 (𝑜 ′ , 𝑜𝑙𝑏 𝑢 𝑢𝑏 ′ ) into 𝐻 , using 𝑜 ′ as the key; 8 Insert (𝑜 ′ , 𝑜𝑙𝑏 𝑙 𝑙𝑏

Input: Query 𝑞, number of objects to be retrieved 𝑘, and the clusters to be scanned 𝑐𝑙. Output: Top-𝑘 results. 1 Initialize two result buffers 𝐵𝑢 and 𝐵𝑙 ; 2 Generate codebook 𝐶 for 𝐵𝑢 and 𝐵𝑙 ; 3 foreach 𝑐𝑟 ∈ 𝑐𝑙 do 4 foreach 𝑜𝑖 ∈ 𝑐𝑟 do 5 Compute the lower/upper bounds 𝑜𝑙𝑏 /𝑜𝑢𝑏 for 𝑜𝑖 and their respective quantization codes 𝑎𝑙𝑏 , 𝑎𝑢𝑏 ; 6 if 𝑎𝑢𝑏 < 𝜏 then 7 Insert 𝑜𝑖 into 𝐵𝑢 ;

else

if 𝑜𝑙𝑏 < 𝐻𝑢 .top( )𝑢𝑏 then Insert (𝑜, 𝑜𝑙𝑏 ) into 𝐻𝑙 , using 𝑜𝑙𝑏 as the key;

10 11

9 10

Initialize 𝑉 𝑖𝑠 ← ∅; while 𝐻𝑢 .top( )𝑢𝑏 > 𝐻𝑙 .top( )𝑙𝑏 do 14 if 𝐻𝑢 .top( ) ∉ 𝑉 𝑖𝑠 and 𝐻𝑢 .top( )𝑙𝑏 < 𝐻𝑙 .top( )𝑙𝑏 then 15 𝑜 ← 𝐻𝑢 .pop( );

Try to insert (𝑜, Distexact (𝑞, 𝑜 ) ) into 𝐻𝑢 , using Distexact (𝑞, 𝑜 ) as the key; 𝑉 𝑖𝑠 ← 𝑉 𝑖𝑠 ∪ {𝑜 }; if 𝐻𝑢 .size( ) > 𝑘 then 𝑜 ′ ← 𝐻𝑢 .pop( ); if 𝑜 ′ ∉ 𝑉 𝑖𝑠 then ′ ) into 𝐻 , using 𝑜 ′ as the key; Insert (𝑜 ′ , 𝑜𝑙𝑏 𝑙 𝑙𝑏

19 20 21 22 23

𝜏 ← Update(𝐵𝑢 , 𝑘 );

Insert objects from 𝐵𝑢 into 𝐵𝑙 ; 𝑖 ← 0, 𝑗 ← 𝜏; 13 Initialize result buffer 𝐵 exact with codebook 𝐶; 14 while 𝑖 < 𝑗 do 15 foreach 𝑜 ∈ 𝐵𝑙 [𝑖 ] ∪ 𝐵𝑢 [ 𝑗 ] do 16 Compute exact distance 𝐷𝑖𝑠𝑡 exact (𝑞, 𝑜 ); 17 Insert 𝑜 into 𝐵 exact based on 𝐷𝑖𝑠𝑡 exact (𝑞, 𝑜 );

else 𝑜 ← 𝐻𝑙 .pop( );

else if 𝑎𝑙𝑏 < 𝜏 then Insert 𝑜𝑖 into 𝐵𝑙 ;

18 19 20 21 22

Clear 𝐵𝑙 [𝑖 ] and 𝐵𝑢 [ 𝑗 ]; 𝑖 ← 0, 𝑗 ← index of the threshold bucket in 𝐵𝑢 ∪ 𝐵 exact ; while 𝐵𝑙 [𝑖 ].empty() do 𝑖 ← 𝑖 + 1; return the objects in 𝐵𝑢 ∪ 𝐵 exact as the final top-𝑘 results;

return the objects in 𝐻𝑢 as the top-𝑘 results

threshold). Based on this insight, we formally define the minimal re-ranking scenario.

update operation has a time complexity of 𝑂 (𝑚), as it requires accumulating the sizes of 𝑚 buckets. In practice, 𝑚 ≪ 𝑘 (e.g., 𝑚 = 80 and 𝑘 = 5, 000), making it substantially more efficient than the 𝑂 (log(𝑘)) cost of binary heap. The collect operation has a time complexity of 𝑂 (𝑁 ). Since it is invoked only once at the end of the query process, its overall cost is negligible.

3.3

Observation 1 (Minimal Re-ranking Scenario). Dist𝑘 denotes the threshold in the final top-𝑘 results. When the objective is to minimize the number of objects to be re-ranked, the minimal re-ranking scenario for bounded quantization method is to re-rank only those objects 𝑜 ∈ 𝐷 whose lower and upper bounds satisfy [𝑜𝑙𝑏 , 𝑜𝑢𝑏 ] ∩ {Dist𝑘 } ≠ ∅. This set represents the theoretical minimal set of objects that must be re-ranked without accuracy loss.

Re-rank Algorithms

Solution to the Minimal Re-ranking Scenario. We design Algorithm 2 to achieve the minimal re-ranking scenario described in Observation 1. Specifically, it consists of two phases: the candidate collection phase and the re-ranking phase. During the candidate collection phase, it maintains the 𝑘 candidates with the smallest upper bounds in a max-heap 𝐻𝑢 and collects those objects with lower bounds below the 𝑘-th upper bound in a min-heap 𝐻𝑙 (lines 2-11). During the re-ranking phase, we first initialize a 𝑉 𝑖𝑠 to mark objects whose exact distances have been computed (line 12). Then, we iteratively select the object with the smaller lower bound from the tops of the two heaps for exact distance computation (lines 14-23). The re-ranking process terminates once the largest upper bound in the max-heap becomes smaller than the smallest lower bound in the min-heap (line 13). Due to page limitations, its correctness proof is provided in the technical report [90]. However, as discussed in Section 2, maintaining a max-heap of size 𝑘 becomes

We now discuss how to integrate the result buffer with existing quantization-based methods: IVF+RaBitQ and IVF+PQ. We aim to enhance their efficiency for handling large-𝑘 ANN queries. To achieve this, we introduce several new techniques. Integrating with IVF+RabitQ. We introduce a novel re-ranking algorithm based on our result buffer by exploiting the bound property [20], namely, the true distance fall within the estimated bound with high probability (e.g., 99%). This property enables us to efficiently estimate the distance range between each visited data object and the query. As a result, it is unnecessary to re-rank data objects that are guaranteed to be within the top-𝑘 (i.e., those whose upper bound is less than the final threshold, which the threshold of the final top-𝑘 results) or definitively outside the top-𝑘 (i.e., those whose lower bound exceeds the final threshold). Re-ranking is required only for candidates whose inclusion in the top-𝑘 remains uncertain (i.e., those whose estimated distance range intersects the final 7

Table 1: Dataset Statistics Algorithm 4: Improved Search Algorithm of IVF+PQ Input: Query 𝑞, the number of objects to be retrieved 𝑘, the clusters to be scanned 𝑐𝑙, the number of objects to be re-ranked 𝑛𝑐𝑎𝑛𝑑 . Output: Top-𝑘 results. 1 Initialize result buffer 𝐵; 2 Sample a subset 𝐷 sample ⊂ 𝐷; 3 Produce codebook 𝐶 for 𝐵; pred ; 4 Generate the predicted threshold bucket 𝜏 5 foreach 𝑐𝑟 ∈ 𝑐𝑙 do 6 foreach 𝑜𝑖 ∈ 𝑐𝑟 do 7 Compute Distquant (𝑞, 𝑜𝑖 ) and bucket id 𝑎𝑖 ; 8 if 𝑎𝑖 < 𝜏 then 9 if 𝑎𝑖 < 𝜏 pred then 10 Compute exact distance Distexact (𝑞, 𝑜𝑖 ); 11 Insert 𝑜 and Distexact (𝑞, 𝑜𝑖 ) into 𝐵; 12 13

14 15 16

Dataset

|𝐷 |

𝑑

|𝑄 |

Size (GB)

WiKi C4 MSMARCO Deep100M

10,000,000 14,252,691 18,000,000 100,000,000

1,536 1,024 768 96

1,000 1,000 1,000 10,000

58 54 51 35

an object from its PQ code, we predict whether it will enter the reranking pool based on the estimated distance. If so, we immediately compute its exact distance to reduce L1 cache misses. Algorithm 4 details our proposed re-ranking approach and summarizes the improved search algorithm. During the sampling stage of (line 2), we use the bucket containing codebook generation |𝑂 sample | × 𝑛𝑐𝑎𝑛𝑑 -th quantized distance as the predicted thresh|𝑂 | old bucket 𝜏 pred (line 3). Then, during the scanning phase, for each

else

object in a bucket preceding the threshold bucket, we compute the exact distance if its bucket ID 𝑎𝑖 < 𝜏 pred and insert the exact value; otherwise, we insert its quantized distance (lines 5-13). After scanning each cluster, we update the predicted threshold 𝜏 pred using

Insert 𝑜 and Distquant (𝑞, 𝑜𝑖 ) into 𝐵; Update 𝜏 pred and 𝜏; Re-rank remaining candidates in 𝐵; return top-𝑘 results;

|𝑂

scanned the × 𝑛𝑐𝑎𝑛𝑑 -th quantized distance and update the thresh|𝑂 | old bucket 𝜏 as described in Algorithm 1 (line 14). This approach leads to a substantial reduction in L1 cache misses and re-ranking time, as verified in Exp-5. A concern is that 𝜏 pred might be too large, causing unnecessary re-ranking. In practice, this does not occur because clusters are traversed from nearest to farthest based on query-centroid distance (line 5), which produces a distribution skewed toward smaller values, thereby keeping 𝜏 pred low. Extension to different Metrics. Our proposed BBC is applicable to different similarity metrics, including Euclidean distance, cosine similarity, and inner product. As these metrics all exhibit the distance concentration phenomenon, the result buffer can handle them by switching the bucket ordering between ascending and descending distance, since cosine similarity and inner product require maintaining the largest top-𝑘 results. The two re-ranking algorithms are compatible with different metrics: RaBitQ supports Euclidean distance, inner product, and cosine similarity, and Product Quantization has been extended to accommodate various metrics [25].

slow when 𝑘 is large, and the unbounded min-heap used above results in greater overhead. Our experiments show that this approach even performs worse than IVF+RaBitQ (as shown in Section 4.2). Therefore, we propose a greedy re-ranking algorithm based on our result buffer, which significantly reduces the number of items to be re-ranked. Algorithm 3 details our proposed re-ranking approach and summarizes the enhanced search algorithm. Specifically, instead of using two heaps, we replace the two heaps with two result buffers that share the same codebook (lines 1–2). Next, we collect candidates based on the lower and upper bounds of 𝑜𝑖 . In particular, when the object’s upper bound lies within the top-𝑘 upper bounds, the object is inserted into 𝐶𝑢 ; otherwise, if its lower bound falls below the threshold, it is inserted into 𝐶𝑙 , as it may still qualify for the final top-𝑘 results (lines 3-9). For the collected candidates, we first re-collect the falsely dropped candidates into 𝐶𝑙 from 𝐶𝑢 (line 11). Then we greedily re-rank all items in the marginal buckets, that is, the top bucket of C𝑙 and the threshold bucket of C𝑢 , and insert the results into a new result buffer Cexact for storing items with exact distance (lines 15-17). After each computation iteration, we clear the candidate buckets and update the marginal buckets until 𝑖 ≥ 𝑗 (lines 18-21). When 𝑖 ≥ 𝑗, the upper bound of C𝑢 is smaller than the lower bound of C𝑙 , indicating that no further potential candidates exist. Finally, we return the results in C𝑢 ∪ Cexact as the final results. The experimental results show that this method achieves near-minimal re-ranking reduction, leading to a substantial decrease in re-ranking time (as shown in Section 4.2). Integrating with IVF+PQ. Due to the unbounded nature of the PQ algorithm, we cannot reduce the number of objects to be re-ranked. Therefore, we propose an early re-ranking algorithm built upon our result buffer to reduce the cache misses caused by the random memory access patterns of IVF+PQ, as illustrated in Figure 3. In particular, we optimize the memory layout to store each object’s PQ code and embedding contiguously. When estimating the distance of

4 EXPERIMENTS 4.1 Evaluation Setup Datasets. We conduct experiments on four real-world datasets. Specifically, we evaluate our method and baselines on the Wiki, C4, MSMARCO, and Deep100M datasets. The statistics of these datasets are listed in Table 1. Details of each dataset are stated in the technical report due to page limitations [90]. Baselines. First, we evaluate four representative ANN methods for large-𝑘 ANN queries, as detailed in the technical report [90]. We integrate our proposed BBC with existing quantization-based methods, IVF+PQ and IVF+RabitQ, yielding IVF+PQ+BBC and IVF+RaBitQ+BBC. We compare them with their original counterparts and also include the minimal re-ranking solution for IVF+RaBitQ, described in Section 3.3 and denoted as IVF+RaBitQ+MIN, as a baseline. We also include brute-force search, denoted as BFC, as a baseline for comparison. Second, to compare the efficiency of our proposed result buffer, denoted as RB, for collecting the top-𝑘 8

QPS

120

IVF+RaBitQ

IVF+PQ

IVF+RaBitQ+BBC

IVF+PQ+BBC

IVF+RaBitQ+MIN

BFC

0 0 0 0 0 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00

Recall@5000

Recall@10000

Recall@20000

Recall@40000

Recall@100000

(a) Wiki 80

QPS

120

00.80 0.85 0.90 0.95 1.00 00.80 0.85 0.90 0.95 1.00 00.80 0.85 0.90 0.95 1.00 00.80 0.85 0.90 0.95 1.00 00.80 0.85 0.90 0.95 1.00

Recall@5000

Recall@10000

Recall@20000

Recall@40000

Recall@100000

(b) C4 80

QPS

120

00.80 0.85 0.90 0.95 1.00 00.80 0.85 0.90 0.95 1.00 00.80 0.85 0.90 0.95 1.00 00.80 0.85 0.90 0.95 1.00 00.80 0.85 0.90 0.95 1.00

Recall@5000

Recall@10000

Recall@20000

320

200

120

240

Recall@40000

Recall@100000

100

QPS

150

160

0 0.80 0.85 0.90 0.95 1.00

Recall@5000

0 0.80 0.85 0.90 0.95 1.00

Recall@10000

0 0.80 0.85 0.90 0.95 1.00

Recall@20000

0 0.80 0.85 0.90 0.95 1.00

Recall@40000

0 0.80 0.85 0.90 0.95 1.00

Recall@100000

(d) Deep100M

Figure 5: The accuracy-efficiency trade-off results under different 𝑘 (upper and right is better). 1 Í𝑖=𝑘 Dist(𝑞,𝑘𝐴𝑁 𝑁 (𝑞) [𝑖 ] ) results, we consider four baselines: the binary heap (denoted as 𝑖=0 Dist(q,kNN(q) [i] ) , where 𝑞 denotes the query, 𝑘𝑁 𝑁 (𝑞) [𝑖] is 𝑘 Heap), the cache-optimized d-ary Heap [34] (denoted as d-Heap), the 𝑖-th true nearest neighbor of 𝑞 in R̃, and 𝑘𝐴𝑁 𝑁 (𝑞) [𝑖] is the the sorted linear buffer used in [1] (denoted as Sorted), and the lazy i-th approximate nearest neighbor retrieved by the ANN algorithm update method (denoted as Lazy). In particular, Sorted maintains in R. Second, to compare our proposed result buffer with alternaall candidates in a sorted linear buffer, shifting the entire buffer tive approaches, we evaluate the time overhead (milliseconds) of upon each insertion. Lazy stores candidates whose distances to the collecting top-𝑘 results under varying dataset sizes and different query are below the current threshold in a linear buffer and updates values of 𝑘. We also report the isolated runtime of our result buffer both the buffer and the threshold using a SIMD-optimized partial and the baselines during this process using VTune profiling. sorting operation (e.g., x86simdsort::qselect), after each cluster is Parameter Settings. Following the suggestion from Faiss [35], processed. the number of clusters for IVF, IVF+RaBitQ, and IVF+PQ is set √︁ Evaluation metrics. First, for ANN query, we use recall rate to approximately |𝐷 |, which is 4,096 in our experiments. For recall@𝑘 = R∩𝑘 R̃ [44, 83] to evaluate the accuracy of search reIVF+RaBitQ, we use the default quantization parameters from the original paper [20], 𝜖0 = 1.9 and 𝐵𝑞 = 4. For IVF+PQ, the number sults and queries per second QPS = |𝑄𝑡 | [17] to evaluate the search’s efficiency. Here, R represents the result retrieved by the ANN inof sub-vectors 𝑀 is set to 𝑑4 , and the number of bits per sub-vector is set to 4, resulting in 𝐵 = 𝑑, following the original settings [3, dex, R̃ denotes the ground-truth result computed by the brute-force 25, 35]. For HNSW, during indexing, we set the candidate list size search. QPS= |𝑄𝑡 | [17] is the ratio of the number of queries (|𝑄 |) 𝑒 𝑓construction and the maximum number of edges per node 𝑀 to 200 to the total search time (𝑡), representing the number of queries and 32, respectively, following previous studies [48]. To evaluate processed per second. We also report the relative error between the the capability of methods in handling large-𝑘 ANN queries under distances of approximate nearest neighbors in R and true nearest different 𝑘, we vary 𝑘 from 5,000 to 100,000, using five representative neighbors in R̃ to assess the quality of the retrieved results. Folvalues (5,000, 10,000, 20,000, 40,000, and 100,000), which are widely lowing previous studies [44, 73], the relative error is computed as 9

IVF+RaBitQ+BBC

IVF+PQ+BBC

IVF+RaBitQ+MIN

600

300

180

150

400

200

120

100

200

100

800

IVF+RaBitQ

QPS

600

0 0.80 0.85 0.90 0.95 1.00

Recall@10

IVF+PQ

800

400

0 0.80 0.85 0.90 0.95 1.00

Recall@100

240

0 0.80 0.85 0.90 0.95 1.00

Recall@500

0 0.80 0.85 0.90 0.95 1.00

Recall@1000

200

BFC

0 0.80 0.85 0.90 0.95 1.00

Recall@2500

Figure 6: The accuracy-efficiency trade-off results under small values of 𝑘 on the C4 dataset (upper and right is better).

IVF+RaBitQ

Relative Error

0.008

IVF+PQ

IVF+RaBitQ+BBC

IVF+PQ+BBC

IVF+RaBitQ+OPT

0.008

0.006

0.004

0.002

0.000 0.000 0.000 0.000 0.000 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00

Recall@5000

Recall@10000

Recall@20000

Recall@40000

Recall@100000

Figure 7: Relative error of large-𝑘 ANN queries on the C4 dataset (lower is better). used in practical scenarios [21, 39]. Additionally, we also present experimental results for 𝑘 values ranging from 10 to 2,500, showing that BBC does not slow down existing methods for small 𝑘. At query time, IVF and IVF+RaBitQ vary the number of clusters for routing 𝑛𝑝𝑟𝑜𝑏𝑒 from 10 to 1,200 and IVF+PQ use the same 𝑛𝑝𝑟𝑜𝑏𝑒 as IVF+RaBitQ. For IVF+PQ, for each dataset and given 𝑘, the 𝑛𝑐𝑎𝑛𝑑 parameter is then fine-tuned to maximize QPS at a target recall of 0.95, under the constraint that the configuration must also be capable of achieving 0.98 recall, which is listed in the full version due to page limitations [90]. For HNSW, we increase 𝑒 𝑓search from 𝑘 in increments of 𝑘2 . For BBC, since our CPU, like most modern CPUs, has an L1 cache of 𝐶𝐿1 = 32 KB, we set the number of buckets 𝑚 according to Equation 3: 56 for Wiki, 80 for C4, 92 for MSMARCO, and 120 for Deep100M. Implementations. The baselines and our method are all implemented in C++. First, we use the hnswlib implementation [49], a widely adopted industry-standard library, for HNSW. For IVF+RaBitQ, we adopt its open-source implementation [20]; and for IVF and IVF+PQ, we implement these methods based on IVF+RaBitQ because they share a common index structure. Second, for Heap, we use the STL implementation. For d-Heap, we use the Boost Library. For Sorted, we use its official implementation. For Lazy, we use the x86simdsort library. All experiments are run on a machine equipped with an AMD Ryzen Threadripper PRO 5965WX 7.0GHz processor (supporting AVX2) and 128 GB of RAM.

4.2

61 ms). The gain stems from the high efficiency of our proposed result buffer and the effectiveness of the newly designed re-ranking algorithm. (2) The acceleration provided by BBC becomes more significant as 𝑘 increases. For example, on Deep100M at recall@𝑘 = 0.95, as 𝑘 increases from 5,000 to 100,000, the acceleration ratio of IVF+PQ+BBC over IVF+PQ increases from 2.9× at 𝑘 = 5,000 (2.8 ms vs. 8.2 ms) to 3.8× at 𝑘 = 100,000 (61 ms vs. 233 ms). This is because, as 𝑘 increases, existing collectors and re-ranking algorithms incur significantly higher costs, whereas our proposed result buffer remains efficient (Exp-4), and the newly designed ranking algorithm can further reduce the re-ranking cost substantially (Exp-6). (3) When 𝑘 is large, IVF+RaBitQ+MIN is significantly slower than IVF+RaBitQ+BBC, and even slower than IVF+RaBitQ. Across the four datasets, IVF+RaBitQ+MIN performs worse than IVF+RaBitQ and IVF+RaBitQ+BBC at 𝑘 = 5,000 and the performance gap widens considerably as 𝑘 increases. This can be attributed to the high cost of heap operations, which outweighs the efficiency gained from re-ranking fewer objects and leads to higher overhead when 𝑘 is large, consistent with our previous analysis. (4) Brute-force search is significantly slower than existing ANN indexes. For example, on the Wiki dataset, BFC takes 1.8s per query, whereas the slowest ANN method, IVF+PQ, requires only 0.5s to achieve recall@100000 = 0.98. Exp-2: ANN Query Performance with small 𝑘. We evaluate our method and the baselines on ANN queries with small 𝑘. The results on the C4 dataset are presented in Figure 6, and similar trends are exhibited in the other datasets. The experimental results show that (1) IVF+RaBitQ+BBC and IVF+RaBitQ, as well as IVF+PQ+BBC and IVF+PQ, exhibit comparable performance when 𝑘 = 10 and 𝑘 = 100; (2) When 𝑘 varies from 500 to 2500, IVF+RaBitQ+BBC and IVF+PQ+BBC outperform IVF+RaBitQ and IVF+PQ, respectively, and the performance gap widens as 𝑘 increases. This suggests that BBC maintains query performance at small 𝑘 (e.g., 10 or 100) and should be used when 𝑘 ≥ 500 to improve query performance. Exp-3: Relative error for large-𝑘 ANN queries. Figure 7 reports the relative error of large-𝑘 ANN queries on the C4 dataset. The results show that (1) as recall increases, the relative error drops

Experimental Results

Exp-1: Large-𝑘 ANN Query Performance. The accuracy-efficiency trade-off results over the four datasets are shown in Figure 5. We have the following observations: (1) BBC achieves 1.4×–3.8× speedup over existing quantization-based methods for large𝑘 ANN queries. Specifically, on the Deep100M dataset, when 𝑘 = 100,000 and recall@𝑘 = 0.95, IVF+PQ+BBC requires 61 ms per query, compared to 233 ms per query for IVF+PQ, achieving a 3.8× speedup. When 𝑘 = 5,000, on the Wiki dataset at recall@𝑘 = 0.98, IVF+PQ+BBC achieves a 1.4× acceleration over IVF+PQ (42 ms vs. 10

IVF+RaBitQ+Heap k = 5,000

Time (ms)

IVF+RaBitQ+d-Heap k = 10,000

IVF+RaBitQ+Sorted k = 20,000

IVF+RaBitQ+Lazy k = 40,000

IVF+RaBitQ+RB k = 100,000

Evaluated Objects (105) Evaluated Objects (105) Evaluated Objects (105) Evaluated Objects (105) Evaluated Objects (105)

Figure 8: Overhead of top-𝑘 collectors under varying numbers of evaluated objects on the Deep100M dataset.

k = 5,000

IVF+RaBitQ+Heap k = 10,000

Threshold

5.2 5.1 5.0 4.9 4.8 4.7

5.3 5.2 5.1 5.0 4.9 4.8

IVF+RaBitQ+RB IVF+PQ+Heap IVF+PQ+RB k = 20,000 k = 40,000 k = 100,000

5.4 5.3 5.2 5.1 5.0 4.9

5.6 5.5 5.4 5.3 5.2 5.1

5.8 5.7 5.6 5.5 5.4 5.3

Evaluated Objects (106) Evaluated Objects (106) Evaluated Objects (106) Evaluated Objects (106) Evaluated Objects (106)

Figure 9: Comparison values generated IVF+RaBitQ+MIN by the result buffer and binary heap IVF+PQ+BBC on the C4 Dataset. IVF+RaBitQof threshold IVF+RaBitQ+BBC IVF+PQ 45

120

220

160

100

Time (ms)

0 0.80 0.85 0.90 0.95 1.00

Recall@5000

0 10 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00

Recall@10000

Recall@20000

0 40 0.80 0.85 0.90 0.95 1.00 0.80 0.85 0.90 0.95 1.00

Recall@40000

(a) Re-ranking Time on the C4 dataset 180 240

120

160

0 0.80 0.85 0.90 0.95 1.00

Rerank Number (103)

Recall@5000

Recall@10000

Recall@20000

Recall@100000

500 350 200

Recall@40000

50 0.80 0.85 0.90 0.95 1.00

Recall@100000

(b) Number of Re-ranked Objects on the C4 Dataset

10:(10 Re-ranking Timecollection and Number of Re-ranked Objects on the C4 Dataset 5 ) during top-𝑘 Table 2: L1 cache missFigure counts process with different collectors under 𝑘 when 𝑛𝑝𝑟𝑜𝑏𝑒 = 210. observed on other datasets and IVF+PQ. We find that: (1) Our result buffer RB is significantly faster than existing collectors, 𝑘 5,000 10,000 20,000 40,000 100,000 achieving up to an order of magnitude improvement. For example, on the Deep100M dataset, when 𝑘 = 100,000 and 𝑛𝑝𝑟𝑜𝑏𝑒 Heap 3.2 3.7 4.8 7.2 9.7 = 210, for IVF+RaBitQ, RB takes only 2.0 ms, compared to 30.6 ms d-Heap 3.1 3.5 4.3 6.6 9.3 for Heap and 12.3 ms for Lazy, achieving an order-of-magnitude Sorted 4.5 8.9 19.9 69.3 396 speedup. (2) RB remains efficient at higher values of 𝑘, while Lazy 2.9 3.4 4.0 5.1 8.1 Lazy and Heap face significant degradation. For example, on RB 2.7 2.9 3.1 3.4 4.1 Deep100M, when 𝑘 = 5,000 and 𝑛𝑝𝑟𝑜𝑏𝑒 = 210, for IVF+RaBitQ, RB takes 0.9 ms, compared to 1.5 ms for Lazy and 1.9 ms for Heap. sharply from 0.3% (recall@100,000 = 0.89) to 0.01% (recall@100,000 When 𝑘 = 100,000 and 𝑛𝑝𝑟𝑜𝑏𝑒 = 210, RB takes 2.0 ms, while Lazy = 0.98), and (2) the relative error remains stable across different 𝑘. takes 12.3 ms and Heap takes 30.6 ms. This efficiency is due to Exp-4: Latency of Top-𝑘 Collectors. We evaluate the time overRB avoiding maintaining an exact top-𝑘 set throughout, which is head of our proposed result buffer, denoted as RB, and compare it consistent with previous experimental results. We further present with four baselines: Heap, d-Heap, Sorted, and Lazy. Using quanthe overall time for collecting the top-𝑘 results based on estimated tized distances from IVF+RaBitQ as keys, we use these methods to distances using our proposed result buffer RB and the existing colgather top-𝑘 results, with 𝑘 ranging from 5,000 to 100,000, under lectors, including the time spent on collectors, quantized distance varying numbers of evaluated objects. The number of evaluated computation, and other operations in the technical report [xx]. objects is controlled by 𝑛𝑝𝑟𝑜𝑏𝑒 , which is tuned as in the previous We also report the total L1 cache misses during the top-𝑘 colexperiment. The isolated time overhead of these methods is mealection process in Table 2, measured using Perf profiling. Since sured by VTune. Due to page limitations, we present the results on Deep100M in Figure 8 for IVF+RaBitQ, while similar trends are 11

Table 4: Top-𝑘 collection time (ms) under varying values of 𝑚 on the C4 dataset (𝑛𝑝𝑟𝑜𝑏𝑒 = 90) other components of the pipeline, such as estimated distance computation, are identical across methods, the observed differences in L1 cache misses mainly stem from the use of different collectors. The experimental results confirm that the acceleration of the top-𝑘 collection process is primarily driven by reduced L1 cache misses, with the speedup closely tracking the reduction in miss counts. For example, when 𝑘 = 100,000, RB halves the L1 cache misses compared to Lazy, resulting in an 2× speedup.

5,000

10,000

20,000

40,000

100,000

IVF+PQ 1.03 IVF+PQ+BBC 0.83

1.74 1.37

3.23 2.59

5.42 3.61

7.61 5.23

5,000

10,000

20,000

40,000

100,000

8 32 80 128 256

4.74 3.59 3.50 3.58 3.70

5.22 3.74 3.68 3.72 3.74

5.65 3.99 3.82 3.89 3.91

5.91 4.28 4.14 4.16 4.28

6.28 4.91 4.81 4.87 5.00

Exp-7: Parameter Sensitivity Study. We evaluate the impact of the number of buckets 𝑚 following the procedure in Exp-3. Specifically, we measure the top-𝑘 collection latency of IVF+RaBitQ+BBC on the C4 dataset with 𝑛𝑝𝑟𝑜𝑏𝑒 = 90, varying 𝑚 from 8 to 256, and using quantized distances from IVF+RaBitQ as keys for the collection process. The experimental results are shown in Table 4, where 𝑚 = 80 is the optimal number of buckets as determined by Equation 3. The results indicate that (1) the value of 𝑚 computed by Equation 3 achieves the lowest latency; (2) small deviations from this value result in only marginal latency increases; (3) very small values of 𝑚 cause a substantial latency increase because objects become concentrated in a few buckets, making the final selection costly; and (4) very large values of 𝑚 also increase latency due to more frequent L1 cache misses induced by the large 𝑚. Exp-8: Memory Cost. Table 5 reports the memory cost of BBC under different 𝑘 and 𝑚 settings. The results indicate that the memory cost of BBC is negligible compared to the dataset sizes reported in Table 1 since BBC introduces nearly no additional memory usage.

Table 3: L1 cache miss counts (105 ) of different re-ranking methods under varying values of 𝑘 when 𝑛𝑝𝑟𝑜𝑏𝑒 = 500. 𝑘

𝑚\𝑘

Exp-5: Gap between the relaxed and exact thresholds. We compare the threshold values generated by our proposed result buffer with those produced by the binary heap, thereby empirically validating the effectiveness of the equal-depth method. The experimental results on the C4 dataset are shown in Figure 9. It indicates that the gap between the relaxed and exact threshold values remains consistently small, with differences on the order of 10−2 , thereby validating Theorem B.1. Exp-6: Comparison of Re-ranking Algorithms. We compare our proposed re-ranking algorithm with the naive algorithm, evaluating both their time overhead and the number of items re-ranked. In particular, Figure 10 presents the re-ranking times and the number of re-ranked objects for IVF+PQ, IVF+PQ+BBC, IVF+RaBitQ, and IVF+RaBitQ+BBC on the C4 dataset, based on VTune profiling results. The parameter 𝑛𝑝𝑟𝑜𝑏𝑒 varies as in the previous experiments. We report recall@𝑘 and the corresponding re-ranking times/re-ranked objects for 𝑘 = 5,000, 10,000, 20,000, 40,000, and 100,000. The key observations are as follows: (1) Our re-rank algorithms significantly accelerate the re-ranking process. Specifically, when 𝑘 = 20,000 and recall@𝑘 = 0.95, IVF+RaBitQ+BBC requires about 32 ms per query, whereas IVF+PQ takes around 18 ms, achieving a 1.8× speedup. Similarly, when 𝑘 = 20,000 and recall@𝑘 = 0.95, IVF+PQ+BBC requires approximately 45 ms per query for re-ranking, compared to about 60 ms for IVF+PQ, resulting in a 1.3× speedup. The speedup of IVF+RaBitQ+BBC mainly results from a reduction in the number of re-ranked items, while the speedup of IVF+PQ+BBC can be attributed to reduced cache misses, as detailed below. (2) The number of re-ranked objects in IVF+RaBitQ+BBC is significantly reduced compared to IVF+RaBitQ. Specifically, when 𝑘 = 100,000 and recall@𝑘 = 0.95, IVF+RaBitQ re-ranks 450,067 objects, whereas IVF+RaBitQ+BBC re-ranks 223,142 objects, representing a reduction of nearly 50%. This result is consistent with the 1.8× speedup observed above. Notably, the number of re-ranked objects in IVF+RaBitQ+BBC is only slightly higher than that in the minimal re-ranking scenario of IVF+RaBitQ+MIN, demonstrating the effectiveness of our method. (3) The L1 cache miss count of IVF+PQ+BBC is significantly lower than that of IVF+PQ. As shown in Table 3, when 𝑘 = 100, 000, the L1 cache miss count is reduced from 7.61 ×105 to 5.23 ×105 , corresponding to a 1.45× reduction, which demonstrates the effectiveness of Algorithm 4.

RELATED WORK

Approximate Nearest Neighbor Search. Various Approximate Nearest Neighbor (ANN) search methods have been proposed [13, 44, 52, 60, 63], which are typically classified into four categories: graph-based methods [7, 16, 17, 26, 47, 48, 83], quantization methods [8, 14, 19, 20, 22, 23, 32, 33, 50, 52, 61, 70, 78, 86, 91], hashingbased methods [11, 18, 27, 28, 40, 43, 45, 58, 64, 76–78, 82], and tree-based methods [4, 9, 10, 69, 89]. Among these methods, IVF and graph-based indexes are widely used in industry [42, 60] and quantization methods have proven highly effective in saving memory and accelerating query processing [3, 20, 25, 30]. For a comprehensive overview, we refer readers to recent tutorials [13], benchmark/experimental evaluations [5, 6, 12, 71, 84], and surveys [52, 59, 60] for details. Although ANN queries have been extensively studied, to the best of our knowledge, the large-𝑘 ANN query studied in this work has not yet been specifically investigated. In addition, Large-𝑘 ANN queries cannot be effectively solved with range queries. In practice, range queries in vector search remain underexplored and technically difficult to utilize for two reasons: (1) lack of intuition and semantic meaning of similarity ranges. In highdimensional spaces, the semantic meaning of a similarity threshold (e.g., 0.9) is opaque: the same threshold may return few results for some queries, indicating high similarity, but hundreds of thousands objects for other queries, indicating lower similarity, making it difficult to specify an effective threshold; and (2) high uncertainty in result cardinality: due to the distance concentration phenomenon, the distances from a query vector to data vectors often lie within a very narrow range (e.g., 0.9–1.0), so even a small change in the threshold can result in a dramatic change in the number of returned objects, which makes the results challenging to use effectively. 12

Table 5: Memory cost (MB) of BBC under different 𝑚 and 𝑘. 𝑚\𝑘

5,000

10,000

20,000

40,000

100,000

56 120

2.1 4.6

4.3 9.2

8.5 18.3

17.1 36.6

34.2 73.2

REFERENCES [1] Cecilia Aguerrebere, Ishwar Singh Bhati, Mark Hildebrand, Mariano Tepper, and Theodore L. Willke. 2023. Similarity search in the blink of an eye with compressed indices. Proc. VLDB Endow. 16, 11 (2023), 3433–3446. [2] Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2015. Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan. Proc. VLDB Endow. 9, 4 (2015), 288–299. [3] Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. 2017. Accelerated Nearest Neighbor Search with Quick ADC. In Proceedings of the 2017 ACM on International Conference on Multimedia Retrieval, ICMR 2017, Bucharest, Romania, June 6-9, 2017. 159–166. [4] Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya. 2018. HDIndex: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces. Proceedings of the VLDB Endowment 11, 8 (2018), 906–919. [5] Martin Aumüller, Erik Bernhardsson, and Alexander John Faithfull. 2020. ANNBenchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Inf. Syst. 87 (2020). [6] Martin Aumüller and Matteo Ceccarello. 2023. Recent Approaches and Trends in Approximate Nearest Neighbor Search, with Remarks on Benchmarking. IEEE Data Eng. Bull. 47, 3 (2023), 89–105. [7] Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2025. Graph-based vector search: An experimental evaluation of the state-of-the-art. Proceedings of the ACM on Management of Data 3, 1 (2025), 1–31. [8] Artem Babenko and Victor S. Lempitsky. 2014. Additive Quantization for Extreme Vector Compression. In 2014 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2014, Columbus, OH, USA, June 23-28, 2014. 931–938. [9] Alina Beygelzimer, Sham M. Kakade, and John Langford. 2006. Cover Trees for Nearest Neighbor. In Machine Learning, Proceedings of the Twenty-Third International Conference (ICML 2006), Pittsburgh, Pennsylvania, USA, June 25-29, 2006 (ACM International Conference Proceeding Series), Vol. 148. 97–104. [10] Paolo Ciaccia, Marco Patella, and Pavel Zezula. 1997. M-tree: An E cient access method for similarity search in metric spaces. In Proceedings of the 23rd VLDB conference, Athens, Greece. 426–435. [11] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the 20th ACM Symposium on Computational Geometry, Brooklyn, New York, USA, June 8-11, 2004. 253–262. [12] Magdalen Dobson, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2023. Scaling Graph-Based ANNS Algorithms to Billion-Size Datasets: A Comparative Analysis. CoRR abs/2305.04359 (2023). [13] Karima Echihabi, Themis Palpanas, and Kostas Zoumpatianos. 2021. New Trends in High-d Vector Similarity Search: AI-Driven, Progressive, and Distributed. Proc. VLDB Endow. 14, 12 (2021), 3198–3201. [14] Hakan Ferhatosmanoglu, Ertem Tuncel, Divyakant Agrawal, and Amr El Abbadi. 2000. Vector approximation based indexing for non-uniform high dimensional data sets. In Proceedings of the ninth international conference on Information and knowledge management. 202–209. [15] Michael L Fredman and Robert Endre Tarjan. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM) 34, 3 (1987), 596–615. [16] Cong Fu, Changxu Wang, and Deng Cai. 2022. High Dimensional Similarity Search with Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, 8 (2022), 4139–4150. [17] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Approximate Nearest Neighbor Search with the Navigating Spreading-out Graph. Proceedings of the VLDB Endowment 12, 5 (2019), 461–474. [18] Junhao Gan, Jianlin Feng, Qiong Fang, and Wilfred Ng. 2012. Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, AZ, USA, May 20-24, 2012. 541–552. [19] Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, and Raymond Chi-Wing Wong. 2025. Practical and asymptotically optimal quantization of high-dimensional vectors in euclidean space for approximate nearest neighbor search. Proceedings of the ACM on Management of Data 3, 3 (2025), 1–26. [20] Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proceedings of the ACM on Management of Data 2, 3 (2024), 1–27. [21] Weihao Gao, Xiangjun Fan, Chong Wang, Jiankai Sun, Kai Jia, Wenzi Xiao, Ruofan Ding, Xingyan Bin, Hui Yang, and Xiaobing Liu. 2021. Learning an end-to-end structure for retrieval in large-scale recommendations. In Proceedings of the 30th ACM international conference on information & knowledge management. 524–533. [22] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2014. Optimized Product Quantization. IEEE Trans. Pattern Anal. Mach. Intell. 36, 4 (2014), 744–755.

Quantization. We focus on improving quantization based methods. The quantization of high-dimensional vectors has been extensively explored in the literature [8, 19, 20, 22, 23, 25, 32, 33, 51– 53, 61, 70, 78, 86, 91]. Early research on quantization focuses on reducing quantization error, with Product Quantization (PQ) [22, 32] as the representative method. Recently, RaBitQ [19, 20] is proposed, which provides theoretical bounds for estimated distances. With the help of SIMD-based implementations (a.k.a. FastScan), these methods have achieved great success in accelerating other ANN approaches [2, 19, 20, 24, 25, 30]. In this study, we integrate our proposed BBC into IVF+PQ and IVF+RaBitQ to demonstrate its plug-and-play ability to improve the efficiency of quantization methods for large-𝑘 ANN queries. There are methods that integrate quantization and graph-based approaches. However, these early explorations exhibit limited scalability. For instance, SymphonyQG [24] and NGT-QG [30] encounter out-of-memory errors during indexing on our system due to their substantial memory consumption, which exceeds the available capacity. This is consistent with prior experimental findings [24]. Moreover, LVQ [1] is closed-source. Therefore, we leave the integration of BBC with these methods for future work. Priority Queue. Priority queues have been extensively studied, with the binary heap and its variants being the most common implementations due to their 𝑂 (log(𝑛)) insertion and deletion time complexity [87]. However, in large-𝑘 ANN queries, this theoretical efficiency is no longer effective, as L1 cache misses dominate the runtime overhead. This observation is consistent with previous experimental evaluations [38], which report a strong correlation between the priority queue’s processing time and L1 cache miss rates. Consequently, studies that focus on optimizing the theoretical time complexity of priority queues [15, 67, 79], such as the Fibonacci heap, offer limited benefits in our context. It is noted that [1] replaces the heap with a sorted linear buffer. Each insertion locates the proper position and shifts all subsequent elements backward to maintain order. The linear buffer’s sequential layout facilitates hardware prefetching, thereby reducing L1 cache misses and outperforming the heap when 𝑘 is small [1]. However, its advantage vanishes with larger 𝑘 due to the 𝑂 (𝑘) insertion cost. Several topk collectors are designed for GPUs [35, 72, 75], such as FAISS’s WarpSelect. However, as reported in [35], these methods also face performance degradation when 𝑘 is large.

CONCLUSIONS AND FUTURE DIRECTIONS

In this paper, we propose a novel bucket-based result collector (BBC) to accelerate quantization-based methods for large-𝑘 ANN queries, which consists of two key components: a bucket-based result buffer and two re-ranking algorithms. One potential future direction is to modify the BBC to support graph-quantization methods for large-𝑘 ANN queries. Another promising direction is adapting BBC for GPU settings to accelerate batch large-𝑘 ANN queries.

[44] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2020. Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement. IEEE Transactions on Knowledge and Data Engineering 32, 8 (2020), 1475–1488. [45] Kejing Lu, Hongya Wang, Wei Wang, and Mineichi Kudo. 2020. VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning. Proc. VLDB Endow. 13, 9 (2020), 1443–1455. [46] Varun Malhotra and Christos Kozyrakis. 2006. Library-based prefetching for pointer-intensive applications. In Technical report. Computer Systems Laboratory, Stanford University. [47] Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate Nearest Neighbor Algorithm Based on Navigable Small World Graphs. 45 (2014), 61–68. [48] Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42, 4 (2020), 824– 836. [49] Yu A Malkov and Dmitry A Yashunin. 2020. hnswlib: Hierarchical Navigable Small World graphs. https://github.com/nmslib/hnswlib. Accessed: 2025-09-09. [50] Julieta Martinez, Shobhit Zakhmi, Holger H. Hoos, and James J. Little. 2018. LSQ++: Lower Running Time and Higher Recall in Multi-codebook Quantization. In Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part XVI (Lecture Notes in Computer Science), Vol. 11220. 508–523. [51] Yusuke Matsui, Ryota Hinami, and Shin’ichi Satoh. 2018. Reconfigurable inverted index. In Proceedings of the 26th ACM international conference on Multimedia. 1715–1723. [52] Yusuke Matsui, Yusuke Uchida, Hervé Jégou, and Shin’ichi Satoh. 2018. A Survey of Product Quantization. ITE Transactions on Media Technology and Applications 6, 1 (2018), 2–10. [53] Yusuke Matsui, Toshihiko Yamasaki, and Kiyoharu Aizawa. 2015. Pqtable: Fast exact asymmetric distance neighbor search for product quantization using hash tables. In Proceedings of the IEEE International Conference on Computer Vision. 1940–1948. [54] Luke Merrick. 2024. Embedding And Clustering Your Data Can Improve Contrastive Pretraining. arXiv preprint arXiv:2407.18887 (2024). [55] Jason Mohoney, Anil Pacaci, Shihabur Rahman Chowdhury, Ali Mousavi, Ihab F Ilyas, Umar Farooq Minhas, Jeffrey Pound, and Theodoros Rekatsinas. 2023. High-throughput vector similarity search in knowledge graphs. Proceedings of the ACM on Management of Data 1, 2 (2023), 1–25. [56] Hamid Mousavi and Carlo Zaniolo. 2011. Fast and accurate computation of equi-depth histograms over data streams. In Proceedings of the 14th international conference on extending database technology. 69–80. [57] M Muralikrishna and David J DeWitt. 1988. Equi-depth multidimensional histograms. In Proceedings of the 1988 ACM SIGMOD international conference on Management of data. 28–36. [58] Parth Nagarkar and K Selçuk Candan. 2018. Pslsh: An index structure for efficient execution of set queries in high-dimensional spaces. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management. 477– 486. [59] James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Survey of vector database management systems. VLDB J. 33, 5 (2024), 1591–1615. [60] James Jie Pan, Jianguo Wang, and Guoliang Li. 2024. Vector Database Management Techniques and Systems. In Companion of the 2024 International Conference on Management of Data. Santiago AA Chile, 597–604. [61] John Paparrizos, Ikraduya Edian, Chunwei Liu, Aaron J. Elmore, and Michael J. Franklin. 2022. Fast Adaptive Similarity Search through Variance-Aware Quantization. In 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9-12, 2022. 2969–2983. [62] Liana Patel, Siddharth Jha, Melissa Pan, Harshit Gupta, Parth Asawa, Carlos Guestrin, and Matei Zaharia. 2025. Semantic Operators and Their Optimization: Enabling LLM-Based Data Processing with Accuracy Guarantees in LOTUS. Proceedings of the VLDB Endowment 18, 11 (2025), 4171–4184. [63] Marco Patella and Paolo Ciaccia. 2009. Approximate similarity search: A multifaceted problem. Journal of Discrete Algorithms 7, 1 (2009), 36–48. [64] Ninh Pham and Tao Liu. 2022. Falconn++: A locality-sensitive filtering approach for approximate nearest neighbor search. Advances in Neural Information Processing Systems 35 (2022), 31186–31198. [65] Gregory Piatetsky-Shapiro and Charles Connell. 1984. Accurate estimation of the number of tuples satisfying a condition. ACM Sigmod Record 14, 2 (1984), 256–276. [66] Jeffrey Pound, Floris Chabert, Arjun Bhushan, Ankur Goswami, Anil Pacaci, and Shihabur Rahman Chowdhury. 2025. MicroNN: An On-device Disk-resident Updatable Vector Database. In Companion of the 2025 International Conference on Management of Data. 608–621. [67] William Pugh. 1990. Skip lists: a probabilistic alternative to balanced trees. Commun. ACM 33, 6 (1990), 668–676.

[23] Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. 2013. Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image Retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence 35, 12 (2013), 2916–2929. [24] Yutong Gou, Jianyang Gao, Yuexuan Xu, and Cheng Long. 2025. SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 3, 1 (2025), 80:1–80:26. [25] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating Large-Scale Inference with Anisotropic Vector Quantization. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, Vol. 119. 3887–3896. [26] Ben Harwood and Tom Drummond. 2016. Fanng: Fast approximate nearest neighbour graphs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 5713–5722. [27] Jae-Pil Heo, Youngwoon Lee, Junfeng He, Shih-Fu Chang, and Sung-Eui Yoon. 2015. Spherical Hashing: Binary Code Embedding with Hyperspheres. IEEE Trans. Pattern Anal. Mach. Intell. 37, 11 (2015), 2304–2316. [28] Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. 2015. Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search. Proc. VLDB Endow. 9, 1 (2015), 1–12. [29] Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998. 604–613. [30] Yahoo Japan. 2018. Neighborhood Graph and Tree for Indexing High-dimensional Data. https://github.com/yahoojapan/NGT. Accessed: 2024-04-17. [31] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. Diskann: Fast accurate billion-point nearest neighbor search on a single node. Advances in neural information processing Systems 32 (2019). [32] H Jégou, M Douze, and C Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 1 (2011), 117–128. [33] Wenqi Jiang, Shigang Li, Yu Zhu, Johannes de Fine Licht, Zhenhao He, Runbin Shi, Cédric Renggli, Shuai Zhang, Theodoros Rekatsinas, Torsten Hoefler, and Gustavo Alonso. 2023. Co-design Hardware and Algorithm for Vector Search. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2023, Denver, CO, USA, November 12-17, 2023. 87:1–87:15. [34] Donald B Johnson. 1975. Priority queues with update and finding minimum spanning trees. Inform. Process. Lett. 4, 3 (1975), 53–57. [35] Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-Scale Similarity Search with GPUs. IEEE Transactions on Big Data 7, 3 (2019), 535–547. [36] Sujay Khandagale, Bhawna Juneja, Prabhat Agarwal, Aditya Subramanian, Jaewon Yang, and Yuting Wang. 2025. InteractRank: Personalized Web-Scale Search Pre-Ranking with Cross Interaction Features. In Companion Proceedings of the ACM on Web Conference 2025, WWW 2025, Sydney, NSW, Australia, 28 April 2025 - 2 May 2025. 287–295. [37] Omar Khattab and Matei Zaharia. 2020. Colbert: Efficient and effective passage search via contextualized late interaction over bert. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval. 39–48. [38] Daniel H Larkin, Siddhartha Sen, and Robert E Tarjan. 2014. A back-to-basics empirical study of priority queues. In 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 61–72. [39] Jinhyuk Lee, Zhuyun Dai, Sai Meher Karthik Duddu, Tao Lei, Iftekhar Naim, Ming-Wei Chang, and Vincent Zhao. 2023. Rethinking the role of token retrieval in multi-vector retrieval. Advances in Neural Information Processing Systems 36 (2023), 15384–15405. [40] Yifan Lei, Qiang Huang, Mohan S. Kankanhalli, and Anthony K. H. Tung. 2020. Locality-Sensitive Hashing Scheme Based on Longest Circular Co-Substring. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, Online Conference [Portland, or, USA], June 14-19, 2020. 2589– 2599. [41] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020. Retrieval-augmented generation for knowledge-intensive nlp tasks. Advances in neural information processing systems 33 (2020), 9459–9474. [42] Conglong Li, Minjia Zhang, David G. Andersen, and Yuxiong He. 2020. Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020. 2539–2554. [43] Jinfeng Li, Xiao Yan, Jie Zhang, An Xu, James Cheng, Jie Liu, Kelvin Kai Wing Ng, and Ti-Chung Cheng. 2018. A General and Efficient Querying Method for Learning to Hash. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018. 1333–1347. 14

Collector. In https:// github.com/ Heisenberg-Yin/ BBC/ blob/ main/ BBC_for_VLDB. pdf . Full version manuscript. [91] Ting Zhang, Chao Du, and Jingdong Wang. 2014. Composite Quantization for Approximate Nearest Neighbor Search. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014 (JMLR Workshop and Conference Proceedings), Vol. 32. 838–846. [92] Yanzhao Zhang, Mingxin Li, Dingkun Long, Xin Zhang, Huan Lin, Baosong Yang, Pengjun Xie, An Yang, Dayiheng Liu, Junyang Lin, Fei Huang, and Jingren Zhou. 2025. Qwen3 Embedding: Advancing Text Embedding and Reranking Through Foundation Models. arXiv preprint arXiv:2506.05176 (2025). [93] Wayne Xin Zhao, Jing Liu, Ruiyang Ren, and Ji-Rong Wen. 2024. Dense text retrieval based on pretrained language models: A survey. ACM Transactions on Information Systems 42, 4 (2024), 1–60.

[68] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. 2020. Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer. Journal of Machine Learning Research 21, 140 (2020), 1–67. [69] Parikshit Ram and Kaushik Sinha. 2019. Revisiting Kd-Tree for Nearest Neighbor Search. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019. 1378–1388. [70] Patrick Schäfer, Jakob Brand, Ulf Leser, Botao Peng, and Themis Palpanas. 2024. Fast and Exact Similarity Search in less than a Blink of an Eye. CoRR abs/2411.17483 (2024). [71] Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamny, Gopal Srinivasa, et al. 2022. Results of the NeurIPS’21 challenge on billion-scale approximate nearest neighbor search. In NeurIPS 2021 Competitions and Demonstrations Track. 177–189. [72] Nikos Sismanis, Nikos Pitsianis, and Xiaobai Sun. 2012. Parallel search of knearest neighbors with synchronous operations. In 2012 IEEE Conference on High Performance Extreme Computing. IEEE, 1–6. [73] Yifang Sun, Wei Wang, Jianbin Qin, Ying Zhang, and Xuemin Lin. 2014. SRS: solving c-approximate nearest neighbor queries in high dimensional euclidean space with a tiny index. Proceedings of the VLDB Endowment (2014). [74] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. 2015. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition. 1–9. [75] Xiaoxin Tang, Zhiyi Huang, David Eyers, Steven Mills, and Minyi Guo. 2015. Efficient selection algorithm for fast k-nn search on gpus. In 2015 IEEE International Parallel and Distributed Processing Symposium. IEEE, 397–406. [76] Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis. 2010. Efficient and Accurate Nearest Neighbor and Closest Pair Search in High-Dimensional Space. ACM Transactions on Database Systems 35, 3 (2010), 20:1–20:46. [77] 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. [78] Ertem Tuncel, Hakan Ferhatosmanoglu, and Kenneth Rose. 2002. VQ-Index: An Index Structure for Similarity Searching in Multimedia Databases. In Proceedings of the 10th ACM International Conference on Multimedia 2002, Juan Les Pins, France, December 1-6, 2002. 543–552. [79] Jean Vuillemin. 1978. A data structure for manipulating priority queues. Commun. ACM 21, 4 (1978), 309–315. [80] Jianguo Wang, Eric Hanson, Guoliang Li, Yannis Papakonstantinou, Harsha Simhadri, and Charles Xie. 2024. Vector Databases: What’s Really New and What’s Next?(VLDB 2024 Panel). Proceedings of the VLDB Endowment 17, 12 (2024), 4505–4506. [81] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. In SIGMOD ’21: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021. 2614–2627. [82] Jingdong Wang, Ting Zhang, Jingkuan Song, Nicu Sebe, and Heng Tao Shen. 2018. A Survey on Learning to Hash. IEEE Trans. Pattern Anal. Mach. Intell. 40, 4 (2018), 769–790. [83] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search. Proceedings of the VLDB Endowment 14, 11 (2021), 1964–1978. [84] Zeyu Wang, Peng Wang, Themis Palpanas, and Wei Wang. 2023. Graph- and Tree-based Indexes for High-dimensional Vector Similarity Search: Analyses, Comparisons, and Future Directions. IEEE Data Eng. Bull. 47, 3 (2023), 3–21. [85] Roger Weber, Hans-Jörg Schek, and Stephen Blott. 1998. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. In VLDB’98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. 194–205. [86] Roger Weber, Hans-Jörg Schek, and Stephen Blott. 1998. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. In VLDB’98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. 194–205. [87] John William Joseph Williams. 1964. Algorithm 232: heapsort. Commun. ACM 7, 6 (1964), 347–348. [88] Wen Yang, Tao Li, Gai Fang, and Hong Wei. 2020. Pase: Postgresql ultra-highdimensional approximate nearest neighbor search extension. In Proceedings of the 2020 ACM SIGMOD international conference on management of data. 2241–2253. [89] Peter Yianilos. 1993. Data structures and algorithms for nearest neighbor search in general metric spaces. (1993). [90] Ziqi Yin, Gao Cong, Kai Zeng, Jinwei Zhu, and Bin Cui. 2026. BBC: Improving Large-𝑘 Approximate Nearest Neighbor Search with a Bucket-based Result 15

THE CORRECTNESS PROOF OF ALGORITHM 2

Let 𝑅b be the quantized distance obtained by mapping 𝑅 ∈ [𝑏𝑖 , 𝑏𝑖+1 ] to its upper bound 𝑏𝑖+1

Proof. As described in Algorithm 2, after the scanning phase (lines 2-11), we obtain two heaps: a max-heap 𝐻𝑢 of size 𝑘 and a min-heap 𝐻𝑙 . Clearly, the top-𝑘 results returned by the RaBitQ must be contained in 𝐻𝑢 or 𝐻𝑙 . There are two possible cases:

𝑅b =

𝑏𝑖+1 1{𝑅 ∈ [𝑏𝑖 , 𝑏𝑖+1 ]}.

𝑖=1

Then, the expected mean absolute error of the equal-depth quantization method satisfies the following expression, where 𝑐 0 is a constant. √︄ √ √︂ log(4𝑚) 𝜋 2− 2 b ≤ E|𝑅 − 𝑅| + + , 𝑐 0𝑑 𝑐 0𝑑 𝑚

(1) 𝐻𝑢 are the final top-𝑘 results. In this scenario, the object at the top of 𝐻𝑢 cannot be avoided for re-ranking. This is because its upper bound is the 𝑘-th largest and thus greater than Dist𝑘 (the exact distance of the 𝑘-th object), while its lower bound must be less than Dist𝑘 since it is included in the top-𝑘 results. (2) Some objects in 𝐻𝑙 may enter the final top-𝑘. In this case, the object at the top of 𝐻𝑙 must also be re-ranked. This is because its lower bound is smaller than those of other objects in 𝐻𝑙 that enter the top-𝑘, meaning its lower bound is less than Dist𝑘 . At the same time, its upper bound exceeds the 𝑘-th upper bound, and thus is also greater than Dist𝑘 .

PROOF OF THEOREM B.1

Lemma C.1. Let 𝑞, 𝑜 ∈ R𝑑 be independently and uniformly sampled from the unit sphere, then with high probability, their Euclidean √ distance 𝑅 = ∥𝑞 − 𝑜 ∥ concentrates around 2 at scale √1 . 𝑑

Proof. Let 𝑋 = ⟨𝑞, 𝑜⟩. By the identity ∥𝑞 − 𝑜 ∥ 2 = ∥𝑞∥ 2 + ∥𝑜 ∥ 2 − 2⟨𝑞, 𝑜⟩ = 2 − 2𝑋, we have the one-to-one transformation 𝑌 = 2 − 2𝑋 with inverse 𝑋 = 1 − 𝑌2 mapping 𝑋 ∈ [−1, 1] to 𝑌 ∈ [0, 4].

Therefore, in both cases, at least one of the objects at the top of 𝐻𝑢 or 𝐻𝑙 must be re-ranked. We further prove that the object with the smaller lower bound between the two is guaranteed to require re-ranking. Similarly, there are two cases to consider.

Step 1 (Law of the inner product). By rotational invariance of inner products under orthogonal transformations [20], we may fix 𝑜 = 𝑒 1 = (1, 0, . . . , 0) without loss of generality. Then 𝑋 = ⟨𝑞, 𝑜⟩ has the same distribution as the first coordinate 𝑞[0] of a uniformly sampled point 𝑞 on the unit sphere, whose probability density function is given as [20]:

(1) If the object at the top of 𝐻𝑢 has the smaller lower bound, it must be re-ranked. If it belongs to the top-𝑘, it must be re-ranked as discussed above. If it does not belong to the top-𝑘, its lower bound remains smaller than that of the top object in 𝐻𝑙 , and its upper bound is the 𝑘-th upper bound; therefore, it must also be re-ranked. (2) If the object at the top of 𝐻𝑙 has the smaller lower bound, it is also unavoidable for re-ranking. This is because its predicted distance interval entirely covers that of the object at the top of 𝐻𝑢 , and thus intersects with Dist𝑘 .

Γ( 𝑑2 ) 𝑑 −3 1 − 𝑥2 2 , 𝑓𝑋 (𝑥) = √ 𝜋 Γ( 𝑑 −1 ) 2

𝑥 ∈ [−1, 1].

Step 2 (A tail bound and concentration of ∥𝑞 − 𝑜 ∥ 2 around 2). In particular, there exists an absolute constant 𝑐 0 > 0 such that for all 𝑡 ≥ 0, 𝑡 P |𝑋 | > √ ≤ 2 exp(−𝑐 0𝑡 2 ). 𝑑 which is proven in the appendix of [20]. Since 𝑌 = 2 − 2𝑋 , we have |𝑌 − 2| = 2|𝑋 |, hence 2𝑡 𝑡 P ∥𝑞 − 𝑜 ∥ 2 − 2 > √ = P |𝑋 | > √ ≤ 2 exp(−𝑐 0𝑡 2 ) 𝑑 𝑑 Equivalently, 2𝑡 2𝑡 2 ≥ 1 − 2 exp(−𝑐 0𝑡 2 ), P 2 − √ ≤ ∥𝑞 − 𝑜 ∥ ≤ 2 + √ 𝑑 𝑑 which captures the concentration of the squared distance around 2 with high probability. √ Step 3 (Concentration of the distance 𝑅 around 2). Recall that √ 𝑅 = ∥𝑞 − 𝑜 ∥ = 2 − 2𝑋 . On the interval |𝑋 | ≤ 12 , the mean value √ theorem together with 𝑔′ (𝑥) = −1/ 2 − 2𝑥 implies |𝑔′ (𝑥)| ≤ 1. Hence, when |𝑋 | ≤ 12 , we have √ 𝑅 − 2 = |𝑔(𝑋 ) − 𝑔(0)| ≤ |𝑋 |.

The above consideration is based on the case where neither of the top objects from the two heaps has been re-ranked. We now consider the case where the top object in 𝐻𝑢 has already been evaluated. (1) 𝐻𝑢 are the final top-𝑘 results. In this scenario, the distance between the object at the top of 𝐻𝑢 and the query is Dist𝑘 . If the lower bound of the top of 𝐻𝑙 is smaller than Dist𝑘 , it needs to be re-ranked. (2) Some objects in 𝐻𝑙 may enter the final top-𝑘. In this case, the object at the top of 𝐻𝑙 must also be re-ranked, as in the previous situation. □

𝑚 ∑︁

THEOREM B.1

Theorem B.1 (Expected Mean Absolute Error). Let 𝑞, 𝑜 ∈ R𝑑 be independently and uniformly sampled from the unit sphere. Let 𝑅 = ∥𝑞 − 𝑜 ∥ 2 ∈ [0, 2] denote the Euclidean distance between them, with 𝐹 (𝑟 ) = P(𝑅 ≤ 𝑟 ) being its cumulative distribution function (CDF). For an integer 𝑚 ≥ 2, consider the equal-depth partition determined by the quantiles −1 𝑏𝑖 := 𝐹 −1 𝑖𝑚 , 𝑖 = 1, . . . , 𝑚 + 1 (𝑏 1 = 0, 𝑏𝑚+1 = 2).

Therefore, when |𝑋 | ≤ 12 , for any 𝑡 ≥ 0, √ P 𝑅 − 2 > √𝑡 ≤ P |𝑋 | > √𝑡 ≤ 2 exp(−𝑐 0𝑡 2 ). 𝑑

𝑑

√

For the case |𝑋 | > 12 , note that setting 𝑡 = 2𝑑 in the same bound yields −𝑐 0𝑑 P |𝑋 | > 12 ≤ 2 exp( ) 4 Combining these estimates gives √ −𝑐 0𝑑 ≤ 2 exp(−𝑐 0𝑡 2 ) + 2 exp( ). P 𝑅 − 2 ≥ √𝑡 𝑑 4 when 𝑑 ranges from hundreds to thousands, the second term is on the order of exp(−100), which is very √ close to 0 and negligible. Thus √ 𝑅 concentrates around 2 at scale 1/ 𝑑 with high probability. □

valid for any constant 𝑐. With 𝑎 = 𝑏𝑖 , 𝑏 = 𝑏𝑖+1, 𝑐 = 𝑏𝑖+1 , we obtain ∫ 𝑏𝑖+1 ∫ 𝑏𝑖+1 𝐹 (𝑟 ) 𝑑𝑟 . (𝑏𝑖+1 − 𝑟 ) 𝑑𝐹 (𝑟 ) = −(𝑏𝑖+1 − 𝑏𝑖 )𝐹 (𝑏𝑖 ) +

Theorem C.2 (Expected Mean Absolute Error). Let 𝑞, 𝑜 ∈ R𝑑 be independently and uniformly sampled from the unit sphere, and define 𝑅 = ∥𝑞 − 𝑜 ∥ ∈ [0, 2], 𝐹 (𝑟 ) = P(𝑅 ≤ 𝑟 ).

Step 3. Using equal-depth quantiles. By construction of the equal-depth partition, we have

For an integer 𝑚 ≥ 2, consider the equal-depth partition determined by the quantiles −1 𝑏𝑖 := 𝐹 −1 𝑖𝑚 , 𝑖 = 1, . . . , 𝑚 + 1, (𝑏 1 = 0, 𝑏𝑚+1 = 2).

Therefore, 𝑚 ∑︁

On each interval [𝑏𝑖 , 𝑏𝑖+1 ], use the upper distance 𝑏𝑖+1 as the representative value, and define the quantized variable

Hence,

𝑅b :=

𝑚 ∑︁

𝑏𝑖

Summing over 𝑖 = 1, . . . , 𝑚 yields ∫ 𝑏𝑖+1 𝑚 h i ∑︁ b = E |𝑅 − 𝑅| −(𝑏𝑖+1 − 𝑏𝑖 )𝐹 (𝑏𝑖 ) + 𝐹 (𝑟 ) 𝑑𝑟 ∫ 2 𝐹 (𝑟 ) 𝑑𝑟 −

= 0

𝑚 ∑︁

(𝑏𝑖+1 − 𝑏𝑖 )𝐹 (𝑏𝑖 ).

(10)

𝑖=1

𝐹 (𝑏𝑖 ) =

𝑖 −1 , 𝑚

𝑖 = 1, . . . , 𝑚.

𝑚

(𝑏𝑖+1 − 𝑏𝑖 )𝐹 (𝑏𝑖 ) =

𝑖=1

1 ∑︁ (𝑖 − 1)(𝑏𝑖+1 − 𝑏𝑖 ). 𝑚 𝑖=1 𝑚

∫ 2 b = E |𝑅 − 𝑅|

𝐹 (𝑟 ) 𝑑𝑟 − 0

𝑏𝑖+1 1{𝑅 ∈ [𝑏𝑖 , 𝑏𝑖+1 ]}.

(9)

𝑏𝑖

𝑖=1

1 ∑︁ (𝑖 − 1)(𝑏𝑖+1 − 𝑏𝑖 ). 𝑚 𝑖=1

Expand the summation:

𝑖=1 𝑚 ∑︁

Then the expected mean absolute error satisfies √︄ √ √︂ log(4𝑚) 𝜋 2− 2 b ≤ E|𝑅 − 𝑅| + + 𝑐 0𝑑 𝑐 0𝑑 𝑚

(𝑖 − 1)(𝑏𝑖+1 − 𝑏𝑖 ) = (𝑚 − 1)𝑏𝑚+1 −

𝑖=1

∫ 2 b = E |𝑅 − 𝑅|

𝐹 (𝑟 ) 𝑑𝑟 − 0

Proof. We define the quantized variable of 𝑅 by 𝑅b :=

𝑏𝑖+1 .

𝑖=1

Therefore,

where 𝑐 0 is constant.

𝑚 ∑︁

𝑚−1 ∑︁

𝑚−1 ∑︁ 1 𝑏𝑖+1 . (𝑚 − 1)𝑏𝑚+1 − 𝑚 𝑖=1

Since 𝑏𝑚+1 = 2, this further simplifies to ∫ 2 𝑚−1 2 1 ∑︁ b = 𝑏𝑖+1 . E |𝑅 − 𝑅| 𝐹 (𝑟 ) 𝑑𝑟 − 2 + + 𝑚 𝑚 𝑖=1 0

𝑏𝑖+1 1{𝑅 ∈ [𝑏𝑖 , 𝑏𝑖+1 ]},

𝑖=1

that is, 𝑅b takes the upper distance 𝑏𝑖+1 whenever 𝑅 falls into the 𝑖-th quantile interval.

Recall the general identity ∫ 2 𝐹 (𝑟 ) 𝑑𝑟 = 2 − E[𝑅].

Step 1. Reformulation of the error. The mean absolute error can be written as 𝑚 ∑︁ b = |𝑅 − 𝑅| (𝑏𝑖+1 − 𝑅) 1{𝑅 ∈ [𝑏𝑖 , 𝑏𝑖+1 ]}.

Substituting this, we arrive at the exact expression 𝑚−1 ∑︁ b = − E[𝑅] + 2 + 1 E |𝑅 − 𝑅| 𝑏𝑖+1 . 𝑚 𝑚 𝑖=1

𝑖=1

Taking expectation gives b = E |𝑅 − 𝑅|

𝑚 ∑︁

E[(𝑏𝑖+1 − 𝑅) 1{𝑅 ∈ [𝑏𝑖 , 𝑏𝑖+1 ]}]

Step 4. Dimension-dependent bound. Rewrite the exact identity √ by adding and subtracting 2: √ ∑︁ √ √ 2− 2 1 𝑚−1 b E|𝑅 − 𝑅| = 2 − E[𝑅] + 𝑏𝑖+1 − 2 + . 𝑚 𝑖=1 𝑚

(7)

𝑖=1

𝑚 ∫ 𝑏𝑖+1 ∑︁ 𝑖=1

(𝑏𝑖+1 − 𝑟 ) 𝑑𝐹 (𝑟 ),

(8)

𝑏𝑖

Taking absolute values on the first two terms and applying the triangle inequality yields: √ 𝑚−1 ∑︁ √ √ 2− 2 b ≤ E[𝑅] − 2 + 1 E|𝑅 − 𝑅| 𝑏𝑖+1 − 2 + . (11) 𝑚 𝑖=1 𝑚 | {z } | {z } (𝐼 )

where 𝐹 (𝑟 ) = P(𝑅 ≤ 𝑟 ) is the cumulative distribution function of 𝑅. Step 2. Stieltjes integration by parts. For each interval [𝑏𝑖 , 𝑏𝑖+1 ], apply the integration-by-parts identity ∫ 𝑏 ∫ 𝑏 (𝑐 − 𝑟 ) 𝑑𝐹 (𝑟 ) = −(𝑐 − 𝑎)𝐹 (𝑎) + 𝐹 (𝑟 ) 𝑑𝑟, 𝑎

(𝐼 𝐼 )

𝑎 17

Table 6: The 𝑛 cand parameter of IVF+PQ across different datasets and 𝑘 settings. 𝑘

WiKi

MSMARCO

Deep100M

10 100 500 1,000 2,500 5,000 10,000 20,000 40,000 100,000

500 2,500 8,000 15,000 30,000 50,000 80,000 150,000 240,000 500,000

500 2,500 8,000 15,000 30,000 50,000 80,000 140,000 240,000 500,000

600 3,000 15,000 30,000 50,000 70,000 100,000 180,000 280,000 600,000

1,000 5,000 20,000 40,000 60,000 100,000 140,000 240,000 320,000 700,000

h i h i 1 1 For each 𝑖 ∈ {1, . . . , 𝑚−1} we have 𝑚𝑖 ∈ 𝑚1 , 1− 𝑚1 ⊂ 2𝑚 . , 1− 2𝑚 By the monotonicity of 𝐹 and the definition of the (left-continuous) quantile function 𝐹 −1 , this implies √ √ 𝑏𝑖+1 = 𝐹 −1 𝑚𝑖 ∈ [ 𝑎, 𝑏 ] = [ 2 − 𝜀𝑚 , 2 + 𝜀𝑚 ],

Control of (𝐼 ). By the preceding lemma, we get ∫ ∞ √ √ √ |E[𝑅] − 2| ≤ E(|𝑅 − 2|) = P |𝑅 − 2| ≥ 𝑢 𝑑𝑢. 0

Let 𝑢 = √𝑡 , then 𝑑𝑢 = √1 𝑑𝑡, we have 𝑑 𝑑

∫ ∞ ∫ ∞ hence √ 1 √ P |𝑅 − 2| ≥ √𝑡 𝑑𝑡 ≤ √ 2𝑒𝑥𝑝 (−𝑐 0𝑡 2 ) 𝑑𝑡 . 𝑖 = 1, . . . , 𝑚 − 1. 𝑏𝑖+1 − 2 ≤ 𝜀𝑚 , 𝑑 0 𝑑 0 we then have for every 1 ≤ 𝑖 ≤ 𝑚 − 1 The Gaussian integral can be evaluated explicitly: √︄ 𝑚−1 √︂ ∫ ∞ √ log(4𝑚) 1 ∑︁ 2 1 𝜋 |𝑏𝑖+1 − 2| ≤ 𝜀𝑚 = 𝑒 −𝑐 0𝑡 𝑑𝑡 = . 𝑚 𝑐 0𝑑 𝑖=1 2 𝑐 √ 1 E |𝑅− 2| = √ 𝑑

(16)

Conclusion. Combining the above equations yields √︄ √ √︂ log(4𝑚) 𝜋 2− 2 b + + E|𝑅 − 𝑅| ≤ 𝑐 0𝑑 𝑐 0𝑑 𝑚

Hence, √ 1 1 E |𝑅 − 2| ≤ √ · 2 · 2 𝑑

√︂

𝜋 1 =√ 𝑐0 𝑑

√︂

𝜋 . 𝑐0

Therefore, √ |E[𝑅] − 2| ≤

√︂

□ 𝜋 . 𝑐 0𝑑

For 𝑑 ranges from hundreds to thousands, the second term is negligible, then we set 𝜀𝑚 to make the first term equal to 1/(2𝑚): √︄ log(4𝑚) 1 2 ⇐⇒ 𝜀𝑚 = . (13) 2 exp −𝑐 0𝑑 𝜀𝑚 = 2𝑚 𝑐 0𝑑 Combining above equations gives √ P 𝑅 − 2 ≥ 𝜀𝑚 ≤

and

1 . 2𝑚

EXPERIMENTAL SETTINGS

Details of the evaluated methods are provided below: • IVF [32]: A representative ANN index. The accuracy-efficiency trade-off is controlled by the hyperparameter 𝑛𝑝𝑟𝑜𝑏𝑒 . • HNSW [48]: A popular graph-based ANN index. The accuracyefficiency trade-off is controlled by the hyperparameter 𝑒 𝑓𝑠𝑒𝑎𝑟𝑐ℎ . • IVF+PQ [22]: This method integrates the representative unbounded quantization technique, product quantization (PQ), with the IVF index. At query time, each query is routed to the 𝑛𝑝𝑟𝑜𝑏𝑒 nearest clusters, within which the search procedure of PQ is applied, as detailed above. The accuracy-efficiency trade-off is controlled by the hyperparameters 𝑛𝑐𝑎𝑛𝑑 and 𝑛𝑝𝑟𝑜𝑏𝑒 . • IVF+RaBitQ [20]: This method integrates the representative bounded quantization method RaBitQ with the IVF index. At query time, each query is routed to the 𝑛𝑝𝑟𝑜𝑏𝑒 nearest clusters, within which the search procedure of RaBitQ is applied, as detailed above. The accuracy-efficiency trade-off is controlled by the hyperparameter 𝑛𝑝𝑟𝑜𝑏𝑒 . The dataset statistics are shown below. • WiKi: The WiKi dataset comprises 10 million corpus sampled from the Wikipedia dataset2 , which serves as the open-source

Control of (𝐼𝐼 ). We substitute 𝜖 = √𝑡 into the preceding lemma, 𝑑 then there is 𝑐 0 > 0 such that for all 𝜀 ∈ (0, 1), √ −𝑐 0𝑑 ). P |𝑅 − 2| ≥ 𝜀 ≤ 2 exp(−𝑐 0𝑑 𝜀 2 ) + 2 exp( 4 We proceed to choose a 𝜖 = 𝜀𝑚 that satisfies 𝑐 0𝑑 1 2 2 exp −𝑐 0𝑑 𝜀𝑚 + 2 exp − ≤ . (12) 4 2𝑚

Then this is equivalent to √ 1 𝐹 ( 2 − 𝜖𝑚 ) ≤ 2𝑚

(15)

(14)

√ 1 𝐹 ( 2 + 𝜖𝑚 ) ≥ 1 − . 2𝑚

2 https://huggingface.co/datasets/Cohere/wikipedia-22-12-en-embeddings

backbone for large language model pre-training. The embeddings are generated using the gte-Qwen2-1.5B-instruct model [92]. The query set 𝑄 consists of 1,000 randomly selected passages. • C4: The C4 dataset3 is a large-scale open-source corpus designed for natural language pre-training. We select 40 JSON files from the training set, which contains over 14 million passages, and generate embeddings using the T5 model [68]. The query set 𝑄 consists of 1,000 randomly selected passages. • MSMARCO: The MSMARCO dataset4 comprises 18 million passages sampled from the MSMARCO-V2.1 dataset, which is used as the corpora for The TREC 2024 RAG Track. The embeddings are generated using the Snowflake’s Arctic-embed-m-v1.5 model [54]. The query set 𝑄 consists of 1,000 randomly selected passages. • Deep100M: The Deep100M dataset [71] is the largest benchmark commonly used for ANN evaluation. The embeddings are obtained from an image descriptor dataset, where each embedding

is produced by the GoogLeNet model [74]. The official 100K query set is used in our experiments. Table 6 reports the optimal 𝑛𝑐𝑎𝑛𝑑 values for different datasets and 𝑘. For each dataset–𝑘 combination, 𝑛𝑐𝑎𝑛𝑑 is determined to maximize QPS at a recall of 0.95, while ensuring that recall can reach 0.98.

LATENCY OF TOP-𝑘 COLLECTORS

Figure 11 shows the results on Deep100M and similar trends are observed on other datasets. The results show that: RB significantly accelerates top-𝑘 collection based on estimated distances compared to Heap and Lazy. In particular, on the Deep100M dataset, when 𝑘 = 100,000 and 𝑛𝑝𝑟𝑜𝑏𝑒 = 210, for IVF+RaBitQ, RB buffer requires only 9.2 ms, compared to 36.2 ms for Heap and 18.9 ms for Lazy, achieving a 2.1× speedup. 3 https://huggingface.co/datasets/allenai/c4/ 4 https://huggingface.co/datasets/Snowflake/msmarco-v2.1-snowflake-arctic-embed-

m-v1.5

IVF+RaBitQ+Heap k = 5,000

Time (ms)

IVF+RaBitQ+d-Heap k = 10,000

IVF+RaBitQ+Sorted k = 20,000

IVF+RaBitQ+Lazy k = 40,000

IVF+RaBitQ+RB k = 100,000

Evaluated Objects (106) Evaluated Objects (106) Evaluated Objects (106) Evaluated Objects (106) Evaluated Objects (106) Figure 11: Top-𝑘 collection time under different numbers of evaluated objects on the Deep100M dataset.

BBC: Improving Large-k Approximate Nearest Neighbor Search with a Bucket-based Result Collector

Related documents