An O( n) query time algorithm for reducing -NN to (c,r)-NN

DOI10.1016/J.TCS.2019.10.004MaRDI QIDQ2283022zbMATH OpenOpenAlexFDO

Authors Hengzhao Ma, Jianzhong Li

Publication date 27 December 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.10.004

zbMATH Keywords

approximate nearest neighborcomputational geometryreduction

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Recommendations

• An algorithm for reducing approximate nearest neighbor to approximate near neighbor with \(O(\log{n})\) query time
• Approximate nearest neighbor queries revisited
• Approximate nearest neighbors search without false negatives for \(l_2\) for \(c>\sqrt{\log\log n}\)
• scientific article; zbMATH DE number 1003290
• On approximate nearest neighbors under \(l_\infty\) norm

Cites work

• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• An algorithm for reducing approximate nearest neighbor to approximate near neighbor with \(O(\log{n})\) query time
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Approximate closest-point queries in high dimensions
• Approximate nearest neighbor: towards removing the curse of dimensionality
• Beyond locality-sensitive hashing
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Entropy based nearest neighbor search in high dimensions
• scientific article; zbMATH DE number 437552 (Why is no real title available?)
• scientific article; zbMATH DE number 1160328 (Why is no real title available?)
• scientific article; zbMATH DE number 1559575 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 3215519 (Why is no real title available?)
• scientific article; zbMATH DE number 6469222 (Why is no real title available?)
• Locality-sensitive hashing scheme based on p-stable distributions
• Optimal data-dependent hashing for approximate near neighbors
• Plongements lipschitziens dans ${\bbfR}\sp n$
• Reductions among high dimensional proximity problems

Cited in

(1)

• An algorithm for reducing approximate nearest neighbor to approximate near neighbor with \(O(\log{n})\) query time

This page was built for publication: An \(O(\log n)\) query time algorithm for reducing \(\varepsilon \)-NN to \((c,r)\)-NN

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2283022)