Accession Number:

ADA555156

Title:

A Randomized Approximate Nearest Neighbors Algorithm

Descriptive Note:

Research rept.

Corporate Author:

YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Report Date:

2010-09-14

Pagination or Media Count:

114.0

Abstract:

In this paper, we describe an algorithm for finding approximate nearest neighbors ANN in d-dimensional Euclidean space for each of N user-specified points xj. For each point xj , the scheme produces a list of k suspects , that have high probability of being the k closest points nearest neighbors in the Euclidean metric. Those of the suspects that are not among the true nearest neighbors, are close to being so.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE