Hope: Differentiated Backbone-Expansion ANNS Updates via In-Storage Computing

Abstract

Graph-based Approximate Nearest Neighbor Search (ANNS) has become fundamental to modern data-intensive applications, yet supporting efficient vector updates while maintaining index quality remains a critical challenge. Existing approaches face a tough dilemma: extensive reconstruction ensures connectivity but incurs unpredictable overhead, while restricting update scope improves efficiency but degrades search accuracy. In this paper, we reveal that graph-based ANNS indexes inherently comprise backbone nodes that dictate global navigation capability and expansion nodes that provide local refinement. This insight motivates Hope, a Host-CSD (Computational Storage Device) cooptimized update framework that optimizes both index quality and update efficiency with a differentiated update design. For efficient vector categorization, we propose an in-storage sketcher that leverages per-dimension correlation with the bitmap-based flip mechanism to dynamically identify backbone and expansion vectors with minimal overhead. For asymmetric update handling, Hope employs the host-CPU for computation-intensive backbone updates with multi-hop neighbor gathering to preserve connectivity, while delegating I/O-intensive expansion updates to in-storage computing for immediate local manipulations. Our evaluation demonstrates that Hope achieves superior update efficiency and index quality compared to state-of-the-art baselines, providing stable performance for both vector updates and ANNS queries in dynamic environments.