File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Continuous monitoring of distributed data streams over a time-based sliding window

TitleContinuous monitoring of distributed data streams over a time-based sliding window
Authors
KeywordsAlgorithms
Communication
Distributed data streams
Frequent items
Quantiles
Issue Date2012
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Algorithmica, 2012, v. 62 n. 3-4, p. 1088-1111 How to Cite?
AbstractIn this paper we extend the study of algorithms for monitoring distributed data streams from whole data streams to a time-based sliding window. The concern is how to minimize the communication between individual streams and the root, while allowing the root, at any time, to report the global statistics of all streams within a given error bound. This paper presents communication-efficient algorithms for three classical statistics, namely, basic counting, frequent items and quantiles. The worst-case communication cost over a window is {Mathematical expression} bits for basic counting, {Mathematical expression} words for frequent items and {Mathematical expression} words for quantiles, where k is the number of distributed data streams, N is the total number of items in the streams that arrive or expire in the window, and ε<1 is the given error bound. The performance of our algorithms matches and nearly matches the corresponding lower bounds. We also show how to generalize these results to streams with out-of-order data. © 2011 Springer Science+Business Media, LLC.
Persistent Identifierhttp://hdl.handle.net/10722/152454
ISSN
2015 Impact Factor: 0.795
2015 SCImago Journal Rankings: 0.898
ISI Accession Number ID
Funding AgencyGrant Number
GRFHKU-713909E
HKU-716307E
Funding Information:

T. W. Lam is partially supported by the GRF Grant HKU-713909E.

 

DC FieldValueLanguage
dc.contributor.authorChan, HLen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorLee, LKen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2012-06-26T06:39:15Z-
dc.date.available2012-06-26T06:39:15Z-
dc.date.issued2012en_HK
dc.identifier.citationAlgorithmica, 2012, v. 62 n. 3-4, p. 1088-1111en_HK
dc.identifier.issn0178-4617en_HK
dc.identifier.urihttp://hdl.handle.net/10722/152454-
dc.description.abstractIn this paper we extend the study of algorithms for monitoring distributed data streams from whole data streams to a time-based sliding window. The concern is how to minimize the communication between individual streams and the root, while allowing the root, at any time, to report the global statistics of all streams within a given error bound. This paper presents communication-efficient algorithms for three classical statistics, namely, basic counting, frequent items and quantiles. The worst-case communication cost over a window is {Mathematical expression} bits for basic counting, {Mathematical expression} words for frequent items and {Mathematical expression} words for quantiles, where k is the number of distributed data streams, N is the total number of items in the streams that arrive or expire in the window, and ε<1 is the given error bound. The performance of our algorithms matches and nearly matches the corresponding lower bounds. We also show how to generalize these results to streams with out-of-order data. © 2011 Springer Science+Business Media, LLC.en_HK
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_HK
dc.relation.ispartofAlgorithmicaen_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectAlgorithmsen_HK
dc.subjectCommunicationen_HK
dc.subjectDistributed data streamsen_HK
dc.subjectFrequent itemsen_HK
dc.subjectQuantilesen_HK
dc.titleContinuous monitoring of distributed data streams over a time-based sliding windowen_HK
dc.typeArticleen_HK
dc.identifier.emailChan, HL: hlchan@cs.hku.hken_HK
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_HK
dc.identifier.emailLee, LK: lklee@mpi-inf.mpg.deen_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_fulltexten_US
dc.identifier.doi10.1007/s00453-011-9506-5en_HK
dc.identifier.scopuseid_2-s2.0-79952701285en_HK
dc.identifier.hkuros206259-
dc.identifier.volume62-
dc.identifier.issue3-4-
dc.identifier.spage1088en_HK
dc.identifier.epage1111en_HK
dc.identifier.isiWOS:000298852300022-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.citeulike9082454-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats