A strong lower bound for approximate nearest neighbor searching

DOI10.1016/j.ipl.2004.06.001zbMath1173.68468OpenAlexW1975663164MaRDI QIDQ834886

Ding Liu

Publication date: 27 August 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.06.001

zbMATH Keywords

lower boundcomputational geometryapproximate nearest neighbor searching

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Related Items

Lower bounds for predecessor searching in the cell probe model

Cites Work

• Approximate nearest neighbor queries revisited
• On data structures and asymmetric communication complexity
• Lower bounds for union-split-find related problems on random access machines
• A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube
• Lower bounds for high dimensional nearest neighbor search and related problems
• Tighter bounds for nearest neighbor search and related problems in the cell probe model
• A Randomized Algorithm for Closest-Point Queries
• Should Tables Be Sorted?
• Multidimensional Searching Problems
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Nearest neighbor pattern classification
• Optimal numberings and isoperimetric problems on graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item