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

transaction
guarantee
dismissal
monitoring
time
trend

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

An approximate approach for maintaining recent occurrences of itemsets in a sliding window over data streams. / Koh, Jia Ling; Shin, Shu Ning; Don, Yuan Bin.

Complex Data Warehousing and Knowledge Discovery for Advanced Retrieval Development: Innovative Methods and Applications. IGI Global, 2009. p. 308-327.

Research output: Chapter in Book/Report/Conference proceedingChapter

Koh, JL, Shin, SN & Don, YB 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. IGI Global, pp. 308-327. https://doi.org/10.4018/978-1-60566-748-5.ch014
Koh JL, Shin SN, Don YB. 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. IGI Global. 2009. p. 308-327 https://doi.org/10.4018/978-1-60566-748-5.ch014
Koh, Jia Ling ; Shin, Shu Ning ; Don, Yuan Bin. / An approximate approach for maintaining recent occurrences of itemsets in a sliding window over data streams. Complex Data Warehousing and Knowledge Discovery for Advanced Retrieval Development: Innovative Methods and Applications. IGI Global, 2009. pp. 308-327
@inbook{ac7dea4bbbf54a9fa895e47a746d4745,
title = "An approximate approach for maintaining recent occurrences of itemsets in a sliding window over data streams",
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.",
author = "Koh, {Jia Ling} and Shin, {Shu Ning} and Don, {Yuan Bin}",
year = "2009",
doi = "10.4018/978-1-60566-748-5.ch014",
language = "English",
isbn = "9781605667485",
pages = "308--327",
booktitle = "Complex Data Warehousing and Knowledge Discovery for Advanced Retrieval Development: Innovative Methods and Applications",
publisher = "IGI Global",

}

TY - CHAP

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

AU - Koh, Jia Ling

AU - Shin, Shu Ning

AU - Don, Yuan Bin

PY - 2009

Y1 - 2009

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

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

UR - http://www.scopus.com/inward/record.url?scp=84900125042&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84900125042&partnerID=8YFLogxK

U2 - 10.4018/978-1-60566-748-5.ch014

DO - 10.4018/978-1-60566-748-5.ch014

M3 - Chapter

AN - SCOPUS:84900125042

SN - 9781605667485

SP - 308

EP - 327

BT - Complex Data Warehousing and Knowledge Discovery for Advanced Retrieval Development: Innovative Methods and Applications

PB - IGI Global

ER -