Whittle Index Policy for Crawling Ephemeral Content - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2015

Whittle Index Policy for Crawling Ephemeral Content

Résumé

We consider a task of scheduling a crawler to retrieve content from several sites with ephemeral content. A user typically loses interest in ephemeral content, like news or posts at social network groups, after several days or hours. Thus, development of timely crawling policy for such ephemeral information sources is very important. We first formulate this problem as an optimal control problem with average reward. The reward can be measured in the number of clicks or relevant search requests. The problem in its initial formulation suffers from the curse of dimensionality and quickly becomes intractable even with moderate number of information sources. Fortunately, this problem admits a Whittle index, which leads to problem decomposition and to a very simple and efficient crawling policy. We derive the Whittle index and provide its theoretical justification.
Fichier principal
Vignette du fichier
RR-8702.pdf (798.21 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01136651 , version 1 (27-03-2015)

Identifiants

Citer

Konstantin Avrachenkov, Vivek S. Borkar. Whittle Index Policy for Crawling Ephemeral Content. [Research Report] RR-8702, Inria Sophia Antipolis; INRIA. 2015. ⟨hal-01136651⟩
223 Consultations
179 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More