We present two algorithms for the approximate nearest neighbor problem in high-dimensional spaces. For data sets of size n living in R d , the algorithms require space that is only polynomial in n and d, while achieving query times that are sub-linear in n and polynomial in d. We also show applications to other high-dimensional geometric problems, such as the approximate minimum spanning tree.

• NS
  National Science Foundation

  Awards: 0915984, 0132901, CCF-0915984, CAREER, 9357849
• MU
  Multidisciplinary University Research Initiative
• AR
  Army Research Office