A Randomized Approximate Nearest Neighbors Algorithm

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 {x(j)}. For each point x(j) , 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 14, 2010
Accession Number
ADA555156

Entities

People

  • Andrei Osipov
  • Peter W. Jones
  • Vladimir Rokhlin, Jr.

Organizations

  • Yale University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Data Sets
  • Distribution Functions
  • Gaussian Distributions
  • Integrals
  • Laptop Computers
  • Normal Distribution
  • Numbers
  • Order Statistics
  • Probability
  • Random Variables
  • Real Numbers
  • Statistics
  • Trees (Data Structures)

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Regression Analysis.
  • Statistical inference.

Technology Areas

  • Space