Cost-Optimal Execution of Trees of Boolean Operators with Shared Streams

Résumé : Le traitement de requêtes, exprimées sous forme d'arbres d'opérateurs booléens appliqués à des prédicats sur des flux de données de senseurs, a de nombreuses applications dans le domaine du calcul mobile. Les données doivent être transférées des senseurs vers l'appareil de traitement des données, par exemple un {smartphone}. Transférer une donnée induit un coût, par exemple une consommation énergétique qui diminuera la charge de la batterie du smartphone. Comme l'arbre de requêtes contient des opérateurs booléens, des pans de l'arbre peuvent être court-circuités en fonction des données récupérées. Un problème intéressant est de déterminer l'ordre dans lequel les prédicats doivent être évalués afin de minimiser l'espérance du coût du traitement de la requête. Ce problème a déjà été étudié sous l'hypothèse que chaque flux apparaît dans un seul prédicat. Dans le présent travail nous éliminons cette hypothèse qui ne correspond pas forcément à la réalité. Nos principaux résultats sont un algorithme optimal pour les arbres avec un seul niveau, et une preuve de NP-complétude pour les arbres sous forme normale disjonctive. Pour les arbres sous forme normale disjonctive, cependant, nous montrons qu'il existe un ordre optimal d'évaluation des prédicats qui correspond à un parcours en profondeur d'abord. Ce résultat nous sert à concevoir toute une classe d'heuristiques. Nous montrons que l'une de ces heuristiques a de bien meilleurs résultats que les autres heuristiques et, entre autres, que la seule heuristique précédemment proposée pour le cadre général.
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00869340
Contributeur : Equipe Roma <>
Soumis le : vendredi 18 octobre 2013 - 13:36:07
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : vendredi 7 avril 2017 - 13:14:17

Fichier

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

Identifiants

  • HAL Id : hal-00869340, version 2

Collections

Citation

Henri Casanova, Lipyeow Lim, Yves Robert, Frédéric Vivien, Dounia Zaidouni. Cost-Optimal Execution of Trees of Boolean Operators with Shared Streams. [Research Report] RR-8373, INRIA. 2013, pp.39. 〈hal-00869340v2〉

Partager

Métriques

Consultations de la notice

267

Téléchargements de fichiers

197