B+ANN: A Fast Billion-Scale Disk-based Nearest-Neighbor Index

1 INTRODUCTION

• ANN search balances speed and accuracy, yet many indexes assume in-memory storage and neglect memory and disk retrievals and data locality.The introduction frames these as factors in search speed alongside the number of distance computations.Source: §1 · p. 1
• In multi-turn RAG, temporally related questions may retrieve overlapping information, while most VDBs are described as lacking mechanisms to exploit query temporal correlation.The introduction also notes that most VDBs focus on similar vectors, unlike relational systems that support dissimilar queries.Source: §1 · p. 2
• B+ANN recursively clusters vectors, uses centroids as B+ tree keys and vectors as values, and adds skip-connections between in-memory leaf nodes.The design aims to keep semantically related vectors physically close and enable hybrid tree and graph traversal.Source: §1 · p. 2
• B+ANN introduces semantic views for query-specific subsets, and reports that views can survive up to 1,000 temporally correlated queries.Subsequent related queries are answered from the query-specific view.Source: §1 · p. 2
• The paper reports up to 19.23% relative gain in cache misses and 24x lower index build time, while also supporting dissimilarity queries.The introduction attributes these contributions to semantic locality and coarser-grained computation.Source: §1 · p. 2

2 RELATED WORK

• ANN approaches mainly partition vector spaces to reduce search space or navigate proximity graphs toward nearby vectors.Partitioning includes clustering, hashing, and tree-based solutions.Source: §2 · pp. 2–3
• Clustering and quantization methods reduce or encode search spaces, but IVF can create overly populated subspaces.The cited approaches include IVF, PQ, and IVFPQ.Source: §2 · p. 3
• Hash-based LSH maps close vectors to shared buckets and offers sub-linear search with theoretical accuracy guarantees, but large hash tables can underperform newer graph methods.Tree-based methods include KD-Tree, R-Tree, and M-Tree, with high-dimensional variants facing deep or unbalanced trees and ignored insertions.Source: §2 · p. 3
• Graph approaches connect vectors by distance, while hybrid methods combine clustering and graphs but can incur per-vertex locking or high memory requirements.The section also notes random seeds and random memory access as sources of cache misses.Source: §2 · p. 3
• Disk-based ANN methods scale with modest memory, but DiskANN incurs random disk-access latency, HM-ANN uses more fast memory, and SPANN uses only tree leaves.SPANN also requires in-search updates to keep its tree balanced.Source: §2 · p. 3

3.1 Random Accesses of HNSW

• HNSW’s greedy traversal starts randomly and accesses nodes with cache misses and slower memory accesses, a problem that worsens for disk-resident execution.Each node visit performs a fine-grained pairwise distance calculation; Figure 1 contrasts 140 HNSW steps with 23 B+ANN steps.Source: §3.1 · p. 3, Figure 1 · p. 4
• B+ANN places semantically related vectors near one another and batches leaf vectors for distance calculations, including vector–matrix operations.A leaf access loads multiple vectors, and the next leaf is nearby during traversal.Source: §3.1 · pp. 3–4

3.2 The Temporal Correlation in Retrievals

• In MTRAG, the probability of retrieving the same documents across turns decreases from 0.7 to 0.4 as turns increase.The passage presents this as evidence of temporal relationships between consecutive queries.Source: §3.2 · p. 4
• B+ANN’s query-specific views answer related subsequent queries in memory, while adjacent-leaf traversal maps temporal relations to spatial locality.The described view’s recall is highest at creation and degrades as more queries arrive.Source: §3.2 · p. 4

• Brute-force k-NN search is impractical for collections far larger than billions, motivating approximate methods that trade efficiency for accuracy.Source: §4 · p. 5
• A k-ANN index maps a query to a candidate subset and returns approximate neighbors sufficiently close to the true neighbors.Source: §4 · p. 5
• B+ANN combines tree partitioning with skip-edge graph traversal to reach query-near vectors through both structures.Source: §4 · p. 5
• Tree-based indexing navigates hierarchical partitions from root to leaves, while graph-based indexing routes among candidate subsets until a stopping condition is met.Source: §4 · p. 5
• A view is a query-derived subtree built from k approximate neighbors and used to serve later queries.Source: §4 · p. 5

5.1 Recursively Partitioning by Hierarchical Clustering

• B+ANN recursively partitions data with K-means++ until clusters meet a size threshold, adapting partitions to non-uniform density.Source: §5.1 · p. 5

5.2 Building and Indexing B+ANN Tree

• The tree is built by adding centroid–cluster pairs from the clustering hierarchy, splitting full inner nodes to maintain a wide, balanced structure.Source: §5.2 · p. 7
• Adjacent tree nodes and vectors within each node are stored close together on disk, improving spatial locality for temporarily related queries.Source: §5.2 · p. 7

5.3 Building and Traversing the Skip Connections

• Skip-edges connect neighboring regions to address boundary errors: inter-connections hop between nodes, while intra-connections enable local searches within a node.Source: §5.3 · p. 7
• Greedy search starts from tree-search outputs, explores their edges, and retains the top-k nearest vectors, allowing multiple seeds to traverse branches concurrently.Source: §5.3 · p. 8

5.4 View Creation and B+ANN Usage

• A view connects the leaves of a query-derived subtree with skip-edges; temporarily correlated queries can reuse it for up to 1000 queries.Source: §5.4 · pp. 8–9
• Views can bound dissimilarity search to a query’s topical context, such as finding a dissimilar cereal without retrieving unrelated items.Source: §5.4 · p. 9

6.1 Datasets and Experimental Setup

