Accelerating Large-scale Graph-based Nearest Neighbor Search On A Computational Storage Platform

Abstract

K-nearest neighbor search is one of the fundamental tasks in various applications and the hierarchical navigable small world (HNSW) has recently drawn attention in large-scale cloud services, as it easily scales up the database while offering fast search. On the other hand, a computational storage device (CSD) that combines programmable logic and storage modules on a single board becomes popular to address the data bandwidth bottleneck of modern computing systems. In this paper, we propose a computational storage platform that can accelerate a large-scale graph-based nearest neighbor search algorithm based on SmartSSD CSD. To this end, we modify the algorithm more amenable on the hardware and implement two types of accelerators using HLS- and RTL-based methodology with various optimization methods. In addition, we scale up the proposed platform to have 4 SmartSSDs and apply graph parallelism to boost the system performance further. As a result, the proposed computational storage platfo

Stats

• citations31
• S2 citations—
• github stars0
• HF likes0
• heat score11.29
• arxiv keykim2022accelerating

Related papers

• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search (2021)0.00
• Efficient And Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016)22.99
• Breaking The Storage-compute Bottleneck In Billion-scale ANNS: A Gpu-driven Asynchronous I/O Framework (2025)0.00
• High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, And Unindexed Query Compatibility (2019)17.30
• Fusionanns: An Efficient CPU/GPU Cooperative Processing Architecture For Billion-scale Approximate Nearest Neighbor Search (2024)0.00
• CAGRA: Highly Parallel Graph Construction And Approximate Nearest Neighbor Search For Gpus (2023)12.17
• A Memory-efficient Distributed Algorithm For Approximate Nearest Neighbour Search With Arbitrary Distances (2024)0.00