HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Optimal Robot Scheduling for Web Search Engines

Abstract : A robot is deployed by a Web search engine in order to maintain the currency of its data base of Web pages. This paper studies robot scheduling policies that minimize the fractions $r_i$ of time pages spend out-of-date, assuming independent Poisson page-change processes, and a general distribution for the page access time $X$. We show that, if $X$ is decreased in the increasing-convex ordering sense, then $r_i$ is decreased for all $i$ under any scheduling policy, and that, in order to minimize expected total obsolescence time of any page, the accesses to that page should be as evenly spaced in time as possible. We then investigate the problem of scheduling to minimize the cost function $\sum c_i r_i,$ where the $c_i$ are given weights proportional to the page-change rates $\mu_i$. We give a tight bound on the performance of such a policy and prove that the optimal frequency at which the robot should access page $i$ is proportional to $\ln (h_i)^{-1}$, where $h_i := {\rm E}e^{-\mu_iX}.$ Note that this reduces to being proportional to $\mu_i$ when $X$ is a constant, but not, as one might expect, when $X$ has a general distribution. Next, we evaluate randomized accessing policies whereby the choices of page access are determined by independent random samples from the distribution ${f_i}$. We show that when the weights $c_i$ in the cost function are proportional to $\mu_i$, the minimum cost is achieved when $f_i$ is proportional to $(h_i)^{-1} - 1$. Finally, we present and analyze a heuristic policy that is especially suited to the asymptotic regime of large data bases.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 12:38:52 PM
Last modification on : Wednesday, April 6, 2022 - 3:48:18 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:44:17 PM


  • HAL Id : inria-00073372, version 1



E. G. Coffman, Zhen Liu, Richard R. Weber. Optimal Robot Scheduling for Web Search Engines. RR-3317, INRIA. 1997. ⟨inria-00073372⟩



Record views


Files downloads