Willkommen, schön sind Sie da!
Logo Ex Libris

A Randomized Approximate Nearest Neighbors Algorithm

  • Kartonierter Einband
  • 136 Seiten
(0) Erste Bewertung abgeben
Bewertungen
(0)
(0)
(0)
(0)
(0)
Alle Bewertungen ansehen
The classical nearest neighbors problem is formulated as follows: given a collection of N points in the Euclidean space R^d, for e... Weiterlesen
CHF 80.00
Auslieferung erfolgt in der Regel innert 2 bis 4 Werktagen.
Bestellung & Lieferung in eine Filiale möglich

Beschreibung

The classical nearest neighbors problem is formulated as follows: given a collection of N points in the Euclidean space R^d, for each point, find its k nearest neighbors (i.e. closest points). Obviously, for each point X, one can compute the distances from X to every other point, and then find k shortest distances in the resulting array. However, the computational cost of this naive approach is at least (d N^2)/2 operations, which is prohibitively expensive in many applications. For example, "naively" solving the nearest neighbors problem with d=100, N=1,000,000 and k=30 on a modern laptop can take about as long as a day of CPU time. Fortunately, in such areas as data mining, image processing, machine learning etc., it often suffices to find "approximate" nearest neighbors instead of the "true" ones. In this work, a randomized approximate algorithm for the solution of the nearest neighbors problem is described. It has a considerably lower computational cost than the naive algorithm, and is fairly fast in practical applications. We provide a probabilistic analysis of this algorithm, and demonstrate its performance via several numerical experiments.

Autorentext

Dr. Andrei Osipov received his M.Sc. in mathematics fromthe Hebrew University of Jerusalem, Israel.He received his Ph.D. in applied mathematics from Yale University.Currently Dr. Osipov holds the position of Gibbs Assistant Professor at Yale.

Produktinformationen

Titel: A Randomized Approximate Nearest Neighbors Algorithm
Untertitel: Theory and Applications
Autor:
EAN: 9783659128387
ISBN: 978-3-659-12838-7
Format: Kartonierter Einband
Herausgeber: LAP Lambert Academic Publishing
Genre: Mathematik
Anzahl Seiten: 136
Gewicht: g
Größe: H220mm x B220mm
Jahr: 2012
Auflage: Aufl.