簡易檢索 / 詳目顯示

研究生: 黃子玹
Tzu-Hsuan Huang
論文名稱: DBSCAN於GPU加速計算平台之研究
A study on accelerating DBSCAN using GPU
指導教授: 陳維美
Wei-Mei Chen
口試委員: 吳晉賢
Chin-Hsien Wu
林昌鴻
Chang-Hong Lin
林淵翔
Yuan-Hsiang Lin
學位類別: 碩士
Master
系所名稱: 電資學院 - 電子工程系
Department of Electronic and Computer Engineering
論文出版年: 2020
畢業學年度: 108
語文別: 中文
論文頁數: 50
中文關鍵詞: 分群DBSCAN平行演算法GPU
外文關鍵詞: clustering, DBSCAN, parallel, algorithm, GPU
相關次數: 點閱:326下載:0
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報


摘 要 I ABSTRACT II 第一章 緒論 1 1.1 研究動機 1 1.2 研究背景 2 1.3 論文架構 3 第二章 GPU架構 4 2.1 NVIDIA GPU PASCAL硬體架構 4 2.2 CUDA之軟硬體架構 6 2.3 全域記憶體與共享記憶體 8 2.4 演算法設計限制 10 第三章 文獻探討 11 3.1 DBSCAN演算法 11 3.2 改進循序執行的DBSCAN演算法 13 3.3 平行的DBSCAN演算法 14 第四章 研究方法 17 4.1 平行建樹 17 4.2 平行尋找核心點 20 4.3 平行連結核心點群集 22 4.4 平行連結邊緣點與找出雜訊點 23 4.5 演算法概述 23 第五章 實驗模擬 25 5.1 實驗設定 25 5.2 實驗結果 27 第六章 結論 39 參考文獻 40

