An algorithm for finding nearest neighbours in constant average time with a linear space complexity

Given a set of n points or 'prototypes' and another point or 'test sample'. The authors present an algorithm that finds a prototype that is a nearest neighbour of the test sample, by computing only a constant number of distances on the average. This is achieved through a preproce...

Full description

Saved in:
Bibliographic Details
Main Authors: Mico, L., Oncina, J., Vidal, E.
Format: Conference Proceeding
Language:English
Subjects:
Computational modeling
Coordinate measuring machines
Extraterrestrial measurements
Neural networks
Pattern recognition
Prototypes
Sections
Testing
Vectors
Virtual prototyping
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a set of n points or 'prototypes' and another point or 'test sample'. The authors present an algorithm that finds a prototype that is a nearest neighbour of the test sample, by computing only a constant number of distances on the average. This is achieved through a preprocessing procedure that computes only a number of distances and uses an amount of memory that grows lineally with n. The algorithm is an improvement of the previously introduced AESA algorithm and, as such, does not assume the data to be structured into a vector space, making only use of the metric properties of the given distance.< >
DOI:10.1109/ICPR.1992.201840