Scaling Approximate Nearest Neighbor Search (ANNS) to massive datasets exposes fundamental bottlenecks in PCIe bandwidth and random I/O. Computational storage devices (CSDs) promise to mitigate these constraints by enabling near-storage computation, but existing CSD-based ANNS engines employ only coarse-grained producer-consumer pipelines and underutilize heterogeneous on-device computational resources. We present Mario, a hierarchically pipelined ANNS framework for CSDs that couples a centroid-shard data organization with fine-grained coordination between the flash translation layer (FTL) and an on-board Field-Programmable Gate Array (FPGA). Mario introduces a speculative inter-shard pipeline that overlaps centroid-graph traversal, shard prefetching, and result aggregation with FPGA processing, and a stall-free intra-shard pipeline that streams vectors through parallel distance units and a streaming top-k updater. We prototype Mario on a Daisy+ OpenSSD platform and evaluate it on 100M-scale datasets, where it achieves 3.49× higher performance than existing ANNS architectures in average QPS, while maintaining a Recall@10 above 90%.
Kaijiang Deng, Shengan Zheng, Penghao Sun et al.· Proceedings of the 19th ACM...· 0 citations
Approximate Nearest Neighbor (ANN) search is a core operation in large-scale vector databases that support recommendation, semantic search, and retrieval-augmented generation. Graph-based indexes are widely used for their superior search performance at million scale, but scaling them to billion-scale datasets exposes a fundamental trade-off between construction efficiency and search performance. CPU-based methods produce high-quality graphs enabling fast search but require multiple days to construct, while GPU-based methods accelerate construction at the cost of degraded search performance. This trade-off stems from the traditional requirement of enforcing global connectivity during graph construction. We observe that graph-based search primarily depends on local connectivity between entry points and a query's nearest neighbors, making global connectivity unnecessary for high search performance. In this paper, we introduce HEXA, a disjoint-subgraph-based indexing framework that partitions the dataset into disjoint clusters and constructs refined proximity subgraphs independently on GPUs. At query time, HEXA employs a two-level routing structure to select relevant subgraphs and query-close entry points, then applies a budget-adaptive search algorithm that allocates exploration effort based on each subgraph's likelihood of containing nearest neighbors. Experiments on billion-scale datasets demonstrate that HEXA achieves up to 14.7 times higher query throughput at the same recall levels compared with various indexing methods, and reduces construction time to approximately one hour.
Yi-Fei Xu, Yan-Yan Shen, Youmin Chen et al.· Proceedings of the VLDB Endo...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
