A Nearest Neighbor Search Engine Using Distance-Based Hashing
- Resource Type
- Conference
- Authors
- Ito, Toshitaka; Itotani, Yuri; Wakabayashi, Shin'ichi; Nagayama, Shinobu; Inagi, Masato
- Source
- 2018 International Conference on Field-Programmable Technology (FPT) FPT Field-Programmable Technology (FPT), 2018 International Conference on. :150-157 Dec, 2018
- Subject
- Communication, Networking and Broadcast Technologies
Components, Circuits, Devices and Systems
Computing and Processing
Robotics and Control Systems
Signal Processing and Analysis
Software algorithms
Nearest neighbor methods
Search engines
Parallel processing
Approximation algorithms
Hardware
Software
FPGA
nearest neighbor search
distance based hashing
- Language
This paper proposes an FPGA-based nearest neighbor search engine for high-dimensional data, in which nearest neighbor search is performed based on distance-based hashing. The proposed hardware search engine implements a nearest neighbor search algorithm based on an extension of flexible distance-based hashing (FDH, for short), which finds an exact solution with high probability. The proposed engine is a parallel processing and pipelined circuit so that search results can be obtained in a short execution time. Experimental results show the effectiveness and efficiency of the proposed engine.