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

This publication is archived. It is kept only for reference purposes, so it is no longer being updated and may not meet accessibility standards. If you need this content in a different format, please email webteam@eecs.berkeley.edu.

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/Archive/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},
    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