ANN-Cache: Accelerating Approximate Nearest Neighbor Search via Caching

Approximate nearest neighbor (ANN) search in the high-dimensional Euclidean space is a pivotal problem for various data science and AI applications. The performance of traditional in-memory ANN methods decreases dramatically when handling large-scale data due to their substantial expansion of main memory. Recently, disk-resident ANN methods have drawn considerable attention to enable large-scale ANN search. However, despite their significant improvements, they still suffer from high query latency due to heavy I/O cost. In this paper, we propose ANN-CACHE, an I/O-efficient cache-conscious ANN framework that leverages the skew in query workloads to reduce I/O cost. To the best of our knowledge, we are the first to formally study exploring caching to accelerate disk-based ANN search. ANN-CACHE consists of two components: (i) a discriminator that checks whether a query's ANN points are cached. If so, an in-memory lookup in the cache is triggered; otherwise, a lookup in the disk-resident index is conducted; and (ii) an LSH-based cache that stores historical queries and their results to support efficient ANN search. Considering a query q, if the cache contains historical queries that are similar to q and their ANNs, we can obtain q's result from these queries' results without accessing the disk-resident index. Experimental results demonstrate that our framework achieves 3×-9× speedup while maintaining consistently higher accuracy compared to the baselines, by introducing less than 50 MB of additional memory overhead on datasets of 10M size.