Scalable k-nearest neighbor algorithms based on learned functions

Chuanjun Xing; Jie Xu; Feng Sun; Jingwen Cai; Yong Zhang; Mingchao Wang

doi:10.1117/12.2686316

28 July 2023 Scalable k-nearest neighbor algorithms based on learned functions

Chuanjun Xing, Jie Xu, Feng Sun, Jingwen Cai, Yong Zhang, Mingchao Wang

Proceedings Volume 12756, 3rd International Conference on Applied Mathematics, Modelling, and Intelligent Computing (CAMMIC 2023); 127564Y (2023) https://doi.org/10.1117/12.2686316
Event: 2023 3rd International Conference on Applied Mathematics, Modelling and Intelligent Computing (CAMMIC 2023), 2023, Tangshan, China

Abstract

Approximate k-Nearest Neighbor (kNN) is a fundamental problem in data science. A lot of traditional approaches have been devel- oped to solve this problem, yet none of them can achieve high accuracy, small memory usage and fast query speed. These methods can be in- efficient since they don’t improve with experience(learning from errors or heuristics employed). A recent trend in algorithm design consists of augmenting classic data structures with machine learning models. Mo- tivated by this, we present a learned index for kNN query in massive amounts of data, named LBF. It robustly combines a traditional index with a learned model. What’s more, a multiple feature extraction mod- ule is embedded into our model to make full use of the raw input. These make our method satisfies all the requirements of a good similarity in- dexing scheme. Theoretical proofs and experimental results on a variety of datasets show that compared to the state-of-the-art methods, we can achieve a comparable accuracy with much less memory usage.

Citation Download Citation

Chuanjun Xing, Jie Xu, Feng Sun, Jingwen Cai, Yong Zhang, and Mingchao Wang "Scalable k-nearest neighbor algorithms based on learned functions", Proc. SPIE 12756, 3rd International Conference on Applied Mathematics, Modelling, and Intelligent Computing (CAMMIC 2023), 127564Y (28 July 2023); https://doi.org/10.1117/12.2686316

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available