We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A learned index for approximate kNN queries in high-dimensional spaces.
- Authors
Li, Lingli; Cai, Jingwen; Xu, Jie
- Abstract
Approximate k-Nearest Neighbor (kNN) search in high-dimensional spaces is a fundamental problem in computer systems and applications. However, traditional indexes for kNN search do not scale gracefully to massive high-dimensional datasets. As the dimension and data size grows, both the time complexity and space complexity would cost a considerable amount. Motivated by the recent research advancements of learned indexes, we present a learned index for approximate kNN search in high-dimensional spaces, named HKC + -index. First, a traditional tree-based index is constructed and used for query processing. Then, a deep neural network is trained as the learned index based on incoming queries and the original tree index. Extensive experiments on a variety of real-world high-dimensional datasets demonstrate that HKC + -index achieves up to 7 times in running time and 8 times smaller over the original tree index, while preserving the high accuracy performance.
- Subjects
ARTIFICIAL neural networks; K-nearest neighbor classification
- Publication
Knowledge & Information Systems, 2022, Vol 64, Issue 12, p3325
- ISSN
0219-1377
- Publication type
Article
- DOI
10.1007/s10115-022-01742-0