應用於即時累進循序性樣式探勘的硬體樹狀結構設計

Abstract

傳統的循序樣式探勘演算法需要龐大的計算時間。當面臨累進式資料庫探勘時所需要的時間更多。在本論文中，我們設計了一種硬體的樹狀結構，用來解決累進式循序樣式探勘的問題。我們的演算法簡稱為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.