Paper Info
Title
Finding top-k elements in a time-sliding window.
Abstract
Identifying the top-k most frequent elements is one of the many problems associated with data streams analysis. It is a well-known and difficult problem, especially if the analysis is to be performed and maintained up to date in near real time. Analyzing data streams in time sliding window model is of particular interest as only the most recent, more relevant events are considered. Approximate answers are usually adequate when dealing with this problem. This paper presents a new and innovative algorithm, the Filtered Space-Saving with Sliding Window Algorithm (FSW) that addresses this problem by introducing in the Filtered Space Saving (FSS) algorithm an approximated time sliding window counter. The algorithm provides the top-k list of elements, their frequency and an error estimate for each frequency value within the sliding window. It provides strong guarantees on the results, depending on the elements real frequencies. Experimental results detail performance on real life cases.
Year
DOI
Venue
2011
10.1007/s12530-010-9020-z
Evolving Systems
Keywords
Field
DocType
near real time,sliding window
Data mining,Data stream mining,Sliding window protocol,Computer science,Algorithm
Journal
Volume
Issue
ISSN
2
1
1868-6486
Citations 
PageRank 
References 
12
0.70
23
Authors
2
Name
Order
Citations
PageRank
Nuno HomemJoao1433.08
João Paulo Carvalho211017.52