File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: 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 streams
Frequent items
Sliding window
Space complexity
Issue Date2011
PublisherMDPIAG. The Journal's web site is located at http://www.mdpi.com/journal/algorithms
Citation
Algorithms, 2011, v. 4 n. 3, p. 200-222 How to Cite?
AbstractIn an asynchronous data stream, the data items may be out of order with respect to their original timestamps. This paper studies the space complexity required by a data structure to maintain such a data stream so that it can approximate the set of frequent items over a sliding time window with sufficient accuracy. Prior to our work, the best solution is given by Cormode et al. [1], who gave an O (1/∈ logW log(∈B/logW) min{logW; 1/∈} log |U|) -space data structure that can approximate the frequent items within an ∈ error bound, where W and B are parameters of the sliding window, and U is the set of all possible item names. We gave a more space-efficient data structure that only requires O (1/∈log W log(∈B/logW) log logW) space. © 2011 by the authors.
Persistent Identifierhttp://hdl.handle.net/10722/152499
ISSN
2015 SCImago Journal Rankings: 0.357
References

 

DC FieldValueLanguage
dc.contributor.authorTing, HFen_HK
dc.contributor.authorLee, LKen_HK
dc.contributor.authorChan, HLen_HK
dc.contributor.authorLam, TWen_HK
dc.date.accessioned2012-06-26T06:39:43Z-
dc.date.available2012-06-26T06:39:43Z-
dc.date.issued2011en_HK
dc.identifier.citationAlgorithms, 2011, v. 4 n. 3, p. 200-222en_HK
dc.identifier.issn1999-4893en_HK
dc.identifier.urihttp://hdl.handle.net/10722/152499-
dc.description.abstractIn an asynchronous data stream, the data items may be out of order with respect to their original timestamps. This paper studies the space complexity required by a data structure to maintain such a data stream so that it can approximate the set of frequent items over a sliding time window with sufficient accuracy. Prior to our work, the best solution is given by Cormode et al. [1], who gave an O (1/∈ logW log(∈B/logW) min{logW; 1/∈} log |U|) -space data structure that can approximate the frequent items within an ∈ error bound, where W and B are parameters of the sliding window, and U is the set of all possible item names. We gave a more space-efficient data structure that only requires O (1/∈log W log(∈B/logW) log logW) space. © 2011 by the authors.en_HK
dc.languageengen_US
dc.publisherMDPIAG. The Journal's web site is located at http://www.mdpi.com/journal/algorithmsen_HK
dc.relation.ispartofAlgorithmsen_HK
dc.subjectAsynchronous data streamsen_HK
dc.subjectFrequent itemsen_HK
dc.subjectSliding windowen_HK
dc.subjectSpace complexityen_HK
dc.titleApproximating frequent items in asynchronous data stream over a sliding windowen_HK
dc.typeArticleen_HK
dc.identifier.emailTing, HF: hfting@cs.hku.hken_HK
dc.identifier.emailLee, LK: lklee@cs.hku.hken_HK
dc.identifier.emailLam, TW: hresltk@hkucc.hku.hken_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.identifier.authorityLee, LK=rp00140en_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_OA_fulltexten_US
dc.identifier.doi10.3390/a4030200en_HK
dc.identifier.scopuseid_2-s2.0-84859517427en_HK
dc.identifier.hkuros210479-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-84859517427&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume4en_HK
dc.identifier.issue3en_HK
dc.identifier.spage200en_HK
dc.identifier.epage222en_HK
dc.publisher.placeSwitzerlanden_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.scopusauthoridChan, HL=55171146200en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats