File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Finding frequent items in a turnstile data stream

TitleFinding frequent items in a turnstile data stream
Authors
Issue Date2008
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2008, v. 5092 LNCS, p. 498-509 How to Cite?
AbstractBecause of important applications such as denial-of-service attack detection, finding frequent items in data streams under different models has been studied extensively. Finding frequent items in a turnstile data stream is the most challenging because both insertions and deletions of items are allowed in the stream. In this paper, we propose a deterministic algorithm that solves the problem. Furthermore, we propose a randomized algorithm for the problem. Empirical results show that our randomized algorithm provides better results than existing randomized algorithms for the problem and our algorithm uses much smaller space, and supports faster query time and similar update time. © 2008 Springer-Verlag Berlin Heidelberg.
Persistent Identifierhttp://hdl.handle.net/10722/93161
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorHung, RYSen_HK
dc.contributor.authorLai, KFen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-09-25T14:52:45Z-
dc.date.available2010-09-25T14:52:45Z-
dc.date.issued2008en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2008, v. 5092 LNCS, p. 498-509en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93161-
dc.description.abstractBecause of important applications such as denial-of-service attack detection, finding frequent items in data streams under different models has been studied extensively. Finding frequent items in a turnstile data stream is the most challenging because both insertions and deletions of items are allowed in the stream. In this paper, we propose a deterministic algorithm that solves the problem. Furthermore, we propose a randomized algorithm for the problem. Empirical results show that our randomized algorithm provides better results than existing randomized algorithms for the problem and our algorithm uses much smaller space, and supports faster query time and similar update time. © 2008 Springer-Verlag Berlin Heidelberg.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.titleFinding frequent items in a turnstile data streamen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-540-69733-6_49en_HK
dc.identifier.scopuseid_2-s2.0-48249096272en_HK
dc.identifier.hkuros149515en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-48249096272&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume5092 LNCSen_HK
dc.identifier.spage498en_HK
dc.identifier.epage509en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridHung, RYS=14028462000en_HK
dc.identifier.scopusauthoridLai, KF=24481755700en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats