A Randomized Approximate Nearest Neighbors Algorithm - A Short Version

Abstract

We present a randomized algorithm for the approximate nearest neighbor problem in d-dimensional Euclidean space. The algorithm has been tested on a number of artificially generated point distributions. Results of some of those tests are presented. The paper is organized as follows. In the first section, we summarize the mathematical and numerical facts to be used in subsequent sections. In the second section, we describe the Randomized Approximate Nearest Neighbors algorithm (RANN) and analyze its cost and performance. In the third section, we illustrate the performance of the algorithm with several numerical examples.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 13, 2011
Accession Number
ADA639824

Entities

People

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

Organizations

  • Yale University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computer Science
  • Computers
  • Costs
  • Data Sets
  • Demographic Cohorts
  • Discrete Fourier Transforms
  • Gaussian Distributions
  • Iterations
  • Laptop Computers
  • Numbers
  • Observation
  • Probability
  • Random Variables
  • Real Numbers
  • Statistics
  • Trees (Data Structures)

Fields of Study

  • Mathematics

Readers

  • Business Analytics
  • Computer Vision.
  • Mathematical Modeling and Probability Theory.

Technology Areas

  • Space