TY - CONF
T1 - Exploiting Correlated Attributes in Acquisitional Query Processing
T2 - 21st International Conference on Data Engineering, 2005. ICDE 2005. Proceedings
Y1 - 2005
A1 - Deshpande, Amol
A1 - Guestrin,C.
A1 - Wei Hong
A1 - Madden,S.
KW - acquisitional query processing
KW - Computer networks
KW - Costs
KW - data acquisition
KW - Delay
KW - Distributed computing
KW - distributed information system
KW - Distributed information systems
KW - distributed processing
KW - exponential time algorithm
KW - optimization techniques
KW - polynomial-time heuristic
KW - Polynomials
KW - probability
KW - Query processing
KW - real-time systems
KW - real-world sensor-network
KW - Runtime
KW - Sensor phenomena and characterization
KW - Sensor systems
AB - Sensor networks and other distributed information systems (such as the Web) must frequently access data that has a high per-attribute acquisition cost, in terms of energy, latency, or computational resources. When executing queries that contain several predicates over such expensive attributes, we observe that it can be beneficial to use correlations to automatically introduce low-cost attributes whose observation will allow the query processor to better estimate the selectivity of these expensive predicates. In particular, we show how to build conditional plans that branch into one or more sub-plans, each with a different ordering for the expensive query predicates, based on the runtime observation of low-cost attributes. We frame the problem of constructing the optimal conditional plan for a given user query and set of candidate low-cost attributes as an optimization problem. We describe an exponential time algorithm for finding such optimal plans, and describe a polynomial-time heuristic for identifying conditional plans that perform well in practice. We also show how to compactly model conditional probability distributions needed to identify correlations and build these plans. We evaluate our algorithms against several real-world sensor-network data sets, showing several-times performance increases for a variety of queries versus traditional optimization techniques.
JA - 21st International Conference on Data Engineering, 2005. ICDE 2005. Proceedings
PB - IEEE
SN - 0-7695-2285-8
M3 - 10.1109/ICDE.2005.63
ER -