[1] "CUDA Compute Capability. " [Online]. Available: https://developer.nvidia.com/cuda-gpus
[2] R. Agrawal, J. Gehrke, D. Gunopulos, and P. Raghavan, "Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications." ACM SIGMOD international conference on Management of data , pp. 94-105, 1998.
[3] G. Andrade, G. Ramos, D. Madeira, R. Sachetto, R. Ferreira, and L. Rocha, "Gdbscan: A gpu accelerated algorithm for density-based clustering." Procedia Computer Science, vol. 18, pp. 369-378, 2013.
[4] M. Ankerst, M.M. Breunig, H.P. Kriegel, and J. Sander Sander, "OPTICS: Ordering points to identify the clustering structure." Proceedings of the 1999 ACM SIGMOD international conference on Management of data , vol. 28, No. 2, pp. 49-60, Aug.1999.
[5] D. Arlia, and M. Coppola, "Experiments in parallel clustering with DBSCAN." European Conference on Parallel Processing, pp. 326-331, Aug. 2001.
[6] N. Beckmann, H.P Kriegel, R. Schneider , and B. Seeger , "The tree: an efficient and robust access method for points and rectangles. " Proceedings of the 1990 ACM SIGMOD international conference on Management of data , vol. 19. No. 2, 322-331, May. 1990.
[7] C. Böhm, R. Noll, C. Plant, and B. Wackersreuther, "Density-based clustering using graphics processors." Proceedings of the 18th ACM conference on Information and knowledge management, pp. 661–670, Nov. 2009.
[8] B. Borah and D. Bhattacharyya, "An improved sampling-based dbscan for large spatial databases." International Conference on Intelligent Sensing and Information Processing, pp. 92–96, Jan. 2004.
[9] J. Cheng, M. Grossman, and T. McKercher, Professional CUDA C programming. John & Wiley Sons Inc, Indianapolis, 2014.
[10] M. Ester, H.-P. Kriegel, J. Sander, X. Xu, " A density-based algorithm for discovering clusters in large spatial databases with noise." KDD, vol. 96, no. 34, pp. 226–231, 1996.
[11] V. Estivill-Castro and I. Lee, "AUTOCLUST: Automatic clustering via boundary extraction for mining massive point-data sets." In Proceedings of the 5th International Conference on Geocomputation, 2000.
[12] V. Estivill-Castro and I. Lee, "AMOEBA: Hierarchical clustering based on spatial proximity using delaunay diagram." Proceedings of the 9th International Symposium on Spatial Data Handling. Beijing, China, pp. 1–16, Aug. 2000.
[13] M. Gowanlock, Cody M. Rude, David M. Blair, Justin D. Li, and Victor Pankratius, "A Hybrid Approach for Optimizing Parallel Clustering Throughput using the GPU." IEEE Transactions on Parallel and Distributed Systems, vol. 30, no. 4 , pp. 766–777, 2019.
[14] S. Guha, R. Rastogi, and K. Shim, "ROCK: A robust clustering algorithm for categorical attributes." Information systems, vol. 25, no. 5, pp. 345–366, July. 2000.
[15] A. Hinneburg and Daniel A. Keim, "An efficient approach to clustering in large multimedia databases with noise." KDD, vol. 98, pp. 58–65, Aug. 1998.
[16] I. Kamel, and C. Faloutsos, "On packing R-trees." CIKM, vol. 93, pp. 490–499, 1993.
[17] G. Karypis, E.-H. Han, and V. Kumar, "Chameleon: Hierarchical clustering using dynamic modeling." Computer, vol. 32, no. 8, pp. 68–75, Aug. 1999.
[18] M. Kryszkiewicz and P. Lasek, "TI-DBSCAN: Clustering with dbscan by means of the triangle inequality. " International Conference on Rough Sets and Current Trends in Computing. Springer, pp. 60–69, 2010.
[19] K. M. Kumar and A. R. M. Reddy, "A fast dbscan clustering algorithm by accelerating neighbor searching using groups method." Pattern Recognition, vol. 58, pp. 39–48, 2016.
[20] W.K. Loh and H. Yu. "Fast density-based clustering through dataset partition using graphics processing units." Information Sciences, vol. 308, pp. 94-112, July. 2015
[21] A. Lulli, M. Dell' Amico, P. Michiardi, and L. Ricci. "NG-DBSCAN: scalable density-based clustering for arbitrary data." Proceedings of the VLDB Endowment, vol.10, pp. 157-168, 2016.
[22] J. MacQueen, "Some methods for classification and analysis of multivariate observations. " Proceedings of the 55th Berkeley symposium on mathematical statistics and probability, vol. 1, no. 14, pp. 281-297, 1967.
[23] D. Palsetia, A. Agrawal, W.K. Liao, F. Manne, and A. Choudhary. "A new scalable parallel DBSCAN algorithm using the disjoint-set data structure." In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, Networking, Storage and Analysis, no. 62, Nov. 2012.
[24] W. Panny, H. Prodinger. "Bottom-up mergesort—a detailed analysis." Algorithmica, vol. 14, pp. 340-354, Oct. 1995.
[25] H. Song, and J.G. Lee. "RP-DBSCAN: A superfast parallel DBSCAN algorithm based on random partitioning." In Proceedings of the 2018 International Conference on Management of Data, pp. 1173-1187, 2018.
[26] H. Tan, W. Luo, H. Mao, D. Ma, S. Feng, and J. Fan. "MR-DBSCAN: an efficient parallel density-based clustering algorithm using MapReduce." IEEE 17th International Conference on Parallel and Distributed Systems, pp. 473-480, Dec. 2011
[27] P. Viswanath and R. Pinkesh, "l-DBSCAN: A fast hybrid density based clustering method. " 18th International Conference on Pattern Recognition (ICPR'06), vol. 1, pp. 912–915, 2006.
[28] P. Viswanath and V. S. Babu, "Rough-DBSCAN: A fast hybrid density based clustering method for large data sets." Pattern Recognition Letters, vol. 30, no. 16, pp. 1477–1488, 2009.
[29] B. Walczak and D. Massart, "Rough sets theory." Chemometrics and Intelligent Laboratory Systems, vol. 47, pp. 1–16, 1999.
[30] W. Wang, J. Yang, and R. Muntz Muntz. "STING: A Statistical Information grid Approach to Spatial Data Mining." International Conference on Very Large Data Base, vol. 97, pp. 186-195, 1997.
[31] X. Xu, J. Jager, and H.P. Kriegel. "A fast parallel clustering algorithm for large spatial databases." High Performance Data Mining, vol. 3, no. 3, pp. 263-290, Sept. 1999.
[32] K. Yang, Y. Gao, R. Ma, L. Chen, S. Wu, and G. Chen. "DBSCAN-MS: Distributed Density-Based Clustering in Metric Spaces." In 2019 IEEE 35th International Conference on Data Engineering, pp. 1346-1357, 2019.
[33] T. Zhang, R. Ramakrishnan, and M. Livny. "BIRCH: an efficient data clustering method for very large databases." Proceedings of the 1996 ACM SIGMOD international conference on Management of data, vol. 25, no. 2, pp. 103-144, 1996.

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