File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Approximating frequent items in asynchronous data stream over a sliding window

TitleApproximating frequent items in asynchronous data stream over a sliding window
Authors
KeywordsAsynchronous data stream
Data items
Data stream
Efficient data structures
Error bound
Issue Date2009
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 7th Workshop on Approximation and Online Algorithms (WAOA 2009), University of Copenhagen, Denmark, 10-11 September 2009. In Lecture Notes in Computer Science, 2009, v. 5893, p. 49-61 How to Cite?
AbstractIn 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]. © 2010 Springer-Verlag Berlin Heidelberg.
DescriptionLNCS v. 5893 is Proceedings of the 7th International Workshop, WAOA 2009
WAOA Session 7
Persistent Identifierhttp://hdl.handle.net/10722/93223
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLee, LKen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-09-25T14:54:37Z-
dc.date.available2010-09-25T14:54:37Z-
dc.date.issued2009en_HK
dc.identifier.citationThe 7th Workshop on Approximation and Online Algorithms (WAOA 2009), University of Copenhagen, Denmark, 10-11 September 2009. In Lecture Notes in Computer Science, 2009, v. 5893, p. 49-61en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93223-
dc.descriptionLNCS v. 5893 is Proceedings of the 7th International Workshop, WAOA 2009-
dc.descriptionWAOA Session 7-
dc.description.abstractIn 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]. © 2010 Springer-Verlag Berlin Heidelberg.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectAsynchronous data stream-
dc.subjectData items-
dc.subjectData stream-
dc.subjectEfficient data structures-
dc.subjectError bound-
dc.titleApproximating frequent items in asynchronous data stream over a sliding windowen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChan, HL: hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_HK
dc.identifier.emailLee, LK: lklee@cs.hku.hken_HK
dc.identifier.emailTing, HF: hfting@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityLee, LK=rp00140en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-12450-1_5en_HK
dc.identifier.scopuseid_2-s2.0-78651251138en_HK
dc.identifier.hkuros162182en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-78651251138&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume5893 LNCSen_HK
dc.identifier.spage49en_HK
dc.identifier.epage61en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 7th Workshop on Approximation and Online Algorithms (WAOA 2009), University of Copenhagen, Denmark, 10-11 September 2009. In Lecture Notes in Computer Science, 2009, v. 5893, p. 49-61-
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats