-------------------------------------------------------------------------------
                   B O S T O N   U N I V E R S I T Y
                                       
                      Computer Science Department
                                       
                          C O L L O Q U I U M

                  Probabilistic Methods for Web Caching

                          David Starobinski
                    Electrical & Computer Engineering
                          Boston University

   		         Wednesday, October 18
			       3:00 PM 
                       (Coffee served at 2:45PM)
                                       
                         Seminar Room / MCS 135


We introduce and analyze new randomized policies for the management of
web caches. The proposed policies are fully scalable, that is,
handling a hit or an eviction requires only O(1) time. Our analysis is
probabilistic, in nature, and based on an extended version of the IR
model. The extension is needed in order to deal with the varying-cost
and varying-size features of web documents.  Under this assumption, we
derive closed-form expressions for the stationary probabilities of
finding each possible arrangement of the documents within the
cache. Our analysis shows that the performance of the proposed
algorithms are close to that of the optimal off-line algorithm. Using
simulations and real traces, we also show that the new algorithms
perform at least as well as existing algorithms of higher
complexity. Variations on the algorithms, aimed at increasing their
responsiveness to non-stationary trends, are also investigated.

Joint work with David Tse


Host:  John Byers

-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
-------------------------------------------------------------------------------