2010 MiningTopKFrequentItemsinaDataS

• (Thanh Lam et al., 2010) ⇒ Hoang Thanh Lam, and Toon Calders. (2010). “Mining Top-k Frequent Items in a Data Stream with Flexible Sliding Windows.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835842

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Mining+top-k+frequent+items+in+a+data+stream+with+flexible+sliding+windows%22+2010
• http://portal.acm.org/citation.cfm?id=1835842&preflayout=flat#citedby

Quotes

Abstract

We study the problem of finding the [math]\displaystyle{ k }[/math] most frequent items in a stream of items for the recently proposed max-frequency measure. Based on the properties of an item, the max-frequency of an item is counted over a sliding window of which the length changes dynamically. Besides being parameterless, this way of measuring the support of items was shown to have the advantage of a faster detection of bursts in a stream, especially if the set of items is heterogeneous. The algorithm that was proposed for maintaining all frequent items, however, scales poorly when the number of items becomes large. Therefore, in this paper we propose, instead of reporting all frequent items, to only mine the top-[math]\displaystyle{ k }[/math] most frequent ones. First we prove that in order to solve this problem exactly, we still need a prohibitive amount of memory (at least linear in the number of items). Yet, under some reasonable conditions, we show both theoretically and empirically that a memory-efficient algorithm exists. A prototype of this algorithm is implemented and we present its performance w.r.t. memory-efficiency on real-life data and in controlled experiments with synthetic data.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 MiningTopKFrequentItemsinaDataS	Hoang Thanh Lam Toon Calders			Mining Top-k Frequent Items in a Data Stream with Flexible Sliding Windows		KDD-2010 Proceedings	http://www.win.tue.nl/~lamthuy/MyPub/sigkdd2010.pdf	10.1145/1835804.1835842		2010