A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match

  • Rina Panigrahy ,
  • Kunal Talwar ,
  • Udi Wieder

FOCS '08: Proceedings of the 49th annual IEEE Symposium on Foundations of Computer Science |

Published by IEEE

This work investigates a geometric approach to proving cell probe lower bounds for data structure problems.

We consider the approximate nearest neighbor search problem on the Boolean hypercube (boold,onenorm ·) with d=Θ(log n). We show that any (randomized) data structure for the problem that answers c-approximate nearest neighbor search queries using t probes must use space at least n1+Ω(1/ct). In particular, our bound implies that any data structure that uses space ˜O(n) with polylogarithmic word size, and with constant probability gives a constant approximation to nearest neighbor search queries must be probed Ω(log n/ log log n) times. This improves on the lower bound of Ω(log log d/log log log d) probes shown by Chakrabarti and Regev for any polynomial space data structure, and the Ω(log log d) lower bound in Patrascu and Thorup for linear space data structures.

Our lower bound holds for the near neighbor problem, where the algorithm knows in advance a good approximation to the distance to the nearest neighbor.

Additionally, it is an average case lower bound for the natural distribution for the problem. Our approach also gives the same bound for (2-frac 1c)-approximation to the farthest neighbor problem.

For the case of non-adaptive algorithms we can improve the bound slightly and show a Ω(log n) lower bound on the time complexity of data structures with O(n) space and logarithmic word size.

We also show similar lower bounds for the partial match problem: any randomized t-probe data structure that solves the partial match problem on {0,1,star }d for d=Θ(log n) must use space n1+Ω(1/t). This implies an Ω(log n/log log n) lower bound for time complexity of near linear space data structures, slightly improving the Ω(log n /(log log n)2) lower bound from, for this range of d. Recently and independently Patrascu achieved similar bounds . Our results also generalize to approximate partial match, improving on the bounds of.