(3.80.6.131) 您好!臺灣時間:2021/05/17 03:48
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:林承毅
研究生(外文):LIN, CHENG-YI
論文名稱:使用GPU及分塊計算方法來加速k-近鄰演算法
論文名稱(外文):Accelerating k-Nearest Neighbor Algorithm Using GPU and Chunking Method
指導教授:阮議聰
指導教授(外文):Juan, Yee-Jsong
口試委員:廖怡欽黃崇仁阮議聰賴榮滄
口試委員(外文): Juan, Yee-Jsong
口試日期:2015-06-26
學位類別:碩士
校院名稱:國立臺灣海洋大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
語文別:中文
論文頁數:65
中文關鍵詞:CUDAGPUk-近鄰算法分塊最近鄰算法
外文關鍵詞:CUDAGPUKNNChunkingNN
相關次數:
  • 被引用被引用:0
  • 點閱點閱:121
  • 評分評分:
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
摘要 I
Abstract II
目錄 III
圖目錄 V
表目錄 VII
演算法目錄 VIII
第一章 1
緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 論文架構 3
第二章 4
相關研究 4
2.1暴力法 (Brute Force) kNN 4
2.2 GPU-FS-kNN 4
第三章 6
系統架構 6
3.1系統流程簡介 6
3.2 k-近鄰算法 (k-nearest Neighbor) 8
3.3皮爾森距離 (Pearon distance) 9
3.4本論文方法 9
3.5 Distance Kernel 18
3.6 kNN Kernel 22
第四章 34
實驗與分析 34
4.1 測試資料集合與硬體配備 34
4.2 實驗結果 36
4.3 方法與參數比較 43
4.4 系統參數設定與比較 46
第五章 61
結論 61
參考文獻 62

