Skip to Main content Skip to Navigation
Reports

Cost-Optimal Execution of Trees of Boolean Operators 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 to a query processing device, such as a smartphone, over one or more network interfaces. Retrieving a data item incurs a cost, e.g., an energy expense that depletes the smartphone's battery. Since the query tree contains boolean operators, part of the tree can be shortcircuited depending on the retrieved sensor data. An interesting problem is to determine the order in which predicates should be evaluated so as to minimize the expected query processing cost. This problem has been studied in previous work assuming that each data stream occurs in 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 the one heuristic proposed in previous work for our general version of the query processing problem.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-00869340
Contributor : Equipe Roma <>
Submitted on : Friday, October 18, 2013 - 1:36:07 PM
Last modification on : Monday, November 16, 2020 - 9:56:03 AM
Long-term archiving on: : Friday, April 7, 2017 - 1:14:17 PM

File

RR-INRIA-8373.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

346

Files downloads

460