DocumentCode :
1783185
Title :
Cost-Optimal Execution of Boolean Query Trees with Shared Streams
Author :
Casanova, H. ; Lipyeow Lim ; Robert, Yannick ; Vivien, F. ; Zaidouni, Dounia
Author_Institution :
Univ. of Hawai`i at Manoa, Honolulu, HI, USA
fYear :
2014
fDate :
19-23 May 2014
Firstpage :
7
Lastpage :
16
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 in practice. 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.
Keywords :
Boolean functions; computational complexity; data handling; mobile computing; query processing; tree data structures; Boolean operator trees; Boolean query trees; DNF trees; NP-completeness proof; cost-optimal execution; expected cost minimization; heuristics; mobile computing; mobile query processing device; optimal algorithm; optimal predicate evaluation; query evaluation; sensor data retrieval; sensor data streams; shared streams; single-level trees; Accelerometers; Batteries; Complexity theory; Optimized production technology; Query processing; Schedules; Smart phones;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing Symposium, 2014 IEEE 28th International
Conference_Location :
Phoenix, AZ
ISSN :
1530-2075
Print_ISBN :
978-1-4799-3799-8
Type :
conf
DOI :
10.1109/IPDPS.2014.13
Filename :
6877237
Link To Document :
بازگشت