Robust ANN Searching for Dynamic Vector Streams without Rebuilding Index

Graph-based approximate nearest neighbour (ANN) algorithms have dominated vector indexing recently. However, some of them do not support incremental vector addition, while most of them do not support in-place deletion. Therefore, additional rebuilding overhead is required to keep the index updated. We propose HSG (Hybrid Stride Graph) to enable the vector index to accept dynamic vector streams. Inspired by the K-ANN graph and NSG, HSG constructs the index with short and long edges simultaneously without any preprocessing or prior dataset knowledge. Finally, HSG is evaluated against three well-known datasets and the experimental results indicate that HSG can deliver acceptable QPS with an excellent recall guarantee.