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

Hardware Architecture of Tree Structure for Real-time Progressive Sequential Pattern Mining

陳伯翰(Bo-Han Chen)

指導教授 ： 陳銘憲

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2007年)

https://doi.org/10.6342/NTU.2007.01033

摘要

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

並列關鍵字

Tree ； Data Mining ； Progressive Sequential Pattern Mining ； Hardware-enhanced ； Architecture Design ； Real-time ； FPGA

參考文獻

[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.