Skip to Main content Skip to Navigation
Reports

Cost-Optimal Execution of Boolean DNF Trees with Shared Streams

Abstract : Several applications process queries expressed as trees of Booleanoperators applied to predicates on sensor data streams, e.g., mobile appsand automotive apps. Sensor data must be retrieved from the sensors, whichincurs a cost, e.g., an energy expense that depletes the battery of a mobile device, abandwidth usage. The objective is to determine the order in whichpredicates should be evaluated so as to shortcut part of the queryevaluation and minimize the expected cost. This problem has been studiedassuming that each data stream occurs at a single predicate. In this workwe study the case in which a data stream occurs in multiple predicates,either when each predicate references a single stream or when a predicatecan reference multiple streams. In the single-stream case we give anoptimal algorithm for a single-level tree and show that the problem isNP-complete for DNF trees. For DNF trees we show that there exists an optimal predicate evaluation order that is depth-first, which provides a basis for designinga range of heuristics. In the multi-stream case we show that the problemis NP-complete even for single-level trees. As in the single stream case,for DNF trees we show that there exists a depth-first leaf evaluation order that isoptimal and we design efficient heuristics.
Document type :
Reports
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01079868
Contributor : Equipe Roma <>
Submitted on : Thursday, December 11, 2014 - 8:58:49 PM
Last modification on : Tuesday, November 19, 2019 - 2:41:53 AM
Long-term archiving on: : Thursday, March 12, 2015 - 11:20:59 AM

File

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

Identifiers

  • HAL Id : hal-01079868, version 2

Collections

Citation

Henri Casanova, Lipyeow Lim, Yves Robert, Frédéric Vivien, Dounia Zaidouni. Cost-Optimal Execution of Boolean DNF Trees with Shared Streams. [Research Report] RR-8616, INRIA. 2014. ⟨hal-01079868v2⟩

Share

Metrics

Record views

370

Files downloads

359