[1] HU H, WEN Y, CHUA T, LI X. Toward Scalable Systems for Big Data Analytics: A Technology Tutorial. IEEE Access. 2014;2:652-87. doi: 10.1109/ACCESS.2014.2332453.
[2] WANG Y, WANG Z. The Impact of Data Mining on Management Accounting in Big Data Era. Proceedings of Annual Paris Business Research Conference; 2015 August 13-14; France. Paris; 2015. p. 1-11.
[3] Bansal S, Rana A. Transitioning from Relational Databases to Big Data. International Journal of Advanced Research in Computer Science and Software Engineering. 2014; 4(1):626-30.
[4] Mauro AD, Greco M, Grimaldi M. What is big data? A consensual definition and a review of key research topics. Proceedings of the 4th International Conference on Integrated Information; 2014 September 5-8; Spain, Madrid: AIP Conference; 2015. doi:10.1063/1.4907823.
[5] Chandrika M, Parvathy J, Srinidhi BS, Bhandi V, Balaji S. Impact of Big Data and Emerging Research Trends. Proceedings of Computational Systems for Health & Sustainability; 2015 April 17-18; Bangalore, Karnataka, INDIA: 2015. p. 14-7.
[6] UC Irvine Machine Learning Repository[Interner]. c2007- [cited 2015 Oct 26]. Available from: https://archive.ics.uci.edu/ml/index.html
[7] Ghorpade J, Parande J, Kulkarni M, Bawaskar A. GPGPU PROCESSING IN CUDA ARCHITECTURE. Advanced Computing . 2012;3(1):105-20. doi : 10.5121/acij.2012.3109.
[8] Mitchell T (Carnegie Mellon University, School of Computer Science). The Discipline of Machine Learning. Machine Learning Department technical report. (US). 2006 July. Report No.: CMU-ML-06-108.
[9] Egghe L, Leydesdorff L. the relation between Pearson's correlation coefficient r and Salton's cosine measure. American Society for Information Science and Technology. 2009;60(5). doi: 10.1016/j.eswa.2012.07.016.
[10] Domingos P. A Few Useful Things to Know about Machine Learning. Communications of the ACM. 2012; 55(10):78-87. doi: 10.1145/2347736.2347755.
[11] N. Suguna and Dr. K. Thanushkodi. An Improved k-Nearest Neighbor Classification Using Genetic Algorithm. International Journal of Computer Science Issues. 2010;7(4):18–21.
[12] Arefin AS, Riveros C, Berretta R, Moscato P. GPU-FS-kNN: A Software Tool for Fast and Scalable kNN Computation Using GPUs. PLoS ONE. 2012;7(8). doi: 10.1371/journal.pone.0044000.
[13] Hastie T, Tibshirani R. Discriminant Adaptive Nearest Neighbor Classification. IEEE Transactions on pattern analysis and machine intelligence. 1996;18:607-16. doi: 10.1109/34.506411.
[14] Fulekar MH, editors. Bioinformatics: Applications in Life and Environmental Sciences, Springer. 2009. p. 110.
[15] Garcia V, Nielsen F. Searching High-Dimensional Neighbours: CPU-Based Tailored Data-Structures Versus GPU-Based Brute-Force Method. Proceedings of Computer Vision/Computer Graphcis Collaboration Techniques and Applications (MIRAGE); 2009 May 4-6; Rocquencourt, France: Springer; 2009;425-36. doi: 10.1007/978-3-642-01811-4_38.
[16] Chen J, Fang H, Saad Y. Fast Approximate kNN Graph Construction for High Dimensional Data via Recursive Lanczos Bisection. Machine Learning Research. 2009;10:1989-2012. doi: 10.1145/1577069.1755852.
[17] Garcia V, Debreuve E, Barlaud M.Fast k nearest neighbor search using GPU. Proceedings of Computer Vision and Pattern Recognition Workshops, CVPRW '08; 2008 June 23-28; Anchorage, AK; 2008:1-6. doi: 10.1109/CVPRW.2008.4563100.
[18] Gou J, Du L, Zhang Y, Xiong T. A New Distance-weighted k-nearest Neighbor Classifier. Information & Computational Science. 2012;9:1429-36
[19] Kaur P, Nishi. A Survey on CUDA. Computer Science & Information Technologies. 2014;5(2):2210-4.
[20] Gieseke F, Heinermann J, Oancea C, Igel C. Buffer k-d Trees: Processing Massive Nearest Neighbor Queries on GPUs. Proceedings of the 31st ICML. 2014, Beijing, China: JMLR: W&CP; 2014. p. 172-80.
[21] Cong J, Zou Y. Parallel Multi-level Analytical Global Placement on Graphics Processing Unit. Proceedings of the Computer-Aided Design; 2009 November 2–5; San Jose, California, USA: IEEE; 2009. p. 681–8.
[22] Advanced CUDA C [Internet]. Micikevicius P, NVIDIA Corporation; 2009. Available from: http://www.nvidia.com/content/GTC/documents/1029_GTC09.pdf
[23] Collet P, Kruger F, Maitre O, editors. Automatic Parallelization of EC on GPGPUs and Clusters of GPGPU Machines with EASEA and EASEA-CLOUD. Massively Parallel Evolutionary Computation on GPGPUs. 2009:35-59. doi: 10.1007/978-3-642-37959-8_3.
[24] Ghahramani Z. Unsupervised Learning. Advanced Lectures on Machine Learning: Springer, 2004. p. 72–112. doi:10.1007/978-3-540-28650-9_5
[25] CUDA C Programming Guide [Internet]. NVIDIA Corporation; 2015. Available from: http://docs.nvidia.com/CUDA/CUDA-c-programming-guide/
[26] Khan A, Al-Mouhamed M, Fatayar A, Almousa A, Baqais A, Assayony M. Padding Free Bank Conflict Resolution for CUDA-Based Matrix Transpose Algorithm. Networked and Distributed Computing. 2014;2(3):124-134. Doi: 10.1109/SNPD.2014.6888709.
[27] Boyer V, Baz DE. Recent Advances on GPU Computing in Operations Research. Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum; 2013 May 20-24; Cambridge, MA: IEEE; 2013 p. 1778–87. doi: 10.1109/IPDPSW.2013.45.
[28] Jablin TB, Prabhu P, Jablin JA, Johnson NP, Beard SR, August DI. Automatic CPU-GPU Communication Management and Optimization. Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation; 2011 June 4-8; New York, USA:ACM;2011. p. 142–151. doi: 10.1145/1993498.1993516.
[29] Owens JD, Houston M, Luebke D, Green S, Stone JE, Philips JC. GPU Computing. Proceedings of the IEEE. 2008;96(5):879-899. doi: 10.1109/JPROC.2008.917757
[30] Xie L; The Travelers Companies Inc. The Travelers Companies Inc. KNN Classification and Regression using SAS. Paper SD-09. 2012;
[31] Chiang TH, Lo HY, Lin SD. A Ranking-based KNN Approach for Multi-Label Classification. Proceedings of JMLR: Workshop and Conference. 2012;25:81-96.
[32] Andoni A, Indyk P. Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. Communications of the ACM. 2008;51(1): 117–122. doi: 10.1145/1327452.1327494.
[33] Li Q, Kecman V, Salman R. A Chunking Method For Ruclidean Distance Matrix Calculation on Large Dataset Using multi-GPU. Proceedings of the 2010 Ninth ICMLA; 2010 Washington, DC, USA: IEEE; 2010. p. 208–213. doi: 10.1109/ICMLA.2010.38.
[34] Holk E, Byrd W, Mahajan N, Willcock J, Chauhan A, Lumsdaine A. Declarative Parallel Programming for GPUs. Tools and Techniques on the Road to Exascale Computing. 2011;22:297-304. doi:10.3233/978-1-61499-041-3-297.
[35] Mahe P, Arsac M, Chatellier S, Monnin V, Perrot N, Mailler S, Girard V, Ramjeet M, Surre J, Lacroix B, Belkum AV, Veyrieras JB. Automatic Identification of Mixed Bacterial Species Fingerprints in a MALDI-TOF Mass-Spectrum. Bioinformatics. 2014;30(9):1280-6. doi: 10.1093/bioinformatics/btu022.
[36] CUDA Pro Tip: Occupancy API Simplifies Launch Configuration. [Internet]. Harris M. NVIDIA Corporation; 2014, Available from: http://devblogs.nvidia.com/parallelforall/CUDA-pro-tip-occupancy-api-simplifies-launch-configuration/

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top