The black-box complexity of nearest-neighbor search

DOI10.1016/j.tcs.2005.09.017zbMath1081.68013OpenAlexW2107342718MaRDI QIDQ2581270

James R. Lee, Robert Krauthgamer

Publication date: 9 January 2006

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

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

zbMATH Keywords

approximation algorithmssimilarity searchdoubling metric spacesnearest neighbor searchingclosest point queries

Mathematics Subject Classification ID

Searching and sorting (68P10) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (8)

Making doubling metrics geodesic ⋮ Indexability, concentration, and VC theory ⋮ A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics ⋮ Space-Time Tradeoffs for Proximity Searching in Doubling Spaces ⋮ COMPUTING THE DISTANCE DISTRIBUTION OF SYSTEMATIC NONLINEAR CODES ⋮ Fractal dimension and lower bounds for geometric problems ⋮ Unnamed Item ⋮ Metric Spaces with Expensive Distances

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nearest neighbor queries in metric spaces
• Lectures on analysis on metric spaces
• On metric Ramsey-type phenomena
• Finding nearest neighbors in growth-restricted metrics
• Bypassing the embedding
• Plongements lipschitziens dans ${\bbfR}\sp n$

This page was built for publication: The black-box complexity of nearest-neighbor search