陳銘憲臺灣大學：電機工程學研究所陳伯翰Chen, Bo-HanBo-HanChen2007-11-262018-07-062007-11-262018-07-062007http://ntur.lib.ntu.edu.tw//handle/246246/53447傳統的循序樣式探勘演算法需要龐大的計算時間。當面臨累進式資料庫探勘時所需要的時間更多。在本論文中，我們設計了一種硬體的樹狀結構，用來解決累進式循序樣式探勘的問題。我們的演算法簡稱為HATS，運用樹狀結構代表每一個序列中的循序元素。透過管線設計，HATS可以高效率的產生循序元素。我們透過軟硬體共同設計，在可規劃邏輯閘陣列上，完成實體電路的設計與驗証。我們的實驗結果也顯示HATS不僅在隨機的測試資料中，明顯地比現有的所有循序樣式探勘演算法快速；並且對於一個在無線閘道的實際應用上表現優異。在這個無線閘道的系統中，透過對網路存取的歷史資料，進行累進式循序樣式探勘，可以提供閘道上預先傳送一個具有高度預測性的規則，進而大幅度的降低了無線使用者的存取延遲。我們的系統可以運用到其他需要即時累進式循序樣式探勘的場合。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.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 754313036 bytesapplication/pdfen-US樹資料探勘累進式循序樣式探勘硬體加速結構設計即時可規劃邏輯閘陣列TreeData MiningProgressive Sequential Pattern MiningHardware-enhancedArchitecture DesignReal-timeFPGAthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53447/1/ntu-96-R94921031-1.pdf