Residential Collegefalse
Status已發表Published
Finding frequent items in time decayed data streams
Wu S.1; Lin H.1; U L.H.2; Gao Y.1; Lu D.1
2016
Conference NameAsia-Pacific Web Conference
Source PublicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9932 LNCS
Pages17-29
Conference Date2016
Conference PlaceSuzhou, China
Abstract

Identifying frequently occurring items is a basic 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 time decay, where the importance of every arrival item is decreased over the time. To address the importance changes over the time, we propose a new heap structure, named Quasiheap, which maintains the item order using a lazy update mechanism. Two approximation algorithms, 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. Extensive experiments demonstrate the superiority of proposed algorithms in terms of both efficiency (i.e., response time) and effectiveness (i.e., accuracy).

KeywordData Stream Hash Function Slide Window Model Streaming Model Frequent Item
DOI10.1007/978-3-319-45817-5_2
URLView the original
Language英語English
Scopus ID2-s2.0-84990070027
Fulltext Access
Citation statistics
Document TypeConference paper
CollectionDEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Faculty of Science and Technology
Affiliation1.Zhejiang University
2.Universidade de Macau
Recommended Citation
GB/T 7714
Wu S.,Lin H.,U L.H.,et al. Finding frequent items in time decayed data streams[C], 2016, 17-29.
APA Wu S.., Lin H.., U L.H.., Gao Y.., & Lu D. (2016). Finding frequent items in time decayed data streams. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9932 LNCS, 17-29.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Wu S.]'s Articles
[Lin H.]'s Articles
[U L.H.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Wu S.]'s Articles
[Lin H.]'s Articles
[U L.H.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Wu S.]'s Articles
[Lin H.]'s Articles
[U L.H.]'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.