Fast nearest neighbour search algorithms for self-organising map and vector quantisation

The self-organising map has been successfully applied in pattern matching and vector quantisation. However, training is often time-consuming. An essential but computationally expensive operation is the nearest neighbour search. Fast search algorithms work by excluding certain cells from consideration. Nevertheless, during training cell weights are modified continuously, thus the data structure used by the algorithm must be updated efficiently. The authors examine a number of exact, Euclidean distance based algorithms and propose a method which reduces the overall computational load by around 85% for a range of vector dimensions. In a colour quantisation application, similar performance was obtained