The black-box complexity of nearest-neighbor search

DOI10.1016/J.TCS.2005.09.017MaRDI QIDQ2581270zbMATH OpenOpenAlexFDO

Authors Robert Krauthgamer, James R. Lee

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 algorithmsclosest point queriesdoubling metric spacesnearest neighbor searchingsimilarity search

Mathematics Subject Classification ID

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

Recommendations

• Automata, Languages and Programming
• scientific article; zbMATH DE number 1559576
• scientific article; zbMATH DE number 1775450
• Nearest neighbor queries in metric spaces
• scientific article; zbMATH DE number 437552

Cites work

• A note on the nearest neighbor in growth-restricted metrics
• Bypassing the embedding
• Finding nearest neighbors in growth-restricted metrics
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 1775451 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 6469222 (Why is no real title available?)
• Lectures on analysis on metric spaces
• Nearest neighbor queries in metric spaces
• Plongements lipschitziens dans ${\bbfR}\sp n$

Cited in

(11)

• Fractal dimension and lower bounds for geometric problems
• Space-Time Tradeoffs for Proximity Searching in Doubling Spaces
• Computing the distance distribution of systematic nonlinear codes
• scientific article; zbMATH DE number 177533 (Why is no real title available?)
• Indexability, concentration, and VC theory
• Metric spaces with expensive distances
• scientific article; zbMATH DE number 7236474 (Why is no real title available?)
• Automata, Languages and Programming
• Making doubling metrics geodesic
• A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics
• Approximate nearest-neighbor search for line segments

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

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