The Implementation of a KNN Classifier on FPGA with a Parallel and Pipelined Architecture based on Predetermined Range Search

K-nearest neighbor(KNN) classification algorithm performs slowly for large scale training set and high dimensions. To overcome the disadvantage, we need to focus on the points within a predetermined range, without changing the precision. This method is named Predetermined Range Search(PRS). In this paper, we proposed a method to find the reference distance(Re Dist), a parallel and pipelined architecture based on PRS to implement KNN classification algorithm on FPGA. Besides, we use real SPECT dataset for evaluation. The result shows that clock frequency is up to 186.4MHz on Virtex 4 which is 1.4x faster than the conventional design. Meanwhile, this novel architecture has a smaller BRAMs(Block RAMs) coverage and a simpler circuit structure.K-nearest neighbor(KNN) classification algorithm performs slowly for large scale training set and high dimensions. To overcome the disadvantage, we need to focus on the points within a predetermined range, without changing the precision. This method is named Predetermined Range Search(PRS). In this paper, we proposed a method to find the reference distance(Re Dist), a parallel and pipelined architecture based on PRS to implement KNN classification algorithm on FPGA. Besides, we use real SPECT dataset for eIEEE Beijing Section