Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

An Improved Frequent Items Algorithm with Applications to Web Caching

Kevin Chen and Satish Rao

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-05-1383
2005

http://www.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 k 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},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2005},
    URL = {http://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/2005/5225.html
%F Chen:CSD-05-1383