Improved nearest neighbor search using auxiliary information and priority functions

Omid Keivani, Kaushik Sinha
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2573-2581, 2018.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-keivani18a, title = {Improved nearest neighbor search using auxiliary information and priority functions}, author = {Keivani, Omid and Sinha, Kaushik}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {2573--2581}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/keivani18a/keivani18a.pdf}, url = {https://proceedings.mlr.press/v80/keivani18a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Improved nearest neighbor search using auxiliary information and priority functions %A Omid Keivani %A Kaushik Sinha %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-keivani18a %I PMLR %P 2573--2581 %U https://proceedings.mlr.press/v80/keivani18a.html %V 80 %X 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.
APA
Keivani, O. & Sinha, K.. (2018). Improved nearest neighbor search using auxiliary information and priority functions. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2573-2581 Available from https://proceedings.mlr.press/v80/keivani18a.html.

Related Material