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
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 provide broad, flexible functionalities or achieve high performance. However, it is inherently difficult to achieve both. We propose ANNLib to address this gap. ANNLib is a library that provides a programming framework to achieve high performance and flexible functionalities for ANNS systems, based on popular graph-based ANNS algorithms. We carefully decouple and independently optimize both the algorithm and the data structure components in an ANNS system. In addition, we integrate state-of-the-art algorithms and data structures as modules in ANNLib, as well as our new designs. Users can choose combinations of components to support sophisticated settings with high performance, such as filtered 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 to 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