Hardware based accelerator for database query using M-tree

Fast indexing is an indexing methods that sort the database and enable content to be accessed quickly. Fast query is part of fast indexing which able to perform the query within a narrow range to reduce the query time. In fast query, machine learning has played an important role on automate the task...

Full description

Saved in:
Bibliographic Details
Main Author: Chai, Kah Hieng
Format: Thesis
Language:English
Published: 2018
Subjects:
Online Access:http://eprints.utm.my/id/eprint/79262/1/ChaiKahHiengMFKE2018.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
id my-utm-ep.79262
record_format uketd_dc
spelling my-utm-ep.792622018-10-14T08:39:58Z Hardware based accelerator for database query using M-tree 2018 Chai, Kah Hieng TK Electrical engineering. Electronics Nuclear engineering Fast indexing is an indexing methods that sort the database and enable content to be accessed quickly. Fast query is part of fast indexing which able to perform the query within a narrow range to reduce the query time. In fast query, machine learning has played an important role on automate the tasks. In state-of-the-art, fast query algorithm are built using software where the performance of the query process is based on the performance of the general-purposed CPU. Besides, the total query time is linearly proportional to the data size where the difficulty of fast query is increasing as the data size increase which result in longer query time. Thus, a hardware accelerator for fast query is proposed in this work. M-tree is a fast indexing algorithm using tree data structure. M-tree data structure is constructed based on metric space and relied on triangle inequality which offer efficient range and k-nearest neighbor (k-NN) queries. The hardware accelerator is implemented using Xilinx’s Vivado Design Suite which targeted on FPGA platform. The hardware accelerator is coded using System Verilog HDL. The hardware accelerator is focusing on the fast query algorithm. The hardware accelerator is designed to be generic which could be implement on different FPGA board. The hardware accelerator has been evaluated by running the comparison on the performance with the existing work which is the M-tree algorithm running in software. The hardware accelerator is able to achieve significant speedup at approximatly 1000 times on the performance of query process compare to the M-tree running in software. The overall performance of the hardware accelerator for several scenario also shown the speedup compare to software based fast query. 2018 Thesis http://eprints.utm.my/id/eprint/79262/ http://eprints.utm.my/id/eprint/79262/1/ChaiKahHiengMFKE2018.pdf application/pdf en public masters Universiti Teknologi Malaysia, Faculty of Electrical Engineering Faculty of Electrical Engineering
institution Universiti Teknologi Malaysia
collection UTM Institutional Repository
language English
topic TK Electrical engineering
Electronics Nuclear engineering
spellingShingle TK Electrical engineering
Electronics Nuclear engineering
Chai, Kah Hieng
Hardware based accelerator for database query using M-tree
description Fast indexing is an indexing methods that sort the database and enable content to be accessed quickly. Fast query is part of fast indexing which able to perform the query within a narrow range to reduce the query time. In fast query, machine learning has played an important role on automate the tasks. In state-of-the-art, fast query algorithm are built using software where the performance of the query process is based on the performance of the general-purposed CPU. Besides, the total query time is linearly proportional to the data size where the difficulty of fast query is increasing as the data size increase which result in longer query time. Thus, a hardware accelerator for fast query is proposed in this work. M-tree is a fast indexing algorithm using tree data structure. M-tree data structure is constructed based on metric space and relied on triangle inequality which offer efficient range and k-nearest neighbor (k-NN) queries. The hardware accelerator is implemented using Xilinx’s Vivado Design Suite which targeted on FPGA platform. The hardware accelerator is coded using System Verilog HDL. The hardware accelerator is focusing on the fast query algorithm. The hardware accelerator is designed to be generic which could be implement on different FPGA board. The hardware accelerator has been evaluated by running the comparison on the performance with the existing work which is the M-tree algorithm running in software. The hardware accelerator is able to achieve significant speedup at approximatly 1000 times on the performance of query process compare to the M-tree running in software. The overall performance of the hardware accelerator for several scenario also shown the speedup compare to software based fast query.
format Thesis
qualification_level Master's degree
author Chai, Kah Hieng
author_facet Chai, Kah Hieng
author_sort Chai, Kah Hieng
title Hardware based accelerator for database query using M-tree
title_short Hardware based accelerator for database query using M-tree
title_full Hardware based accelerator for database query using M-tree
title_fullStr Hardware based accelerator for database query using M-tree
title_full_unstemmed Hardware based accelerator for database query using M-tree
title_sort hardware based accelerator for database query using m-tree
granting_institution Universiti Teknologi Malaysia, Faculty of Electrical Engineering
granting_department Faculty of Electrical Engineering
publishDate 2018
url http://eprints.utm.my/id/eprint/79262/1/ChaiKahHiengMFKE2018.pdf
_version_ 1747818185710632960