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