Proportional vs. Uniform policy for CQs


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 is

$ {\frac{C.W_i.\lambda_i}{\sum_i{(W_i.\lambda_i)}}}$
where Wi and $ \lambda_{i}^{}$ are weight and change frequency of ith page
respectively.
So Information gained for this page is equal to
$ {\frac{C.{W_i}^2.\lambda_i.\rho_i}{\sum_i{(W_i.\lambda_i)}}}$
where $ \rho_{i}^{}$ 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
$ {\frac{C.{W_i}^2.\rho_i}{\sum_i{W_i}}}$
So ratio of performance of the proportion to the uniform policy over all
pages becomes
$ {\frac{\sum_i{\lambda_i}.\sum_i{W_i}}{\sum_i{(W_i.\lambda_i)}}}$
As we know $ \sum_{i}^{}$ai.$ \sum_{i}^{}$bi $ \geq$ $ \sum_{i}^{}$(ai.bi) for non-negative ai's and bi's, above ratio is always greater than 1.
This proves that Proportional always performs better than Uniform no matter how page weights and change frequencies are distributed.



Sandeep Pandey 2003-03-05