Sublinear Time Nearest Neighbor Search over Generalized Weighted Space
Yifan Lei · Qiang Huang · Mohan Kankanhalli · Anthony Tung

Tue Jun 11th 04:20 -- 04:25 PM @ Grand Ballroom

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.

Author Information

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)