File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: A simpler and more efficient deterministic scheme for finding frequent items over sliding windows

TitleA simpler and more efficient deterministic scheme for finding frequent items over sliding windows
Authors
Lee, LKTing, HF
KeywordsData mining
Frequent items
Network monitoring
Streaming algorithms
Issue Date2006
PublisherSpringer.
Citation
Proceedings Of The Acm Sigact-Sigmod-Sigart Symposium On Principles Of Database Systems, 2006, p. 290-297 How to Cite?
DOI: http://dx.doi.org/10.1145/1142351.1142393
AbstractIn this paper, we give a simple scheme for identifying ε-approximate frequent items over a sliding window of size n. Our scheme is deterministic and does not make any assumption on the distribution of the item frequencies. It supports O(1/ε) update and query time, and uses O(1/ε) space. It is very simple; its main data structures are just a few short queues whose entries store the position of some items in the sliding window. We also extend our scheme for variable-size window. This extended scheme uses O(1/ε log(εn)) space. Copyright 2006 ACM.
Persistent Identifierhttp://hdl.handle.net/10722/93086
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorLee, LKen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-09-25T14:50:28Z-
dc.date.available2010-09-25T14:50:28Z-
dc.date.issued2006en_HK
dc.identifier.citationProceedings Of The Acm Sigact-Sigmod-Sigart Symposium On Principles Of Database Systems, 2006, p. 290-297en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93086-
dc.description.abstractIn this paper, we give a simple scheme for identifying ε-approximate frequent items over a sliding window of size n. Our scheme is deterministic and does not make any assumption on the distribution of the item frequencies. It supports O(1/ε) update and query time, and uses O(1/ε) space. It is very simple; its main data structures are just a few short queues whose entries store the position of some items in the sliding window. We also extend our scheme for variable-size window. This extended scheme uses O(1/ε log(εn)) space. Copyright 2006 ACM.en_HK
dc.languageengen_HK
dc.publisherSpringer.en_HK
dc.relation.ispartofProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systemsen_HK
dc.subjectData miningen_HK
dc.subjectFrequent itemsen_HK
dc.subjectNetwork monitoringen_HK
dc.subjectStreaming algorithmsen_HK
dc.titleA simpler and more efficient deterministic scheme for finding frequent items 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_fulltext-
dc.identifier.doi10.1145/1142351.1142393en_HK
dc.identifier.scopuseid_2-s2.0-34250676594en_HK
dc.identifier.hkuros123196en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-34250676594&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage290en_HK
dc.identifier.epage297en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats