FLEX: A Fast and Light-weight Learned Index for kNN Search in High-Dimensional Space

The k-Nearest-Neighbors (kNN) search in the high-dimensional space is a fundamental problem in many applications. However, retrieving the nearest neighbors from a large-scale and high-dimensional dataset is computationally challenging, i.e, existing approaches either suffer from high construction cost or unsatisfactory search performance. In this paper, we propose a fast and light-weight learned index FLEX for kNN search in high-dimensional space. First, we develop a multi-module DNN framework that needs much less training examples than employing classical DNN models directly to reach the same accuracy level. Second, we propose a linear-time data layout algorithm which aims to maximize the accuracy under a search cost constraint. A bound of the expected approximation ratio of the proposed algorithm is also proved. Experimental evaluation shows that our index significantly outperforms the state-of-the-art indexes in terms of both time efficiency and space efficiency while maintaining competitive or better accuracy performance.