Whittle Index Policy for Crawling Ephemeral Content

Abstract : We consider the task of scheduling a crawler to retrieve from several sites their ephemeral content. This is content, such as news or posts at social network groups, for which a user typically loses interest after some days or hours. Thus development of a timely crawling policy for 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 terms of the number of clicks or relevant search requests. The problem in its exact 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, a celebrated heuristics 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 :
Communication dans un congrès
IEEE 54th Annual Conference on Decision and Control (CDC), Dec 2015, Osaka, Japan. 2015, 〈http://www.cdc2015.ctrl.titech.ac.jp/〉
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-01258647
Contributeur : Konstantin Avrachenkov <>
Soumis le : mardi 19 janvier 2016 - 12:23:21
Dernière modification le : samedi 27 janvier 2018 - 01:31:42
Document(s) archivé(s) le : mercredi 20 avril 2016 - 12:20:05

Fichier

CDC15root.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01258647, version 1

Collections

Citation

Konstantin Avrachenkov, Vivek Borkar. Whittle Index Policy for Crawling Ephemeral Content. IEEE 54th Annual Conference on Decision and Control (CDC), Dec 2015, Osaka, Japan. 2015, 〈http://www.cdc2015.ctrl.titech.ac.jp/〉. 〈hal-01258647〉

Partager

Métriques

Consultations de la notice

200

Téléchargements de fichiers

59