Hybrid SORN Implementation of k-Nearest Neighbor Algorithm on FPGA

In this paper a new implementation of the k-Nearest Neighbor algorithm (kNN) is presented. The approach is based on the Sets-of-Real-Numbers (SORN) representation. SORNs are an interval-based binary number representation providing ultra fast and low complex arithmetic operations. The proposed approach combines the advantages of SORN (complexity) and fixed point representations (precision) to provide high dimensional vector arithmetic operations with high precision. This Hybrid SORN approach is used to implement a low-complexity kNN architecture, introduced as Hybrid SORN kNN. The proposed design is implemented on an FPGA board with Zynq 7000 XC7Z100 SoC and verified with the MNIST dataset. To achieve the data transfer to the FPGA for the complete MNIST dataset, an AXI Direct Memory Access (DMA) IP-Core to access an SD card is used. The proposed architecture provides promising results since the validation error is significantly lower compared to floating point implementations. The hardware utilization shows an LUT reduction of 39.2% compared to a fixed point implementation.