A sub-linear time algorithm for approximating k-nearest-neighbor with full quality guarantee

DOI10.1016/j.tcs.2020.12.039zbMath1477.68478arXiv2008.02924OpenAlexW3115248317MaRDI QIDQ5919060

Hengzhao Ma, Jian-Zhong Li

Publication date: 25 January 2021

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

Full work available at URL: https://arxiv.org/abs/2008.02924

zbMATH Keywords

computational geometryapproximate k-nearest-neighbors

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Uses Software

• FLANN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the stabbing number of a random Delaunay triangulation
• Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations
• Maximum reachability preserved graph cut
• The hardness of resilience for nested aggregation query
• An algorithm for reducing approximate nearest neighbor to approximate near neighbor with \(O(\log{n})\) query time
• Optimal Data-Dependent Hashing for Approximate Near Neighbors
• THE EXPECTED EXTREMES IN A DELAUNAY TRIANGULATION
• Two Algorithms for the Minimum Enclosing Ball Problem
• On Distances in Uniformly Random Networks
• Multidimensional binary search trees used for associative searching
• Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
• Delaunay Triangulations in O(sort(n)) Time and More
• Simple and Efficient Distribution-Sensitive Point Location in Triangulations
• Walking in a triangulation
• Locality-sensitive hashing scheme based on p-stable distributions