Proportional vs. Uniform
policy for CQs
Assumption : Update distribution is uniform.
We compare weighted Uniform and weighted Proportional policies.
Number of crawls allocated to ith pagein the proportional policy isAs we know ai.bi (ai.bi) for non-negative ai's and bi's, above ratio is always greater than 1.
where Wi and are weight and change frequency of ith page
So Information gained for this page is equal to
where is the update probability for ith 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
This proves that Proportional always performs better than Uniform no matter how page weights and change frequencies are distributed.
Sandeep Pandey 2003-03-05