Timezone: »
Poster
Sublinear Time Nearest Neighbor Search over Generalized Weighted Space
Yifan Lei · Qiang Huang · Mohan Kankanhalli · Anthony Tung
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)
-
2019 Oral: Sublinear Time Nearest Neighbor Search over Generalized Weighted Space »
Tue. Jun 11th 11:20 -- 11:25 PM Room Grand Ballroom
More from the Same Authors
-
2023 Poster: Deep Regression Unlearning »
Ayush Tarun · Vikram Chundawat · Murari Mandal · Mohan Kankanhalli -
2022 Poster: Adversarial Attack and Defense for Non-Parametric Two-Sample Tests »
Xilie Xu · Jingfeng Zhang · Feng Liu · Masashi Sugiyama · Mohan Kankanhalli -
2022 Spotlight: Adversarial Attack and Defense for Non-Parametric Two-Sample Tests »
Xilie Xu · Jingfeng Zhang · Feng Liu · Masashi Sugiyama · Mohan Kankanhalli -
2020 Poster: Inferring DQN structure for high-dimensional continuous control »
Andrey Sakryukin · Chedy Raissi · Mohan Kankanhalli -
2020 Poster: Attacks Which Do Not Kill Training Make Adversarial Learning Stronger »
Jingfeng Zhang · Xilie Xu · Bo Han · Gang Niu · Lizhen Cui · Masashi Sugiyama · Mohan Kankanhalli