File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Finding frequent items over sliding windows with constant update time

TitleFinding frequent items over sliding windows with constant update time
Authors
Hung, RYSLee, LKTing, HF
KeywordsApproximation algorithms
On-line algorithms
Issue Date2010
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl
Citation
Information Processing Letters, 2010, v. 110 n. 7, p. 257-260 How to Cite?
DOI: http://dx.doi.org/10.1016/j.ipl.2009.01.027
AbstractIn this paper, we consider the problem of finding ε{lunate}-approximate frequent items over a sliding window of size N. A recent work by Lee and Ting (2006) [7] solves the problem by giving an algorithm that supports O (frac(1, ε{lunate})) query and update time, and uses O (frac(1, ε{lunate})) space. Their query time and memory usage are essentially optimal, but the update time is not. We give a new algorithm that supports O (1) update time with high probability while maintaining the query time and memory usage as O (frac(1, ε{lunate})). © 2010 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/127355
ISSN
0020-0190
2023 Impact Factor: 0.7
2023 SCImago Journal Rankings: 0.404
ISI Accession Number ID
WOS:000275923700004
Funding AgencyGrant Number
Hong Kong RGCHKU-7163/07E
Funding Information:

This research was supported in part by Hong Kong RGC Grant HKU-7163/07E.

References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorHung, RYSen_HK
dc.contributor.authorLee, LKen_HK
dc.contributor.authorTing, HFen_HK
dc.date.accessioned2010-10-31T13:20:45Z-
dc.date.available2010-10-31T13:20:45Z-
dc.date.issued2010en_HK
dc.identifier.citationInformation Processing Letters, 2010, v. 110 n. 7, p. 257-260en_HK
dc.identifier.issn0020-0190en_HK
dc.identifier.urihttp://hdl.handle.net/10722/127355-
dc.description.abstractIn this paper, we consider the problem of finding ε{lunate}-approximate frequent items over a sliding window of size N. A recent work by Lee and Ting (2006) [7] solves the problem by giving an algorithm that supports O (frac(1, ε{lunate})) query and update time, and uses O (frac(1, ε{lunate})) space. Their query time and memory usage are essentially optimal, but the update time is not. We give a new algorithm that supports O (1) update time with high probability while maintaining the query time and memory usage as O (frac(1, ε{lunate})). © 2010 Elsevier B.V. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/iplen_HK
dc.relation.ispartofInformation Processing Lettersen_HK
dc.subjectApproximation algorithmsen_HK
dc.subjectOn-line algorithmsen_HK
dc.titleFinding frequent items over sliding windows with constant update timeen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0020-0190&volume=110&issue=7&spage=257&epage=260&date=2010&atitle=Finding+frequent+items+over+sliding+windows+with+constant+update+timeen_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.1016/j.ipl.2009.01.027en_HK
dc.identifier.scopuseid_2-s2.0-76849084439en_HK
dc.identifier.hkuros178821en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-76849084439&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume110en_HK
dc.identifier.issue7en_HK
dc.identifier.spage257en_HK
dc.identifier.epage260en_HK
dc.identifier.isiWOS:000275923700004-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridHung, RYS=14028462000en_HK
dc.identifier.scopusauthoridLee, LK=12646190100en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.citeulike6832013-
dc.identifier.issnl0020-0190-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats