File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Finding heavy hitters over the sliding window of a weighted data stream

TitleFinding heavy hitters over the sliding window of a weighted data stream
Authors
Issue Date2008
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2008, v. 4957 LNCS, p. 699-710 How to Cite?
AbstractWe study the problem of identifying items with heavy weights in the sliding window of a weighted data stream. We give a deterministic algorithm that solves the problem within error bound ε, uses space and supports query and update times. Here, R is the maximum item weight. We also show that the space can be reduced substantially in practice by showing for any c∈>∈0, we can construct an -space algorithm, which returns correct answers provided that the ratio between the total weights of any two adjacent sliding windows is not greater than c. We also give a randomized algorithm that solves the problem with success probability 1∈-∈δ using space where D is the number of distinct items in the data stream. © 2008 Springer-Verlag Berlin Heidelberg.
Persistent Identifierhttp://hdl.handle.net/10722/93436
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorHung, RYSen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-09-25T15:01:06Z-
dc.date.available2010-09-25T15:01:06Z-
dc.date.issued2008en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2008, v. 4957 LNCS, p. 699-710en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93436-
dc.description.abstractWe study the problem of identifying items with heavy weights in the sliding window of a weighted data stream. We give a deterministic algorithm that solves the problem within error bound ε, uses space and supports query and update times. Here, R is the maximum item weight. We also show that the space can be reduced substantially in practice by showing for any c∈>∈0, we can construct an -space algorithm, which returns correct answers provided that the ratio between the total weights of any two adjacent sliding windows is not greater than c. We also give a randomized algorithm that solves the problem with success probability 1∈-∈δ using space where D is the number of distinct items in the data stream. © 2008 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.titleFinding heavy hitters over the sliding window of a weighted data streamen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-540-78773-0_60en_HK
dc.identifier.scopuseid_2-s2.0-43049118248en_HK
dc.identifier.hkuros149514en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-43049118248&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume4957 LNCSen_HK
dc.identifier.spage699en_HK
dc.identifier.epage710en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridHung, RYS=14028462000en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats