請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/29920完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳銘憲(Ming-Syan Chen) | |
| dc.contributor.author | Bo-Han Chen | en |
| dc.contributor.author | 陳伯翰 | zh_TW |
| dc.date.accessioned | 2021-06-13T01:25:00Z | - |
| dc.date.available | 2007-07-20 | |
| dc.date.copyright | 2007-07-20 | |
| dc.date.issued | 2007 | |
| dc.date.submitted | 2007-07-18 | |
| dc.identifier.citation | [1] R. Agrawal and R. Srikant. “Mining sequential patterns,” Proceedings of ICDE, 1995.
[2] J. Ayres, J. Gehrke, T. Yiu, and J. Flannick. “Sequential pattern mining using a bitmap representation,” Proceedings of ACM SIGKDD, 2002. [3] G. Chen, X. Wu, and X. Zhu. “Sequential pattern mining in multiple streams,” Proceedings of ICDM, 2005. [4] J.-W. Huang, C.-Y. Tseng, J.-C. Ou and M.-S. Chen, “On Progressive Sequential Patters Mining,” Proceedings of ACM CIKM, 2006. [5] J.-W. Huang, C.-Y. Tseng, J.-C. Ou and M.-S. Chen, “A General Model for Sequential Pattern Mining with a Progressive Database”, revised by Transaction of IEEE TKDE. [6] H. Cheng, X. Yan, and J. Han.” Incspan: Incremental mining of sequential patterns in large database,” Proceedings of ACM SIGKDD, 2004. [7] S. Cong, J. Han, and D. Padua. “Parallel mining of closed sequential patterns,” Proceedings of ACM SIGKDD, 2005. [8] M. N. Garofalakis, R. Rastogi, and K. Shim. “Spirit: Sequential pattern mining with regular expression constraints,” Proceedings of VLDB, 1999. [9] J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal, and M. C. Hsu. “Freespan: Frequent pattern-projected sequential pattern mining,” Proceedings of ACM SIGKDD, 2000. [10] M.-Y. Lin and S.-Y. Lee. “Incremental update on sequential patterns in large databases by implicit merging and efficient counting.” Proceedings of IIS: IIPWM'04, May 17-20, 2004. [11] H. Mannila, H. Toivonen, and A. I. Verkamo. “Discovery of frequent episodes in event sequences,” Proceedings of IEEE ICDM, July, 1997. [12] F. Masseglia, P. Poncelet, and M. Teisseire. “Incremental mining of sequential patterns in large databases”, Proceedings of IEEE ICDM, July, 2003. [13] S. Parthasarathy, M. J. Zaki, M. Ogihara, and S. Dwarkadas. “Incremental and interactive sequence mining,” Proceedings of ICDM, 1999. [14] J. Pei, J. Han, H. Pinto, Q. Chen, U. Dayal, and M. C. Hsu. “Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth,” Proceedings of ICDE, 2001. [15] R. Srikant and R. Agrawal. “Mining sequential patterns: Generalizations and performance improvements.” Proceedings of EDBT, 1996. [16] M. Zhang, B. Kao, D. W.-L. Cheung, and C. L. Yip. “Efficient algorithms for incremental update of frequent sequences,” Proceedings of PAKDD, 2002. [17] H. Mei, Y-M Wen, and W-J Lin, “Turning an HTTP Proxy Server into a Wireless Internet Gateway” Proceedings of DSTA, May 2000, [18] D. Singelee, and B. Preneel, “The Wireleess Application Protocol”, COSIC Internal Report, Sep. 2003 [19] A. Balachandran, G. M. Voelker, and P.Bahl, “Characterizing User Behavior and Network Performance in a Public Wireless Lan,” Proceedings of the ACM SIGMETRICS, 2002 [20] Q. Yang and H. Zhang, “Web-log Mining for Predictive Web Caching,” IEEE TKDE vol. 15 no4 July, 2003 [21] D. Farin, W. Effelsberg, and Peter H. N. de , “Robust clustering-based video summarization with integration of domain knowledge,” Proceedings IEEE ICME,2002 [22] C. Romero1, S. Ventura1, J-A Delgado1, P-D Bra , “Personalized Links Recommendation Based on Data Mining in Adaptive Educational Hypermedia Systems” Proceedings AH, Spain, May 29 - 31, 2002. [23] D. T. Lee, HSU Chang, and C. K. Wong, “An On-Chip Compare/Steer Bubble Sorter”, IEEE TC, vol. C-30, no. 6, 1981 [24] A. B. Pandey, J. Srivastava, and S. Shekhar, “Web Proxy Server with Intelligent Prefetcher for Dynamic Pages Using Association Rules,” Technical Report Number: 01-004, CS Department of University of Minnesota, 2001 [25] Q. Yang, H-H Zhang, and T. Li, “Mining web logs for prediction models in WWW caching and prefetching,” Proceedings of ACM SIGKDD, 2001 | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/29920 | - |
| dc.description.abstract | 傳統的循序樣式探勘演算法需要龐大的計算時間。當面臨累進式資料庫探勘時所需要的時間更多。在本論文中，我們設計了一種硬體的樹狀結構，用來解決累進式循序樣式探勘的問題。我們的演算法簡稱為HATS，運用樹狀結構代表每一個序列中的循序元素。透過管線設計，HATS可以高效率的產生循序元素。我們透過軟硬體共同設計，在可規劃邏輯閘陣列上，完成實體電路的設計與驗証。我們的實驗結果也顯示HATS不僅在隨機的測試資料中，明顯地比現有的所有循序樣式探勘演算法快速；並且對於一個在無線閘道的實際應用上表現優異。在這個無線閘道的系統中，透過對網路存取的歷史資料，進行累進式循序樣式探勘，可以提供閘道上預先傳送一個具有高度預測性的規則，進而大幅度的降低了無線使用者的存取延遲。我們的系統可以運用到其他需要即時累進式循序樣式探勘的場合。 | zh_TW |
| dc.description.abstract | Traditional sequential pattern mining algorithms induce a significant amount of time. It is even worse on progressive database. In this paper, we design a hardware architecture to implement an efficient progressive sequential pattern mining algorithm. Our algorithm, HATS, uses a tree to maintain potential candidate sequential patterns in each sequence parallelly. With the pipeline design, HATS can generate candidate itemsets efficiently. We use software-hardware co-design technique on FPGA to design and verify our architecture. Our experimental result shows that HATS not only significantly outperforms competitive algorithms on synthetic datasets but also performs well on a real wireless gateway data. By processing wireless gateway log, the result of progressive sequential patterns mining provides a precise prefetching rule on wireless gateway, and minimizes the latency of mobile device query in a revolutionary way. Our design can also be adopted by other real-time applications of progressive sequential patterns mining. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T01:25:00Z (GMT). No. of bitstreams: 1 ntu-96-R94921031-1.pdf: 4313036 bytes, checksum: d51ecdfcba637779f32a4cd7959057e4 (MD5) Previous issue date: 2007 | en |
| dc.description.tableofcontents | ACKNOWLEDGEMENTS III
中文摘要 IV ABSTRACT V CONTENTS 1 FIGURES 3 ALGORITHMS 5 CHAPTER 1. INTRODUCTION 6 CHAPTER 2. PRELIMINARIES 11 2.1 PROBLEM DESCRIPTION 11 2.2 RELATED WORK 13 2.2.1 Sequential Pattern Mining 13 2.2.2 Wireless Gateway Prefetching System 14 CHAPTER 3. HARDWARE ARCHITECTURE OF HATS 17 3.1 OVERVIEW OF HARDWARE DESIGN 17 3.2 CANDIDATE PATTERNS GENERATION 20 3.2.1 Concept 20 3.2.2 Implementation 22 3.3 CONSTRUCTION OF HATS 23 3.3.1 Native HATS Construction Concept 26 3.3.2 Pipeline HATS Construction Concept 32 3.3.3 System Architecture Implementation 35 3.4 PARALLEL MERGING OF HATSS 39 3.4.1 Trees’ Parallel Merging Algorithm 41 3.4.2 Parallel Merging Implementation 42 3.4.3 Classification Enhanced Parallel Merging 44 CHAPTER 4. PERFORMANCE EVALUATION 48 4.1 COMPLEXITY ANALYSIS 48 4.1.1 Time Complexity Analysis 48 4.1.2 Space Complexity Analysis 52 4.2 WIRELESS GATEWAY PREFETCHING SYSTEM 53 4.3 EXPERIMENT RESULT 57 CHAPTER 5. CONCLUSION 68 CHAPTER 6. APPENDIX – ZEUS ARCHITECTURE 69 6.1 OVERVIEW OF ZEUS ARCHITECTURE 69 6.2 HARDWARE ARCHITECTURE OF ZEUS 71 6.2.1 Zero-time Multiple Sorter Algorithms 71 6.2.2 Hardware Architecture Design and implementation 72 6.3 PERFORMANCE EVALUATION 74 6.3.1 Complexity Analysis 74 6.3.2 Experimental Results 75 | |
| dc.language.iso | en | |
| dc.subject | 樹 | zh_TW |
| dc.subject | 資料探勘 | zh_TW |
| dc.subject | 累進式循序樣式探勘 | zh_TW |
| dc.subject | 硬體加速 | zh_TW |
| dc.subject | 結構設計 | zh_TW |
| dc.subject | 即時 | zh_TW |
| dc.subject | 可規劃邏輯閘陣列 | zh_TW |
| dc.subject | Tree | en |
| dc.subject | Real-time | en |
| dc.subject | Architecture Design | en |
| dc.subject | Hardware-enhanced | en |
| dc.subject | Progressive Sequential Pattern Mining | en |
| dc.subject | FPGA | en |
| dc.subject | Data Mining | en |
| dc.title | 應用於即時累進循序性樣式探勘的硬體樹狀結構設計 | zh_TW |
| dc.title | Hardware Architecture of Tree Structure for Real-time Progressive Sequential Pattern Mining | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 95-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 鄭卜壬,呂永和,王傑智,楊得年 | |
| dc.subject.keyword | 樹,資料探勘,累進式循序樣式探勘,硬體加速,結構設計,即時,可規劃邏輯閘陣列, | zh_TW |
| dc.subject.keyword | Tree,Data Mining,Progressive Sequential Pattern Mining,Hardware-enhanced,Architecture Design,Real-time,FPGA, | en |
| dc.relation.page | 83 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2007-07-18 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-96-1.pdf 未授權公開取用 | 4.21 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。