An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching

DOI10.1137/080729955zbMath1207.68156OpenAlexW2014096895MaRDI QIDQ3053154

Amit Chakrabarti, Oded Regev

Publication date: 4 November 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080729955

zbMATH Keywords

nearest neighbor searchcell probe modelround elimination

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (2)

Cell-probe lower bounds for the partial match problem ⋮ ForestDSH: a universal hash design for discrete probability distributions

This page was built for publication: An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching