Select Lab Publications


Approximating Sensor Network Queries Using In-Network Summaries (2009)

By: Alexandra Meliou, Carlos Guestrin, and Joseph M. Hellerstein

Abstract: In this work we present new in-network techniques for communication efficient approximate query processing in wireless s ensornets. We use a model-based approach that constructs and maintains a spanning tree within the network, rooted at the basestatio n. The tree maintains compressed summary information for each link that is used to ``stub out'' traversal during query processing. Our work is based on a formal model of the in-network tree construction task framed as an optimization prob lem. We demonstrate hardness results for that problem, and develop efficient approximation algorithms for subtasks that are too expensive to compute exactly. We also propose efficient heuristics to accommodate a wider set of workloads, an d empirically evaluate their performance and sensitivity to model changes.

Download Information
Alexandra Meliou, Carlos Guestrin, and Joseph M. Hellerstein (2009). "Approximating Sensor Network Queries Using In-Network Summaries." Information Processing in Sensor Networks (IPSN). pdf   talk      
BibTeX citation

@inproceedings{meliou+al:ipsn09,
AUTHOR = {Alexandra Meliou and Carlos Guestrin and Joseph M. Hellerstein},
TITLE = {Approximating Sensor Network Queries Using In-Network
Summaries},
BOOKTITLE = {Information Processing in Sensor Networks (IPSN)},
YEAR = {2009},
month = {April},
wwwfilebase = {ipsn2009-meliou-guestrin-hellerstein},
wwwtopic = {Sensing}
}



full list