On approximate nearest neighbors under \(l_\infty\) norm

DOI10.1006/jcss.2001.1781zbMath1006.68040OpenAlexW1997633753MaRDI QIDQ1604212

Piotr Indyk

Publication date: 4 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2001.1781

zbMATH Keywords

nearest neighbor search

Mathematics Subject Classification ID

Searching and sorting (68P10)

Related Items

How to find ternary LWE keys using locality sensitive hashing ⋮ Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back ⋮ Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of L1 ⋮ Cell-probe lower bounds for the partial match problem ⋮ APPROXIMATE NEAREST NEIGHBOR SEARCH UNDER TRANSLATION INVARIANT HAUSDORFF DISTANCE ⋮ Near-neighbor preserving dimension reduction via coverings for doubling subsets of \(\ell_1\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Point location in arrangements of hyperplanes
• The design of dynamic data structures
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Approximate closest-point queries in high dimensions
• Approximate nearest neighbor queries revisited
• On the distortion required for embedding finite metric spaces into normed spaces
• Lower bounds for high dimensional nearest neighbor search and related problems
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Extensions of Lipschitz mappings into a Hilbert space
• A Randomized Algorithm for Closest-Point Queries