Sublinear Time Nearest Neighbor Search Over Generalized Weighted Manhattan Distance

Abstract

Nearest Neighbor Search (NNS) over generalized weighted distances is fundamental to a wide range of applications. The problem of NNS over the generalized weighted square Euclidean distance has been studied in previous work. However, numerous studies have shown that the Manhattan distance could be more effective than the Euclidean distance for high-dimensional NNS, which indicates that the generalized weighted Manhattan distance is possibly more practical than the generalized weighted square Euclidean distance in high dimensions. To the best of our knowledge, no prior work solves the problem of NNS over the generalized weighted Manhattan distance in sublinear time. This paper achieves the goal by proposing two novel hashing schemes (\(d_w^\{l_1\},l_2\))-ALSH and (\(d_w^\{l_1\},\theta\))-ALSH.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyhu2021sublinear

Related papers

• Efficient Approximate Nearest Neighbor Search For Multiple Weighted \(l_{p\leq2}\) Distance Functions (2020)0.00
• Lightweight-yet-efficient: Revitalizing Ball-tree For Point-to-hyperplane Nearest Neighbor Search (2023)10.01
• A Revisit Of Hashing Algorithms For Approximate Nearest Neighbor Search (2016)11.19
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• Sub-linear Privacy-preserving Near-neighbor Search (2016)0.00
• Learning Space Partitions For Nearest Neighbor Search (2019)0.00
• PM-LSH: A Fast And Accurate In-memory Framework For High-dimensional Approximate NN And Closest Pair Search (2021)8.09