Sublinear Time Nearest Neighbor Search over Generalized Weighted Space

Yifan Lei, Qiang Huang, Mohan Kankanhalli, Anthony Tung
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3773-3781, 2019.

Abstract

Nearest Neighbor Search (NNS) over generalized weighted space is a fundamental problem which has many applications in various fields. However, to the best of our knowledge, there is no sublinear time solution to this problem. Based on the idea of Asymmetric Locality-Sensitive Hashing (ALSH), we introduce a novel spherical asymmetric transformation and propose the first two novel weight-oblivious hashing schemes SL-ALSH and S2-ALSH accordingly. We further show that both schemes enjoy a quality guarantee and can answer the NNS queries in sublinear time. Evaluations over three real datasets demonstrate the superior performance of the two proposed schemes.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-lei19a, title = {Sublinear Time Nearest Neighbor Search over Generalized Weighted Space}, author = {Lei, Yifan and Huang, Qiang and Kankanhalli, Mohan and Tung, Anthony}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {3773--3781}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/lei19a/lei19a.pdf}, url = {https://proceedings.mlr.press/v97/lei19a.html}, abstract = {Nearest Neighbor Search (NNS) over generalized weighted space is a fundamental problem which has many applications in various fields. However, to the best of our knowledge, there is no sublinear time solution to this problem. Based on the idea of Asymmetric Locality-Sensitive Hashing (ALSH), we introduce a novel spherical asymmetric transformation and propose the first two novel weight-oblivious hashing schemes SL-ALSH and S2-ALSH accordingly. We further show that both schemes enjoy a quality guarantee and can answer the NNS queries in sublinear time. Evaluations over three real datasets demonstrate the superior performance of the two proposed schemes.} }
Endnote
%0 Conference Paper %T Sublinear Time Nearest Neighbor Search over Generalized Weighted Space %A Yifan Lei %A Qiang Huang %A Mohan Kankanhalli %A Anthony Tung %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-lei19a %I PMLR %P 3773--3781 %U https://proceedings.mlr.press/v97/lei19a.html %V 97 %X Nearest Neighbor Search (NNS) over generalized weighted space is a fundamental problem which has many applications in various fields. However, to the best of our knowledge, there is no sublinear time solution to this problem. Based on the idea of Asymmetric Locality-Sensitive Hashing (ALSH), we introduce a novel spherical asymmetric transformation and propose the first two novel weight-oblivious hashing schemes SL-ALSH and S2-ALSH accordingly. We further show that both schemes enjoy a quality guarantee and can answer the NNS queries in sublinear time. Evaluations over three real datasets demonstrate the superior performance of the two proposed schemes.
APA
Lei, Y., Huang, Q., Kankanhalli, M. & Tung, A.. (2019). Sublinear Time Nearest Neighbor Search over Generalized Weighted Space. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:3773-3781 Available from https://proceedings.mlr.press/v97/lei19a.html.

Related Material