article · 2021
Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere
Qiang Huang, Yifan Lei, Anthony K. H. Tung
Cited by 16Open access
Abstract
Point-to-Hyperplane Nearest Neighbor Search (P2HNNS) is a fundamental yet challenging problem, and it has plenty of applications in various fields. Existing hyperplane hashing schemes enjoy sub-linear query time and achieve excellent performance on applications such as large-scale active learning with Support Vector Machines (SVMs). However, they only conditionally deal with this problem with a strong assumption that all of the data objects are normalized, located at the unit hypersphere. Those hyperplane hashing schemes may be arbitrarily bad without this assumption. In this paper, we introduce a new asymmetric transformation and develop the first two provable hyperplane hashing schemes, Nearest Hyperplane hashing (NH) and Furthest Hyperplane hashing (FH), for high-dimensional P2HNNS beyond the unit hypersphere. With this asymmetric transformation, we demonstrate that the hash functions of NH and FH are locality-sensitive to the hyperplane queries, and both of them enjoy quality guarantee on query results. Moreover, we propose a data-dependent multi-partition strategy to boost the search performance of FH. NH can perform the hyperplane queries in sub-linear time, while FH enjoys a better practical performance. We evaluate NH and FH over five real-life datasets and show that we are around $3 \sim 100 \times$ faster than the best competitor in four out of five datasets, especially for the recall in $[20%, 80%]$. Code is available at \urlhttps://github.com/HuangQiang/P2HNNS.
Cite this paper
Huang, Q., Lei, Y., & Tung, A. K. H. (2021). Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere. https://doi.org/10.1145/3448016.3457240
Huang, Qiang, et al. “Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere.” 2021, pp. 777–89, https://doi.org/10.1145/3448016.3457240.
Huang, Qiang, Yifan Lei, and Anthony K. H. Tung. 2021. “Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere.” https://doi.org/10.1145/3448016.3457240.
Huang, Q., Lei, Y. and Tung, A.K.H. (2021) ‘Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere’. Available at: https://doi.org/10.1145/3448016.3457240.
@article{huang2021point,
title = {{Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere}},
author = {Huang, Qiang and Lei, Yifan and Tung, Anthony K. H.},
pages = {777--789},
year = {2021},
doi = {10.1145/3448016.3457240}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.