KNN search has been widely used in LiDAR-related applications. As LiDAR’s point clouds become more massive, it is a great challenge to implement a fast and energy-efficient KNN implementation. We propose a high-locality data structure RPS and an ultra-fast FPGA accelerator of the building and searching process. Experimental results show that our method achieves 13.7 times faster than other FPGA implementations. Moreover, energy efficiency results show that our proposed method is 27.4 times and 50.7 times higher than the state-of-the-art implementations on FPGA and GPU platforms, respectively.