Approximating frequent items in asynchronous data stream over a sliding window

Ho Leung Chan, Tak Wah Lam, Lap Kei Lee, Hing Fung Ting

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Citations (Scopus)

Abstract

In an asynchronous data stream, the data items may be out of order with respect to their original timestamps. This paper gives a space-efficient data structure to maintain such a data stream so that it can approximate the frequent item set over a sliding time window with sufficient accuracy. Prior to our work, Cormode et al. [3] have the best solution, with space complexity O( 1/ε log W log (ε B/log W) min{log W, 1/ε } log U), where ε is the given error bound, W and B are parameters of the sliding window, and U is the number of all possible item names. Our solution reduces the space to O( 1/ε log W log (ε B/log W )). We also unify the study of synchronous and asynchronous data stream by quantifying the delay of the data items. When the delay is zero, our solution matches the space complexity of the best solution to the synchronous data streams [8].

Original languageEnglish
Title of host publicationApproximation and Online Algorithms - 7th International Workshop, WAOA 2009, Revised Papers
Pages49-61
Number of pages13
DOIs
Publication statusPublished - 2009
Externally publishedYes
Event7th Workshop on Approximation and Online Algorithms, WAOA 2009 - Copenhagen, Denmark
Duration: 10 Sept 200911 Sept 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5893 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th Workshop on Approximation and Online Algorithms, WAOA 2009
Country/TerritoryDenmark
CityCopenhagen
Period10/09/0911/09/09

Fingerprint

Dive into the research topics of 'Approximating frequent items in asynchronous data stream over a sliding window'. Together they form a unique fingerprint.

Cite this