利用GPU加速Skip Lists查詢效能之最佳化之研究

CCUR > College of Natural Science and Engineering > College of Engineering > Department of Computer Science and Information Engineering > thesis > Item 987654321/53067

Please use this identifier to cite or link to this item: https://irlib.pccu.edu.tw/handle/987654321/53067

Title:	利用GPU加速Skip Lists查詢效能之最佳化之研究 Maximizing Query Performance for Skip Lists for GPU
Authors:	張新羽
Contributors:	資訊工程學系
Keywords:	顯示卡查詢資料結構跳錶 GPUs Tree Query SkipList
Date:	2023
Issue Date:	2024-03-01 13:56:54 (UTC+8)
Abstract:	本論文介紹了一項研究，旨在改善（improve）GPU平台上跳表（Skip Lists）的查詢性能。Skip Lists是一種以鏈表為基礎、有額外層級的資料結構，它可以提升鏈表的查詢效能。同時，有許多的專案也使用了Skip Lists進行資料索引。但是，目前Skip Lists由於隨機化偶爾無法達到效能最大化，故我們實作了一個演算法模型，使Skip Lists無須改變其資料結構即可從中得到效能提升。我們通過在Skip Lists插入時進行資料取樣索引，以確定資料可能的層級，從而在查詢時間接提升Skip Lists的效能。同時，我們還進行了實驗，實驗結果表明相對於完全隨機化的Skip Lists，該改進能使其查詢的效能得到一定的提升。 This essay presents a study aimed at improving the query performance of Skip Lists on GPU platforms. Skip Lists is a data structure that is based on linked lists and that has extra layers, it can improve the query performance of linked lists. Meanwhile, many projects also use Skip Lists for data indexing. However, at present, due to randomization, the performance of Skip Lists sometimes cannot be maximized. Therefore, we have implemented an algorithm model, so that the performance of Skip Lists can be improved without changing its data structure. We perform data sampling and indexing when Skip Lists is inserted to determine the possible levels of data, thereby indirectly improving the performance of Skip Lists at query time. Meanwhile, we also conduct experiments, and the experimental results show that compared with completely randomized Skip Lists, this improvement can improve the query performance to a certain extent.
Appears in Collections:	[Department of Computer Science and Information Engineering] thesis

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	76	View/Open

View Licence

Loading...