An integrated efficient solution for computing frequent and top- k elements in data streams
Authors:
Open Access
- 1 September 2006
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 31 (3) , 1095-1133
Abstract
We propose an approximate integrated approach for solving both problems of finding the most popular k elements, and finding frequent elements in a data stream coming from a large domain. Our solution is space efficient and reports both frequent and top- k elements with tight guarantees on errors. For general data distributions, our top- k algorithm returns k elements that have roughly the highest frequencies; and it uses limited space for calculating frequent elements. For realistic Zipfian data, the space requirement of the proposed algorithm for solving the exact frequent elements problem decreases dramatically with the parameter of the distribution; and for top- k queries, the analysis ensures that only the top- k elements, in the correct order, are reported. The experiments, using real and synthetic data sets, show space reductions with hardly any loss in accuracy. Having proved the effectiveness of the proposed approach through both analysis and experiments, we extend it to be able to answer continuous queries about frequent and top- k elements. Although the problems of incremental reporting of frequent and top- k elements are useful in many applications, to the best of our knowledge, no solution has been proposed.Keywords
This publication has 27 references indexed in Scilit:
- Efficient Computation of Frequent and Top-k Elements in Data Streams2004
- Dynamically maintaining frequent items over a data stream2003
- New directions in traffic measurement and accountingACM Transactions on Computer Systems, 2003
- Issues in data stream managementACM SIGMOD Record, 2003
- A simple algorithm for finding frequent elements in streams and bagsACM Transactions on Database Systems, 2003
- Identifying frequent items in sliding windows over on-line packet streams2003
- A linear-time probabilistic counting algorithm for database applicationsACM Transactions on Database Systems, 1990
- Probabilistic counting algorithms for data base applicationsJournal of Computer and System Sciences, 1985
- Finding repeated elementsScience of Computer Programming, 1982
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970