Lightweight-yet-efficient: Revitalizing Ball-tree For Point-to-hyperplane Nearest Neighbor Search

Abstract

Finding the nearest neighbor to a hyperplane (or Point-to-Hyperplane Nearest Neighbor Search, simply P2HNNS) is a new and challenging problem with applications in many research domains. While existing state-of-the-art hashing schemes (e.g., NH and FH) are able to achieve sublinear time complexity without the assumption of the data being in a unit hypersphere, they require an asymmetric transformation, which increases the data dimension from \(d\) to \(Ω(d^2)\). This leads to considerable overhead for indexing and incurs significant distortion errors. In this paper, we investigate a tree-based approach for solving P2HNNS using the classical Ball-Tree index. Compared to hashing-based methods, tree-based methods usually require roughly linear costs for construction, and they provide different kinds of approximations with excellent flexibility. A simple branch-and-bound algorithm with a novel lower bound is first developed on Ball-Tree for performing P2HNNS. Then, a new tree structure na

Stats

• citations9
• S2 citations—
• github stars17
• HF likes0
• heat score10.01
• arxiv keyhuang2023lightweight

Related papers

• PM-LSH: A Fast And Accurate In-memory Framework For High-dimensional Approximate NN And Closest Pair Search (2021)8.09
• Efficient Autotuning Of Hyperparameters In Approximate Nearest Neighbor Search (2018)6.77
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• Random Binary Trees For Approximate Nearest Neighbour Search In Binary Space (2017)2.26
• PECANN: Parallel Efficient Clustering With Graph-based Approximate Nearest Neighbor Search (2023)0.00
• Learning Space Partitions For Nearest Neighbor Search (2019)0.00
• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• Hd-index: Pushing The Scalability-accuracy Boundary For Approximate Knn Search In High-dimensional Spaces (2018)14.02