研究生: |
黃子玹 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 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
[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.