Timezone: »
Nearest neighbor search using random projection trees has recently been shown to achieve superior performance, in terms of better accuracy while retrieving less number of data points, compared to locality sensitive hashing based methods. However, to achieve acceptable nearest neighbor search accuracy for large scale applications, where number of data points and/or number of features can be very large, it requires users to maintain, store and search through large number of such independent random projection trees, which may be undesirable for many practical applications. To address this issue, in this paper we present different search strategies to improve nearest neighbor search performance of a single random projection tree. Our approach exploits properties of single and multiple random projections, which allows us to store meaningful auxiliary information at internal nodes of a random projection tree as well as to design priority functions to guide the search process that results in improved nearest neighbor search performance. Empirical results on multiple real world datasets show that our proposed method improves the search accuracy of a single tree compared to baseline methods.
Author Information
Omid Keivani (Wichita State University)
Kaushik Sinha (Wichita State University)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Poster: Improved nearest neighbor search using auxiliary information and priority functions »
Fri. Jul 13th 04:15 -- 07:00 PM Room Hall B
More from the Same Authors
-
2021 : FlyNN: Fruit-fly Inspired Federated Nearest Neighbor Classification »
Parikshit Ram · Kaushik Sinha -
2018 Poster: K-means clustering using random matrix sparsification »
Kaushik Sinha -
2018 Oral: K-means clustering using random matrix sparsification »
Kaushik Sinha