FPGA BASED HARDWARE DESIGN OF SIMILARITY SEARCH ALGORITHMS FOR TIME SERIES PROCESSING APPLICATIONS

Abstract

Time series is a huge collection of data indexed sequentially with respect to time. It is being produced at an extremely high rate from almost every domain including stock market, music industry, biomedical industry, etc. Data mining from temporal database requires similarity measures which can distinguish between two or more time series. Many distance functions, such as Dynamic Time Warping, Edit distance on Real Sequences, Move Split Merge, etc., which work efficiently in software for retrieval of similarity in temporal sequences exist. Since the time series is a massive dataset, features need to be extracted before its analysis. In this work, synthesis of five similarity measures has been done using the device xc3s400- 4-pq208 in Xilinx with Verilog Hardware Description Language (HDL) and a comparison has been made to show the outperformance of one over the other based on the critical parameters of hardware utilization and delay. The purpose behind this project is to make these similarity measures available as portable devices for time series analysis in various domains. Simulations were performed in ModelSim. To compare the efficacy of these similarity measures in distinguishing the time series, an application of detection of plagiarism in music has been implemented in MATLAB, where all the five algorithms were used to compute distance between plagiarized, unplagiarized, and same pair of songs. Algorithm which could clearly distinguish these three sets of data, as well as performed fairly well in hardware performance, was given the highest score to be used as a separate entity in real time applications. Also, a comparison was made between the execution time in hardware and software to ensure the speed up of FPGA based implemented algorithms over software. The results showed that while hardware implemented DTW can attain the highest frequency of 18.9 MHz, it is only 9.6 KHz for MATLAB implemented DTW for four element length sequence. Obtained results suggest that DTW was best for plagiarism detection and LCSS stood second. However, LCSS performed best in hardware utilization and delay. Thus, it is a bestfit algorithm for commercial use.