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.
Yifan Lei (National University of Singapore)
Qiang Huang (National University of Singapore)
Mohan Kankanhalli (National University of Singapore,)
Anthony Tung (NUS)
Related Events (a corresponding poster, oral, or spotlight)
2019 Oral: Sublinear Time Nearest Neighbor Search over Generalized Weighted Space »
Tue Jun 11th 04:20 -- 04:25 PM Room Grand Ballroom