Proportional vs. Uniform

policy for CQs

*Assumption :* *Update distribution* is uniform.

We compare weighted *Uniform* and weighted
*Proportional* policies.

As we knowNumber of crawls allocated toi^{th}pagein the proportional policy is

whereW_{i}and are weight and change frequency ofi^{th}page

respectively.

So Information gained for this page is equal to

where is the update probability fori^{th}page at any update instant.

Information gained in case of the uniform allocation for the same page

is equal to

So ratio of performance of the proportion to the uniform policy over all

pages becomes

This proves that

Sandeep Pandey 2003-03-05