• Glove-1.2M tests cosine distance, SIFT-1B tests Euclidean distance at one billion 128-dimensional vectors, and Spotify supports low-scale dissimilarity-search experiments.The evaluation measures 10-Recall and queries per second; Glove-1.2M uses the test split from [6].Source: §6.1 · p. 9

6.2 In-Memory Performance of B+ANN

• B+ANN has the fastest in-memory build time on Arm64 and s390x and the third-fastest on x86; SPTAG takes more than three times as long as B+ANN.The build includes the tree and skip-edge connections; the comparison uses 10 threads, and B+ANN’s advantage over other algorithms grows when thread count exceeds one.Source: §6.2 · p. 10
• B+ANN achieves 10× speedup at 10-Recall and 50× at 100-Recall over HNSW on Arm64, and 1.1×–2× speedup on x86 at the same recall values.The algorithms show the same high recall; B+ANN is comparable to DiskANN and SPTAG, which require CPU-specific accelerations such as AVX512.Source: Figure 4 · p. 9, §6.2 · p. 10

6.3 On-Disk Performance and Memory Usage

• B+ANN builds the SIFT-1B disk index in 2 hours using at most 150GB of memory, 24× faster than DiskANN and with 350GB less memory usage.The authors attribute the build time to O(n log n) tree-building complexity.Source: §6.3 · p. 10, Figure 5 · p. 10
• On SIFT-1B, B+ANN reaches 99.8% Recall-10 in less than 9ms and 80.0% recall in less than 1ms.The search results are shown in Figure 5a.Source: §6.3 · p. 10, Figure 5 · p. 10
• With memory capped, B+ANN loads disk-resident nodes through LRU and asynchronously dumps least-recently-used nodes when memory exceeds the threshold.As more nodes are fetched from memory during continued searching, latency decreases and the system reaches a steady operating point.Source: §6.3 · pp. 10–11

6.4 Average Hops Comparison

• Skip-edge construction accounts for 84.3% of B+ANN’s total indexing time, while building the tree has O(n log(n)) complexity.The reported skip-edge construction complexity is O(n_leaf·n·d_edge).Source: §6.4 · p. 11
• Ordering vectors within leaf nodes by distance to their centroid is proposed as a way to reduce skip-edge construction work, but is left for future work.The proposed ordering could reduce computation when connecting vectors to nearby vectors in neighboring nodes.Source: §6.4 · p. 11
• B+ANN uses 15× fewer hops than HNSW to reach an average 95% Recall value.The comparison varies B+ANN’s skip-edge degree and HNSW’s corresponding degree, then increases search width until each reaches the target recall.Source: §6.4 · p. 11, Figure 6 · p. 11

6.5 Exploiting Temporal Correlation by B+ANN

• With high temporal correlation, Disk I/O counts rise more slowly than for randomly ordered queries because later queries can use nodes already loaded into memory.The authors state that temporal correlation can delay creation of a new view and reduce average response time.Source: §6.5 · p. 11, Figure 7 · p. 11

6.6 Balanced Growth and Insertion

• When a leaf reaches capacity, insertion splits its vectors into two clusters and adds their centroids to inner nodes, locally adjusting branches.The PCA visualization shows a cluster subdividing while a nearby cluster remains unsplit when it has not reached capacity.Source: §6.6 · pp. 11–12, Figure 8 · p. 11
• For GLOVE-200, larger batch sizes generally improve query throughput until saturation is reached.Figure 8 plots QPS against batch size.Source: Figure 9 · p. 12

6.7 Impact of Batch Size on Performance

• Figure 9 plots QPS against batch size, with colored lines representing constant Recall-10 configurations and other parameters held fixed.The workload gradually increases as batch size varies.Source: §6.7 · p. 12
• Up to ×100 increase in QPS is observed as batch size increases.The plotted QPS curves rise rapidly at first and then reach steady levels.Source: §6.7 · p. 12
• Batched tree traversal replaces vector–matrix operations with matrix–matrix operations, making scalability depend on CBLAS SGEMM efficiency.Skip-edge traversal instead assigns each query vector to an individual thread, limiting scalability to the available threads.Source: §6.7 · p. 12

6.8 Evaluating Dissimilarity Search

• Dissimilarity queries identify semantically different entities.The passage gives outlier extraction as an example use case.Source: §6.8 · p. 12
• The evaluation labels each vector with its top-k farthest vectors and measures Recall-10 using B+ANN’s dissimilarity flag.Dissimilarity-RNG connects vectors that are farther apart than any other vectors.Source: §6.8 · p. 12
• B+ANN reaches 100% Recall within less than 0.6ms, while dissimilarity-RNG reaches up to 40%.Figure 11 compares dissimilarity performance, with higher values indicating better performance.Source: §6.8 · p. 12, Figure 11 · p. 12
• Dissimilarity-RNG oscillates between the same graph nodes and converges to a local solution.The authors introduce this baseline because dissimilarity-based vector search has been sparsely studied and current HNSW-type graph algorithms cannot support it.Source: §6.8 · p. 12

7 CONCLUSION

• B+ANN improves functionality, result accuracy, and performance over HNSW.The conclusion characterizes the evaluation as extensive and conducted on a variety of large vector datasets.Source: §7 · p. 12
• B+ANN’s in-memory and disk access patterns improve spatial and temporal locality and computation-acceleration opportunities.Source: §7 · p. 12
• The B+ANN tree approach enables dissimilarity queries, which HNSW-based indices do not support.Source: §7 · p. 12
• Future work will explore semantic views’ impact on index architecture and memory reduction using low-precision floating-point representations.Source: §7 · p. 12