Storing and processing of embedding vectors by specialized Vector databases (VDBs) has become the linchpin in building modern AI pipelines. Most current VDBs employ variants of a graph-based ap- proximate nearest-neighbor (ANN) index algorithm, HNSW, to an- swer semantic queries over stored vectors. Inspite of its wide-spread use, the HNSW algorithm suffers from several issues: in-memory design and implementation, random memory accesses leading to degradation in cache behavior, limited acceleration scope due to fine-grained pairwise computations, and support of only semantic similarity queries. In this paper, we present a novel disk-based ANN index, B+ANN, to address these issues: it first partitions input data into blocks containing semantically similar items, then builds an B+ tree variant to store blocks both in-memory and on disks, and finally, enables hybrid edge- and block-based in-memory traversals. As demonstrated by our experimantal evaluation, the proposed B+ANN disk-based index improves both quality (Recall value), and execution performance (Queries per second/QPS) over HNSW, by improving spatial and temporal locality for semantic operations, reducing cache misses (19.23% relative gain), and decreasing the memory consumption and disk-based build time by 24x over the DiskANN algorithm. Finally, it enables dissimilarity queries, which are not supported by similarity-oriented ANN indices.

翻译：通过专用向量数据库（VDBs）存储和处理嵌入向量已成为构建现代人工智能流程的关键环节。当前大多数VDB采用基于图的近似最近邻（ANN）索引算法HNSW的变体来对存储向量进行语义查询。尽管HNSW算法应用广泛，但其存在若干问题：内存设计与实现、随机内存访问导致缓存行为退化、细粒度成对计算带来的加速范围有限，以及仅支持语义相似性查询。本文提出一种新颖的磁盘ANN索引B+ANN以解决这些问题：首先将输入数据划分为包含语义相似项的块，然后构建B+树变体以在内存和磁盘中存储块，最终实现基于边和块的混合内存遍历。实验评估表明，所提出的B+ANN磁盘索引通过改善语义操作的空间与时间局部性、减少缓存未命中（相对增益19.23%），并在内存消耗和磁盘构建时间上较DiskANN算法降低24倍，从而在质量（召回率）和执行性能（每秒查询数/QPS）上均优于HNSW。此外，该索引还支持面向相似性的ANN索引所不具备的相异性查询功能。