A Fast Nearest Neighbor Algorithm
                  Based on a Principal Axis Tree

                       James McNames
             Electrical and Computer Engineering
                  Portland State University 
                     mcnames@ee.pdx.edu

Algorithms based on the nearest neighbors of a data set are used
in a wide range of applications.  In many cases alternative methods 
are chosen because the computational cost of finding the nearest 
neighbors is prohibitive.  This has inspired the development of many 
fast nearest neighbor algorithms that, in many cases, drastically 
reduce the required computation.

One of the most important applications for these methods is vector 
quantization, a powerful method of signal compression.  This talk 
briefly reviews how vector quantization works, discusses how fast 
nearest neighbor algorithms play a crucial role, and introduces a 
new nearest neighbor algorithm that combines principal component 
analysis, search trees, partial distortion search, and a new 
bounding criterion. 

A thorough comparative study was conducted that compared the 
performance of the new algorithm to sixteen other fast nearest 
neighbor algorithms on three types of common benchmarks including 
synthetic data with known distributions, time series, and vector 
quantization problems.  This talk will summarize the key results 
from this study which show the new algorithm performs as well as or 
better than current methods.  



James McNames graduated with his Ph.D. degree in Electrical Engineering 
at Stanford University this last June.  His dissertation discusses a 
number of improvements to local modeling for time series prediction 
and other applications. He received his M.S. degree in Electrical 
Engineering from Stanford University in 1995. He received his B.S. 
degree in Electrical Engineering from California Polytechnic State 
University, San Luis Obispo, in 1992. His research is primarily in the 
areas of biomedical signal processing, control systems, local modeling, 
integrated circuit test methods, and time series prediction.  He is 
currently working as a visiting assistant professor at Portland State 
University.