Whittle Index Policy for Crawling Ephemeral Content

Abstract : 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.
Type de document :
Rapport
[Research Report] RR-8702, Inria Sophia Antipolis; INRIA. 2015
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01136651
Contributeur : Konstantin Avrachenkov <>
Soumis le : vendredi 27 mars 2015 - 17:05:50
Dernière modification le : dimanche 22 juillet 2018 - 09:10:03
Document(s) archivé(s) le : mardi 18 avril 2017 - 02:26:57

Fichiers

RR-8702.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01136651, version 1
  • ARXIV : 1503.08558

Collections

Citation

Konstantin Avrachenkov, Vivek Borkar. Whittle Index Policy for Crawling Ephemeral Content. [Research Report] RR-8702, Inria Sophia Antipolis; INRIA. 2015. 〈hal-01136651〉

Partager

Métriques

Consultations de la notice

459

Téléchargements de fichiers

131