Skip to yearly menu bar Skip to main content


Sublinear Time Nearest Neighbor Search over Generalized Weighted Space

Yifan Lei · Qiang Huang · Mohan Kankanhalli · Anthony Tung

Pacific Ballroom #82

Keywords: [ Unsupervised Learning ] [ Large Scale Learning and Big Data ] [ Information Retrieval ]


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.

Live content is unavailable. Log in and register to view live content