ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search

Author: Zheqi Shen, Jingbo Su, Zijin Wan, Yan Gu, Yihan Sun
University of California, Riverside
College of William & Mary

Abstract

Approximate Nearest Neighbor Search (ANNS) plays a pivotal role in modern deep learning pipelines. Recently, many ANNS systems have been proposed to either provide broad functionality or reach high performance. However, it is yet difficult to achieve both with minimal programming efforts. We propose ANNLib to address the gap. ANNLib is a library that provides a programming framework for achieving high performance and flexible functionality in ANNS systems, based on popular graph-based ANNS algorithms. We carefully decouple and independently optimize both the algorithm and the data structure components of an ANNS system. In addition, we integrate state-of-the-art algorithms and data structures into ANNLib as modules, along with our new designs. Users can choose combinations of components to implement sophisticated settings with high performance, such as filter search, fully dynamic updates, and historical queries on snapshots. Our experiments show that our new solution provides a simple interface for various applications and achieves comparable or even better performance than previous work, specifically for each application.

Keywords

Approximate nearest neighbor search, Data structure, Vector database, Parallel algorithms

Download

ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search