Alexandra Meliou and Carlos Guestrin and Joseph M. Hellerstein

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2008-137

October 21, 2008

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-137.pdf

In this work we present new in-network techniques for communication-efficient approximate query processing in wireless sensornets. We use a model-based approach that constructs and maintains a spanning tree within the network, rooted at the basestation. 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 problem. 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, and empirically evaluate their performance and sensitivity to model changes.

---

BibTeX citation:

@techreport{Meliou:EECS-2008-137,
    Author= {Meliou, Alexandra and Guestrin, Carlos and Hellerstein, Joseph M.},
    Title= {Approximating Sensor Network Queries with In-Network Summaries},
    Year= {2008},
    Month= {Oct},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-137.html},
    Number= {UCB/EECS-2008-137},
    Abstract= {In this work we present new in-network techniques for communication-efficient approximate query processing in wireless sensornets.
We use a model-based approach that constructs and maintains a spanning tree within the network, rooted at the basestation.  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 problem.  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, and empirically evaluate their performance and sensitivity to model changes.},
}

EndNote citation:

%0 Report
%A Meliou, Alexandra 
%A Guestrin, Carlos 
%A Hellerstein, Joseph M. 
%T Approximating Sensor Network Queries with In-Network Summaries
%I EECS Department, University of California, Berkeley
%D 2008
%8 October 21
%@ UCB/EECS-2008-137
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-137.html
%F Meliou:EECS-2008-137