UM  > 科技學院  > 電腦及資訊科學系
Novel structures for counting frequent items in time decayed streams
Wu, Shanshan1; Lin, Huaizhong1; Hou, Leong U.2; Gao, Yunjun1; Lu, Dongming1
2017-09
Source PublicationWORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS
ISSN1386-145X
Volume20Issue:5Pages:1111-1133
Abstract

Identifying frequently occurring items is a fundamental building block in many data stream applications. A great deal of work for efficiently identifying frequent items has been studied on the landmark and sliding window models. In this work, we revisit this problem on a new streaming model based on the time decay, where the importance of every arrival item is decreased over the time. To address the importance changes over time, we propose an innovative heap structure, named Quasi-heap, which maintains the item order using a lazy update mechanism. Two approximation algorithm, Space Saving with Quasi-heap (SSQ) and Filtered Space Saving with Quasi-heap (FSSQ), are proposed to find the frequently occurring items based on the Quasi-heap structure. To achieve better accuracy of frequency estimation for all the items in the stream, we introduce a new count-min-min (CMM) sketch structure, which can estimate the count of an item with almost error free. Extensive experiments conducted on both real-world and synthetic data demonstrate the superiority of proposed methods in terms of both efficiency (i.e., response time) and effectiveness (i.e., accuracy).

KeywordFrequent Item Data Stream Time Decay Model Data Structure
DOI10.1007/s11280-017-0433-5
URLView the original
Indexed BySCI
Language英语
WOS Research AreaComputer Science
WOS SubjectComputer Science, Information Systems ; Computer Science, Software Engineering
WOS IDWOS:000402177100011
PublisherSPRINGER
The Source to ArticleWOS
Fulltext Access
Citation statistics
Cited Times [WOS]:6   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionDEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Affiliation1.Zhejiang Univ, Coll Comp Sci & Technol, Hangzhou, Zhejiang, Peoples R China
2.Univ Macau, Fac Sci & Technol, Macau, Peoples R China
Recommended Citation
GB/T 7714
Wu, Shanshan,Lin, Huaizhong,Hou, Leong U.,et al. Novel structures for counting frequent items in time decayed streams[J]. WORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS,2017,20(5):1111-1133.
APA Wu, Shanshan,Lin, Huaizhong,Hou, Leong U.,Gao, Yunjun,&Lu, Dongming.(2017).Novel structures for counting frequent items in time decayed streams.WORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS,20(5),1111-1133.
MLA Wu, Shanshan,et al."Novel structures for counting frequent items in time decayed streams".WORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS 20.5(2017):1111-1133.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Wu, Shanshan]'s Articles
[Lin, Huaizhong]'s Articles
[Hou, Leong U.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Wu, Shanshan]'s Articles
[Lin, Huaizhong]'s Articles
[Hou, Leong U.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Wu, Shanshan]'s Articles
[Lin, Huaizhong]'s Articles
[Hou, Leong U.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.