Kevin Chen and Satish Rao

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-05-1383

, 2005

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1383.pdf

We present a simple, intuitive algorithm for the problem of finding an approximate list of the <i>k</i> most frequent items in a data stream when the item frequencies are Zipf-distributed. Our result improves the previous result of Charikar, Chen and Farach-Colton for the same problem when the Zipf parameter is low. We also highlight an application of the algorithm to web caching that may be of practical interest.

---

BibTeX citation:

@techreport{Chen:CSD-05-1383,
    Author= {Chen, Kevin and Rao, Satish},
    Title= {An Improved Frequent Items Algorithm with Applications to Web Caching},
    Year= {2005},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5225.html},
    Number= {UCB/CSD-05-1383},
    Abstract= {We present a simple, intuitive algorithm for the problem of finding an approximate list of the <i>k</i> most frequent items in a data stream when the item frequencies are Zipf-distributed. Our result improves the previous result of Charikar, Chen and Farach-Colton for the same problem when the Zipf parameter is low. We also highlight an application of the algorithm to web caching that may be of practical interest.},
}

EndNote citation:

%0 Report
%A Chen, Kevin 
%A Rao, Satish 
%T An Improved Frequent Items Algorithm with Applications to Web Caching
%I EECS Department, University of California, Berkeley
%D 2005
%@ UCB/CSD-05-1383
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/5225.html
%F Chen:CSD-05-1383