Cost-Optimal Execution of Boolean Query Trees with Shared Streams

Abstract : The processing of queries expressed as trees of boolean operators applied to predicates on sensor data streams has several applications in mobile computing. Sensor data must be retrieved from the sensors, which incurs a cost, e.g., an energy expense that depletes the battery of a mobile query processing device. The objective is to determine the order in which predicates should be evaluated so as to shortcut part of the query evaluation and minimize the expected cost. This problem has been studied assuming that each data stream occurs at a single predicate. In this work we remove this assumption since it does not necessarily hold for real-world queries. Our main results are an optimal algorithm for single-level trees and a proof of NP-completeness for DNF trees. For DNF trees, however, we show that there is an optimal predicate evaluation order that corresponds to a depth-first traversal. This result provides inspiration for a class of heuristics. We show that one of these heuristics largely outperforms other sensible heuristics, including a heuristic proposed in previous work.
Type de document :
Communication dans un congrès
28th IEEE International Parallel & Distributed Processing Symposium, May 2014, Phoenix, United States. IEEE, 2014
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-00923953
Contributeur : Equipe Roma <>
Soumis le : jeudi 30 janvier 2014 - 13:11:36
Dernière modification le : vendredi 20 avril 2018 - 15:44:26
Document(s) archivé(s) le : samedi 8 avril 2017 - 11:40:20

Fichier

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

Identifiants

  • HAL Id : hal-00923953, version 1

Collections

Citation

Henri Casanova, Lipyeow Lim, Yves Robert, Frédéric Vivien, Dounia Zaidouni. Cost-Optimal Execution of Boolean Query Trees with Shared Streams. 28th IEEE International Parallel & Distributed Processing Symposium, May 2014, Phoenix, United States. IEEE, 2014. 〈hal-00923953〉

Partager

Métriques

Consultations de la notice

527

Téléchargements de fichiers

258