簡易檢索 / 詳目顯示

研究生: 邱瀚洋
Han-Yang CHiu
論文名稱: 天際線代表點計算之平行多维索引結構研究
A study of the parallel multi-dimensional index for representative skyline computation
指導教授: 陳維美
Wei-Mei Chen
口試委員: 林昌鴻
Chang-Hong Lin
吳晉賢
Chin-Hsien Wu
學位類別: 碩士
Master
系所名稱: 電資學院 - 電子工程系
Department of Electronic and Computer Engineering
論文出版年: 2020
畢業學年度: 109
語文別: 中文
論文頁數: 48
中文關鍵詞: 樹狀結構平行演算法天際線
外文關鍵詞: Skyline, Bulk-loading, R-tree, Parallel algorithm
相關次數: 點閱:405下載:0
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報


中文摘要iii 英文摘要iv 目錄 v 圖目錄vii 表目錄viii 1 緒論1 1.1 研究背景 1 1.2 研究動機 2 1.3 論文架構 3 2 文獻探討 4 2.1 資料包裝方法之討論 4 2.2 Skyline 之相關研究 5 2.3 演算法平行化 7 3 問題討論 8 3.1 基本定義 8 3.2 Sort Tile Recursive(STR) 演算法 9 3.3 GPGPU 11 3.3.1 Shared memory 和Local memory 12 3.3.2 Warp 12 4 研究方法 14 4.1 演算法概述 14 4.2 STR-CPU建樹及搜尋 15 4.3 STR-GPU建樹及搜尋 22 5 實驗結果與分析 25 5.1 實驗環境 25 5.2 實驗資料與設定 25 5.3 CPU 實驗結果 26 5.3.1 資料量差異 26 5.3.2 維度差異 27 5.4 GPU 實驗結果 30 5.4.1 資料量差異 31 5.4.2 維度差異 31 5.4.3 節點位移次數和支配關係比較量 34 6 結論 37 參考文獻 38

[1] I. Bartolini, P. Ciaccia, and M. Patella, “Salsa: computing the skyline without scanning the whole sky,”
in Proceedings of the 15th ACM international conference on Information and knowledge management,
2006, pp. 405–414.
[2] S. Borzsony, D. Kossmann, and K. Stocker, “The skyline operator,” in Proceedings 17th International
Conference on Data Engineering, 2001, pp. 421–430.
[3] J. Chomicko, P. Godfrey, J. Gryz, and D. Liang, “Skyline with presorting,” in Proceedings 19th International
Conference on Data Engineering, 2003.
[4] P. Godfrey, R. Shipley, and J. Gryz, “Maximal vector computation in large data sets,” in Proceedings
of the 31st international conference on Very large databases, 2005, pp. 229–240.
[5] M. Goncalves and M.E.
Vidal, “Top-k skyline: A unified approach,” in On the Move to Meaningful
Internet Systems 2005: OTM 2005 Workshops, vol. 3762, 2005, pp. 790–799.
[6] A. Guttman, “R-trees:
a dynamic index structure for spatial searching,” in SIGMOD ’84: Proceedings
of the 1984 ACM SIGMOD international conference on Management of data, 1984, pp. 47–57.
[7] V. Hristidis, N. Koudas, and Y. Papakonstantinou, “Prefer: A system for the efficient execution of
multiparametric
ranked queries.” in Proceedings of the 2001 ACM SIGMOD International Conference
on Management of Data, vol. 30, 2001, pp. 259–270.
[8] I. Kamel and C. Faloutsos, “On packing r-trees,”
in CIKM ’93: Proceedings of the second international
conference on Information and knowledge management, 1993, pp. 490 – 499.
[9] J. Kim, S.G.
Kim, and B. Nam, “Parallel multi-dimensional
range query processing with r-trees
on GPU,” Journal of Parallel and Distributed Computing, vol. 73, pp. 1195–1207, 2013.
[10] D. Kossmann, F. Ramsak, and S. Rost, “Shooting stars in the sky: An online algorithm for skyline
queries,” in VLDB ’02: Proceedings of the 28th International Conference on Very Large Databases,
2002, pp. 275–286.
[11] J. Lee, G. won You, and S. won Hwang, “Personalized top-k
skyline queries in high dimensional
space,” Information System, vol. 34, pp. 45–61, 2009.
[12] K. C. K. Lee, B. Zheng, H. Li, and W.C.
Lee, “Approaching the skyline in Z order,” in the 33rd
International Conference on Very Large Data Bases (VLDB’07), 2007, pp. 279 – 290.
[13] S. T. Leutenegger, M. A. Lopez, and J. Edgington, “Str: a simple and efficient algorithm for r-tree
packing,” in Proceedings 13th International Conference on Data Engineering, 1997, pp. 497 – 506.
[14] X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang, “Selecting stars: The k most representative skyline operator,”
in 2007 IEEE 23rd International Conference on Data Engineering, 2007, pp. 86 – 95.
[15] Y.Y.
Lin and W.M.
Chen, “A study of selection for representative skyline points on GPUs,” 2019.
[16] L. Luo, M. D. Wong, and L. Leong, “Parallel implementation of r-trees
on the GPU,” in 17th Asia and
South Pacific Design Automation Conference, 2012.
[17] D. Papadias, Y. Tao, G. Fu, and B. Seeger, “Progressive skyline computation in database systems,”
ACM Transactions on Database Systems., vol. 30, pp. 41–82, 2005.
[18] S. K. Prasad, M. McDermott, and X. He, “GPU-based
parallel r-tree
construction and querying,” in
2015 IEEE International Parallel and Distributed Processing Symposium Workshop, 2015.
[19] S. K. Prasad, M. McDermott, X. He, and S. Puri, “GPU-based
parallel r-tree
construction and querying,”
in 2015 IEEE International Parallel and Distributed Processing Symposium Workshop, 2015.
[20] N. Roussopoulos and D. Leifker, “Direct spatial search on pictorial databases using packed r-trees,”
ACM SIGMOD Record, pp. 17–31, 1985.
[21] A. Vlachou, C. Doulkeridis, and M. Halkidi, “Discovering representative skyline points over distributed
data,” in Scientific and Statistical Database Management, 2012.
[22] M. L. Yiu and N. Mamoulis, “Multidimensional
top-k
dominating queries,” The VLDB Journal VLDB,
vol. 18, pp. 695–718, 2009.
[23] S. You, J. Zhang, and L. Gruenwald, “Parallel spatial query processing on GPUs using r-trees,”
in
BigSpatial ’13: Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Analytics for
Big Geospatial Data, 2013, pp. 23–31.

無法下載圖示 全文公開日期 2025/12/16 (校內網路)
全文公開日期 本全文未授權公開 (校外網路)
全文公開日期 本全文未授權公開 (國家圖書館:臺灣博碩士論文系統)
QR CODE