Paper 6

Efficient Single Pass Ordered Incremental Pattern Mining

Authors: Yun Sing Koh and Gillian Dobbie

Volume 8 (2013)

Abstract

Since the introduction of FP-growth using FP-tree there has been a lot of research into extending its usage to data stream or incremen- tal mining. Most incremental mining adapts the Apriori algorithm. How- ever, we believe that using a tree based approach would increase perfor- mance as compared to the candidate generation and testing mechanism used in Apriori. Despite this, FP-tree still requires two scans through a dataset. In this paper we present a novel tree structure called Single Pass Ordered Tree, SPO-Tree, that captures information with a single scan for incremental mining. All items in a transaction are inserted/sorted based on their frequency. The tree is reorganized dynamically when necessary. SPO-Tree allows for easy maintenance in an incremental or data stream environment.