大型時空資料庫中拓樸樣式探勘之漸進式維護

Abstract

在許多空間時間資料庫的生活應用，例如環境生態分析、氣象分析、位置基礎分析，大都隨著時間變化做增量的更新。當資料庫增量更新後，有些已發現的拓撲樣式會無效，而有些新的拓撲樣式會出現。 當新的事件加入資料庫，假如每一次的更新都必須重新探勘拓撲樣式，將是一件既沒效率且不切實際的工作。儘管最近有學者提出維護拓撲樣式的方法，而且我們也可以應用既有探勘靜態資料庫的演算法重新探勘更新後的資料庫。然而，既存的演算法並不是非常有效率。 在大型時空資料庫中拓撲樣式探勘之漸進式維護是一件艱鉅的工作，因為拓撲樣式探勘相較一般項目集樣式是比較複雜的。在這篇論文，我們提出一個演算法，Inc_TMiner，主要是設計在增量的時空資料庫中維護拓撲樣式。在合成資料的實驗結果顯示 Inc_TMiner 在執行時間優於之前的漸進式演算法，也優於利用現有探勘靜態資料庫的演算法重新探勘更新後的資料庫。

Spatial temporal data mining is an important research area with many interesting topics, such as ecology analysis, meteorology analysis, location-based analysis and so forth. Most spatial temporal databases are updating incrementally with time. Some discovered topological patterns may be invalidated and some new topological patterns may be introduced by the evolution of databases. When new instances are inserted into the database, we can re-mine topological patterns from scratch each time using the existing static algorithms. Some researches on the maintenance of topological patterns in an incremental manner are proposed. However, all static algorithms and incremental algorithms are incompetent and not scalable. In this thesis, an efficient algorithm, Inc_TMiner (Incremental Topology Miner) is developed to incrementally maintain topological patterns from spatial-temporal databases. The experimental results on synthetic datasets indicate that Inc_TMiner significantly outperforms the static algorithms and the existing incremental algorithm in execution time and possesses graceful scalability.