Residential College | false |
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 Name | Asia-Pacific Web Conference |
Source Publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
Volume | 9932 LNCS |
Pages | 17-29 |
Conference Date | 2016 |
Conference Place | Suzhou, 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). |
Keyword | Data Stream Hash Function Slide Window Model Streaming Model Frequent Item |
DOI | 10.1007/978-3-319-45817-5_2 |
URL | View the original |
Language | 英語English |
Scopus ID | 2-s2.0-84990070027 |
Fulltext Access | |
Citation statistics | |
Document Type | Conference paper |
Collection | DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE Faculty of Science and Technology |
Affiliation | 1.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. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment