File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1145/1109557.1109636
 Scopus: eid_2s2.033244489178
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Maintaining significant stream statistics over sliding windows
Title  Maintaining significant stream statistics over sliding windows 

Authors  
Issue Date  2006 
Citation  The 17th Annual ACMSIAM Symposium on Discrete Algorithms, Miami, FL., 2224 January 2006.
Proceedings Of The Annual AcmSiam Symposium On Discrete Algorithms, 2006, p. 724732 How to Cite? 
Abstract  In this paper, we introduce the Significant One Counting problem. Let ε and θ be respectively some userspecified 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 1bits in a sliding window of size n such that whenever there are at least θn 1bits 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. [ACMSIAM Symposium on Discrete Algorithms (2002), pp. 635644]. 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 Identifier  http://hdl.handle.net/10722/151877 
References 
DC Field  Value  Language 

dc.contributor.author  Lee, LK  en_HK 
dc.contributor.author  Ting, HF  en_HK 
dc.date.accessioned  20120626T06:30:18Z   
dc.date.available  20120626T06:30:18Z   
dc.date.issued  2006  en_HK 
dc.identifier.citation  The 17th Annual ACMSIAM Symposium on Discrete Algorithms, Miami, FL., 2224 January 2006. Proceedings Of The Annual AcmSiam Symposium On Discrete Algorithms, 2006, p. 724732  en_US 
dc.identifier.uri  http://hdl.handle.net/10722/151877   
dc.description.abstract  In this paper, we introduce the Significant One Counting problem. Let ε and θ be respectively some userspecified 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 1bits in a sliding window of size n such that whenever there are at least θn 1bits 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. [ACMSIAM Symposium on Discrete Algorithms (2002), pp. 635644]. 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.language  eng  en_US 
dc.relation.ispartof  Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms  en_HK 
dc.title  Maintaining significant stream statistics over sliding windows  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.email  Lee, LK: lklee@cs.hku.hk  en_HK 
dc.identifier.email  Ting, HF: hfting@cs.hku.hk  en_HK 
dc.identifier.authority  Lee, LK=rp00140  en_HK 
dc.identifier.authority  Ting, HF=rp00177  en_HK 
dc.description.nature  link_to_subscribed_fulltext  en_US 
dc.identifier.doi  10.1145/1109557.1109636   
dc.identifier.scopus  eid_2s2.033244489178  en_HK 
dc.identifier.hkuros  112582   
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.033244489178&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.spage  724  en_HK 
dc.identifier.epage  732  en_HK 
dc.identifier.scopusauthorid  Lee, LK=12646190100  en_HK 
dc.identifier.scopusauthorid  Ting, HF=7005654198  en_HK 
dc.customcontrol.immutable  sml 160111  merged   