File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Maintaining significant stream statistics over sliding windows

TitleMaintaining significant stream statistics over sliding windows
Authors
Issue Date2006
Citation
The 17th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL., 22-24 January 2006. Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2006, p. 724-732 How to Cite?
AbstractIn this paper, we introduce the Significant One Counting problem. Let ε and θ be respectively some user-specified error bound and threshold. The input of the problem is a stream of bits. We need to maintain some data structure that allows us to estimate the number of 1-bits in a sliding window of size n such that whenever there are at least θn 1-bits in the window, the relative error of the estimate is guaranteed to be at most ε. When θ = 1/n, our problem becomes the Basic Counting problem proposed by Datar et al. [ACM-SIAM Symposium on Discrete Algorithms (2002), pp. 635-644]. We prove that any data structure for the Significant One Counting problem must use at least Ω(1/ε log 2 1/θ + log εθn) bits of memory. We also design a data structure for the problem that matches this memory bound and supports constant query and update time. Note that for fixed θ and ε, our data structure uses O(log n) bits of memory, while any data structure for the Basic Counting problem needs Ω(log 2 n) bits in the worst case.
Persistent Identifierhttp://hdl.handle.net/10722/151877
References

 

DC FieldValueLanguage
dc.contributor.authorLee, LKen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2012-06-26T06:30:18Z-
dc.date.available2012-06-26T06:30:18Z-
dc.date.issued2006en_HK
dc.identifier.citationThe 17th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL., 22-24 January 2006. Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2006, p. 724-732en_US
dc.identifier.urihttp://hdl.handle.net/10722/151877-
dc.description.abstractIn this paper, we introduce the Significant One Counting problem. Let ε and θ be respectively some user-specified error bound and threshold. The input of the problem is a stream of bits. We need to maintain some data structure that allows us to estimate the number of 1-bits in a sliding window of size n such that whenever there are at least θn 1-bits in the window, the relative error of the estimate is guaranteed to be at most ε. When θ = 1/n, our problem becomes the Basic Counting problem proposed by Datar et al. [ACM-SIAM Symposium on Discrete Algorithms (2002), pp. 635-644]. We prove that any data structure for the Significant One Counting problem must use at least Ω(1/ε log 2 1/θ + log εθn) bits of memory. We also design a data structure for the problem that matches this memory bound and supports constant query and update time. Note that for fixed θ and ε, our data structure uses O(log n) bits of memory, while any data structure for the Basic Counting problem needs Ω(log 2 n) bits in the worst case.en_HK
dc.languageengen_US
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.titleMaintaining significant stream statistics over sliding windowsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLee, LK: lklee@cs.hku.hken_HK
dc.identifier.emailTing, HF: hfting@cs.hku.hken_HK
dc.identifier.authorityLee, LK=rp00140en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1145/1109557.1109636-
dc.identifier.scopuseid_2-s2.0-33244489178en_HK
dc.identifier.hkuros112582-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33244489178&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage724en_HK
dc.identifier.epage732en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.customcontrol.immutablesml 160111 - merged-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats