A Study of Selection for Representative Skyline Points on GPUs
| Autor: | Yuan-Yu Lin, 林遠聿 |
|---|---|
| Rok vydání: | 2019 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 107 Skyline query is mainly used for database screening. It can screen out the representative data points to achieve the effect of information filtering and providing decision making. However, when the dimensionality of dataset is increased, the number of data points obtained by skyline computation will be increased exponentially, thus losing the effectiveness of data screening. Therefore, it generates the applications such as representative skyline points. The expectation is to select representative skyline points with specific features via condition restraints. By setting the dominance number as the condition restraint, we can eliminate the overly extreme data points and keep the data points with more balanced characteristics. Among all skyline query related applications, the main computation is about the comparison of dominance relations, and the data sets to be processes are usually enormous and complicated. Therefore, the two key points are how to enhance computation efficiency and how to reduce unnecessary computation. Along with the current enhancement of computation capability of processor and the improvement of GPU (Graphics Processing Unit) hardware, we can enhance the computation efficiency based on GPU’s capability to parallelize a large amount of computation, and reduce unnecessary computation in coordination with proper computation mechanism in order to improve aforementioned problems. This study will be focused on enhancing computation efficiency of dominance relation, and finding out the number of data points dominated by each point as the strength of each point in order to find out the representative skyline points. In the end, a data structure suitable for GPU and effective traversal algorithm will be proposed to accelerate the computation of skyline representative points dominance relation. The experimental results indicate that the method we proposed can indeed greatly accelerate the computation of number of dominance number. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|