Locality-Sensitive Indexing for Graph-Based Approximate Nearest Neighbor Search

The burgeoning size of modern text datasets has heightened the need for efficient text retrieval systems. For such applications, Approximate Nearest Neighbor (ANN) search algorithms, and in particular graph-based methods have long been established as the leading approach in terms of recall and search speed. However, the data and execution dependencies of vertices increase the construction workload and complicate maintenance processes for the constructed index. In this paper, we present Locality-Sensitive Indexing for Graph-Based Search (or LIGS), which utilizes independent locality-sensitive hashing algorithms to simulate a proximity graph, on which a standard graph search can be performed. We show that LIGS offers substantially faster maintenance (insertion/deletion) speeds and better conservation of graph quality compared to state-of-the-art graph-based ANN methods, demonstrating LIGS as a promising alternative for maintenance-heavy scenarios.