NEAREST-NEIGHBOUR SEARCH IN CONSTANT TIME: AN ALTERNATIVE TO NEURAL NETWORKS FOR PATTERN MATCHING APPLICATIONS

PDF

Authors
  1. Zakarauskas, P.
  2. Ozard, J.M.
Corporate Authors
Defence Research Establishment Pacific, Victoria BC (CAN)
Abstract
In the paper we present an alternate algorithm to the use of neural networks for pattern matching in continuous space, and present performance estimates as a function of the dimensionality of the search space. Neural networks divide decision space with hyperplanes whose positions are adjusted during training, usually through gradient descent. The decision regions thus obtained are not necessarily optimal for noisy data. Another drawback of neural networks is the rapid increase in training time with the size of the problem, leading to the quasi impossibility of training them for very large problems. In order to obtain robust pattern matching for problems where the number of patterns becomes very large, we propose the use of a fast nearest-neighbour algorithm. This algorithm finds the training pattern closest to a test pattern, in a time which is asymptotically constant with the total number of patterns. The algorithm first partitions the search space, and finds which partition each of the training pattern falls into. When a test pattern is supplied, one compares it to all patterns which the partitions which are within a given distance R to the test pattern. If the distance d between the closest pattern found during the first pass and the test pattern is less than R, then the search stops. If not, then a second pass is done using d as a search parameter to select partitions. TRUNCATED
Report Number
DREA-TC-93-305-VOL-1-P-209 — @Conference Paper; CONTAINED IN 93-02664
Date of publication
01 Feb 1993
Number of Pages
21 (p209-229)
DSTKIM No
93-02654
CANDIS No
131315
Format(s):
Microfiche filmed at DSIS;Originator's fiche received by DSIS;Document Image stored on Optical Disk

Permanent link

Document 1 of 1

Date modified: