Approximating Sensor Network Queries using In-Network Summaries
by Alexandra Meliou, Carlos Guestrin, Joseph M. Hellerstein
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
Citation:
Alexandra Meliou, Carlos Guestrin, and Joseph M. Hellerstein, Approximating Sensor Network Queries using In-Network Summaries, in Proceedings of the 8th International Conference on Information Processing in Sensor Networks (IPSN), 2009, pp. 229–240.
Bibtex:
@inproceedings{DBLP:conf/ipsn/MeliouGH09,
    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},
    Author = {Alexandra Meliou and Carlos Guestrin and Joseph M. Hellerstein},
    Booktitle = {Proceedings of the 8th International Conference on Information Processing in Sensor Networks (IPSN)},
    Pages = {229-240},
    Title = {\href{http://people.cs.umass.edu/ameli/papers/IPSN2009.pdf}{Approximating Sensor Network Queries using In-Network Summaries}},
    Venue = {IPSN},
    address = {San Francisco, CA},
    month = {April},
    Year = {2009}
}