跳到主要內容

臺灣博碩士論文加值系統

(44.211.239.1) 您好!臺灣時間:2023/01/31 05:35
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:謝子然
研究生(外文):Tzu-Jan Hsieh
論文名稱:平行G-skyline演算法之研究
論文名稱(外文):A Study of Parallel G-skyline Algorithm
指導教授:陳維美
指導教授(外文):Wei-Mei Chen
口試委員:陳維美林昌鴻林淵翔林敬舜
口試委員(外文):Wei-Mei ChenChang-Hong LinYuan-Hsiang LinChing-Shun Lin
口試日期:2020-07-22
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:電子工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2020
畢業學年度:108
語文別:中文
論文頁數:55
中文關鍵詞:天際線查詢群集天際線平行演算法GPGPU
外文關鍵詞:skyline querygroup skylineparallel algorithmGPGPU
相關次數:
  • 被引用被引用:0
  • 點閱點閱:233
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
教授推薦書 i
口試委員審定書 ii
中文摘要 iii
英文摘要 iv
目錄 v
圖目錄 vii
表目錄 viii
第一章 緒論 1
1.1 研究動機 1
1.2 論文架構 2
第二章 文獻探討 3
第三章 問題描述 6
3.1 G-skyline 6
3.1.1 問題範例 6
3.1.2 基本定義 7
3.2 G-skyline 相關演算法 10
3.2.1 U-Wise+ 搜索法 10
3.2.2 MSL 10
3.3 NVIDIA GPU 硬體架構 12
3.3.1 全域記憶體與共享記憶體 13
3.3.2 GPU 演算法的設計限制 15
第四章 研究方法 16
4.1 演算法改進 16
4.2 適用於 GPU 的多維資料結構 22
4.2.1 平行計算 subspace skyline layers 22
4.2.2 平行建構 Reduced Unit Group(RUG) 25
4.3 使用 warp shuffle 加速 28
4.4 降維修剪策略 31
4.4.1 sum 修剪策略 31
4.4.2 min 修剪策略 31
4.5 搜索指定資料的 G-skyline 32
第五章 實驗結果 34
5.1 實驗環境 34
5.2 實驗資料與設定 34
5.3 實驗結果分析 35
5.3.1 生成候選集時間 36
5.3.2 總執行時間 37
5.3.3 循序法與平行法於不同維度生成候選集時間 39
5.3.4 修剪策略對於候選集執行時間 40
5.3.5 NBA 真實數據 41
第六章 結論 43
參考文獻 44
[1] H. Blunck and J. Vahrenhold, "In-place algorithms for computing0 (layers of) maxima." in Scandinavian Workshop on Algorithm Theory 57, pp.1-21, 2010.
[2] S. Borzsony, D. Kossmann and K. Stocker, "The skyline operator." in Proceedings 17th International Conference on Data Engineering, pp.421-430, 2001.
[3] Z. D. Bai, H. K. Hwang and T. H. Tsai, "Berry-Esseen bounds for the number of maxima in planar regions." Electronic Journal of Probability, vol. 8, 2003.
[4] Z. D. Bai, H. K. Hwang, W. Q. Liang and T. H. Tsai, "Limit theorems for the number of maxima in random samples from planar regions." Electronic Journal of Probability. J. Probability, vol. 6, pp.1-41, 2001.
[5] N. Bell and J. Hoberock, "Thrust: A productivity-oriented library for CUDA." in GPU computing gems Jade edition, vol. 2, pp.359-371, 2011.
[6] W. M. Chen, H. K. Hwang and T. H. Tsai, "Maxima-finding algorithms for multidimensional samples: a two-phase approach." Computational Geometry, vol. 45, no.1-2, pp.33-53, 2012.
[7] C. A. C. Coello, D. A. Van Veldhuizen and G. B. Lamont, Evolutionary Algorithms for Solving Multi-Objective Problems, Springer, vol. 5, 2007.
[8] K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., vol. 16, 2001.
[9] M. Ehrgott, Multicriteria optimization, Springer Science & Business Media, 2006.
[10] A. Guttman, "R-trees: A dynamic index structure for spatial searching." in Proceedings of the 1984 ACM SIGMOD international conference on Management of data, pp.47-57, 1984.
[11] H. Im and S. Park, "Group skyline computation." Information Sciences, 188, pp.151-169, 2012.
[12] H. T. Kung, F. Luccio and F. P. Preparata, "On finding the maxima of a set of vectors." Journal of the ACM (JACM), 22.4, pp.469-476, 1975.
[13] J. Liu, L. Xiong, J. Pei, J. Luo and H. Zhang, "Finding pareto optimal groups: Group-based skyline." in Proceedings of the VLDB Endowment, vol. 8, no.13, pp.2086-2097, 2015.
[14] C. Li, N. Zhang, N. Hassan, S. Rajasekaran and G. Das. "On skyline groups." in Conference on Information and Knowledge Management, pp.2119-2123, 2012.
[15] H. Li, S. Jang and J. Yoo, "An efficient multi-layer grid method for skyline queries in distributed environments." pp.112-119, 2011.
[16] H. Lu, C. S. Jensen and Z. Zhang. "Flexible and efficient resolution of skyline query size constraints." IEEE Transactions on Knowledge and Data Engineering, 23.7, pp.991-1005, 2010.
[17] B. Li, J. Li, K. Tang and X. Yao, "Many-objective evolutionary algorithms: A survey." ACM Computing Surveys, vol. 48, no.1, pp.1-35, 2015.
[18] M. Magnani and I. Assent. "From stars to galaxies: skyline queries on aggregate data." in Proceedings of the 16th International Conference on Extending Database Technology, pp.477-488, 2013.
[19] C. Wang, C. Wang, G. Guo, X. Ye and S. Y. Philip, "Efficient computation of g-skyline groups." IEEE Transactions on Knowledge and Data Engineering, vol.30, no.4, pp.674-688, Apr. 2018.
[20] W. Yu, Z. Qin, J. Liu, L. Xiong, X. Chen and H. Zhang, "Fast algorithms for pareto optimal group-based skyline." in Conference on Information and Knowledge Management, pp.417-426, 2017.
[21] N. Zhang, C. Li, N. Hassan, S. Rajasekaran and G. Das, "On skyline groups." IEEE Transactions on Knowledge and Data Engineering, 26.4, pp.942-956, 2013.
[22] H. Zhu, P. Zhu, X. Li, Q. Liu and P. Xun "Parallelization of group-based skyline computation for multi-core processors." Concurrency and Computation Practice and Experience, vol. 29, no.18, pp.4195-4215, 2017.
[23] NVIDIA, "NVIDIA Turing GPU Architecture Whitepaper" https://www.nvidia.com/content/dam/en-zz/Solutions/design-visualization/technologies/turing-architecture/NVIDIA-Turing-Architecture-Whitepaper.pdf
[24] NVIDIA, "CUDA Toolkit Documentation" https://docs.nvidia.com/cuda/cuda-c-prog-ramming-guide/index.html
[25] NVIDIA, "CUDA C programming guide", https://docs.nvidia.com/cuda/archi-ve/9.0/cuda-c-programming-guide/index.html, 2017.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top