A High Performance k-NN Classifier Using a Binary Correlation Matrix Memory

Ping Zhou, Jim Austin, John KennedyNeurIPS 1998

Overview

This paper introduces a hybrid classifier that combines the rapid processing speed of Binary Correlation Matrix Memories (CMMs) with the established accuracy of $k$-Nearest Neighbor ($k$-NN) algorithms. By utilizing custom FPGA-based hardware—the PRESENCE architecture—and a novel "Robust Uniform Encoding" method, the authors achieve massive computational speedups. The system demonstrates up to a 15x speedup in software and significantly more in hardware, all while maintaining classification accuracy within 1% of a standard $k$-NN approach.

The Computational Bottleneck of $k$-NN

The $k$-Nearest Neighbor ($k$-NN) rule is a cornerstone of pattern classification due to its simplicity and effectiveness across diverse domains. However, it suffers from a major computational Achilles' heel: to classify a single test sample, the algorithm must calculate the distance between that sample and every single training sample. As datasets grow into the millions, this exhaustive search becomes prohibitively slow.

While researchers typically address this by pruning training data or building complex search trees, the authors of this paper take a radically different route. They reframe the search for neighbors as a hardware-accelerated "pattern matching" problem, using a specialized neural network to rapidly filter the data before applying the final $k$-NN rule.

Methods: A Hybrid Two-Stage Approach

To overcome the speed limitations of traditional $k$-NN, the authors propose a two-stage architecture that leverages both approximate filtering and precise distance calculation.

System architecture and visual representation of CMM pre-selection.
  1. CMM Pre-selection: A Correlation Matrix Memory (CMM) acts as a high-speed "match engine." CMMs are single-layer neural networks with binary weights that use simple logical OR operations for training and matrix multiplication for recall. The CMM quickly identifies a small subset of training patterns that are highly likely to be the nearest neighbors.
  2. Refined $k$-NN: A conventional $k$-NN algorithm is then applied only to that pre-selected subset. This step filters out "spurious errors" (recall noise) generated by the CMM while drastically reducing the total number of expensive Euclidean distance calculations required.

The "Secret Sauce": Robust Uniform Encoding (RU)

Because CMMs require binary input, multi-dimensional real numbers must be converted into binary codes. To achieve this, the authors developed Robust Uniform Encoding (RU).

Standard quantization often fails when data is non-uniformly distributed or contains many identical points (such as "background" pixels in images). The RU encoder ensures that data is distributed as uniformly as possible across the CMM's "bins." This prevents certain parts of the memory from being overloaded with data while others remain empty, optimizing the CMM's filtering capability.

Hardware: The PRESENCE Architecture

To truly push the speed limits of this hybrid approach, the team built the PRESENCE architecture—a dedicated hardware implementation using FPGAs on VME and PCI cards.

The PRESENCE hardware architecture and CMM matrix operations.

This custom hardware allows for SIMD (Single Instruction, Multiple Data) parallel processing. By moving the heavy lifting to FPGAs, the system can sum rows of binary weights in a single clock cycle, bypassing the sequential processing limitations of standard workstations.

Datasets and Key Results

The researchers evaluated their system using four large-scale real-world benchmarks from the Statlog project: Satellite Image Database, Letter Image Recognition, Shuttle Data Set, and Image Segmentation.

  • Accuracy Maintained: Across all four benchmarks, the CMM-hybrid classifier performed within 0% to 1% of the accuracy of a standard, exhaustive $k$-NN.
  • Software Speedup: Even without the custom hardware, the software implementation of the hybrid algorithm was 4 to 15 times faster than standard $k$-NN.
  • Hardware Speedup: The core matrix operations on the PRESENCE card were an astounding 216 times faster than a mid-range workstation of the time.
  • Rapid Training: Unlike Multi-Layer Perceptrons (MLP) or Radial Basis Function (RBF) networks that require long, iterative training epochs, the CMM is "one-shot." It trains almost as fast as it classifies.

Key Insights and Future Work

A brilliant insight of this paper is treating the CMM as a lossy filter. The authors accept that the CMM is imperfect and produces "recall noise." However, because it operates so quickly in Hamming space (binary overlap), the system can afford to over-select candidate patterns and let the precise $k$-NN algorithm clean up the results in the original feature space.

Limitations (Amdahl's Law): The authors note a classic Amdahl's Law bottleneck. While the CMM matrix operation is 216x faster in hardware, the overall system speedup is lower (around 12x) because the pre-processing (RU encoding) and post-processing (the final $k$-NN step) are still performed in software on the host computer.

Future Directions: To address this bottleneck, the authors suggest integrating the pre- and post-processing tasks directly into the hardware (VLSI) to eliminate communication overhead between the host and the FPGA card. Furthermore, they propose scaling the system to handle "very large weight arrays" for massive commercial applications, such as chemical structure matching or real-time postcode recognition.

Summary updated

BibTeX
@inproceedings{zhou1998high,
  author = {Ping Zhou and Jim Austin and John Kennedy},
  title = {{A High Performance k-NN Classifier Using a Binary Correlation Matrix Memory}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1998},
}
Figure