An approximate approach for maintaining recent occurrences of itemsets in a sliding window over data streams

Jia Ling Koh, Shu Ning Shin, Yuan Bin Don

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

Recently, the data stream, which is an unbounded sequence of data elements generated at a rapid rate, provides a dynamic environment for collecting data sources. It is likely that the embedded knowledge in a data stream will change quickly as time goes by. Therefore, catching the recent trend of data is an important issue when mining frequent itemsets over data streams. Although the sliding window model proposed a good solution for this problem, the appearing information of patterns within a sliding window has to be maintained completely in the traditional approach. For estimating the approximate supports of patterns within a sliding window, the frequency changing point (FCP) method is proposed for monitoring the recent occurrences of itemsets over a data stream. In addition to a basic design proposed under the assumption that exact one transaction arrives at each time point, the FCP method is extended for maintaining recent patterns over a data stream where a block of various numbers of transactions (including zero or more transactions) is inputted within a fixed time unit. Accordingly, the recently frequent itemsets or representative patterns are discovered from the maintained structure approximately. Experimental studies demonstrate that the proposed algorithms achieve high true positive rates and guarantees no false dismissal to the results yielded. A theoretic analysis is provided for the guarantee. In addition, the authors' approach outperforms the previously proposed method in terms of reducing the run-time memory usage significantly.

Original languageEnglish
Title of host publicationComplex Data Warehousing and Knowledge Discovery for Advanced Retrieval Development: Innovative Methods and Applications
PublisherIGI Global
Pages308-327
Number of pages20
ISBN (Print)9781605667485
DOIs
Publication statusPublished - 2009

    Fingerprint

ASJC Scopus subject areas

  • Social Sciences(all)

Cite this

Koh, J. L., Shin, S. N., & Don, Y. B. (2009). An approximate approach for maintaining recent occurrences of itemsets in a sliding window over data streams. In Complex Data Warehousing and Knowledge Discovery for Advanced Retrieval Development: Innovative Methods and Applications (pp. 308-327). IGI Global. https://doi.org/10.4018/978-1-60566-748-5.ch014