Querying Uncertain Data in Resource Constrained Settings
by Alexandra Meliou
Abstract:
Sensor networks are progressively becoming a standard in applications that require the monitoring of physical phenomena. Measurements like temperature, humidity, light, and acceleration are gathered at various locations and can be used to extract information on the phenomenon observed. Sensor networks are naturally distributed, and they display strong resource restrictions. Moreover, the gathered data comes in various degrees of uncertainty, due to noisy and dropped measurements, interference, and the unavoidable discretization of the examined domain. A basic task in sensor networks is to interactively gather data from a subset of nodes in the network. Surprisingly, this problem is non-trivial to implement efficiently and robustly, even for relatively static networks. In this thesis we address the traditional database problem of query optimization in this new setting. We identify the characteristics of sensor network environments and the requirements of applications that are relevant to querying. We focus on making queries more energy efficient by means of minimizing the communication and sensing that is required to provide sufficient answers. Our contributions include theoretical, algorithmic and empirical results. We provide complexity analysis for common data gathering tasks, develop algorithms that approximate the optimal query plans, and apply our techniques to a prototype implementation that tests our theory and algorithms over real world data, demonstrating the feasibility of our approach.
Citation:
Alexandra Meliou, Querying Uncertain Data in Resource Constrained Settings, Ph.D. dissertation, University of California, Berkeley, Berkeley, CA, 2009.
Bibtex:
@phdthesis{Meliou-phd,
    Abstract = {Sensor networks are progressively becoming a standard in
    applications that require the monitoring of physical phenomena.
    Measurements like temperature, humidity, light, and acceleration are
    gathered at various locations and can be used to extract information on
    the phenomenon observed. Sensor networks are naturally distributed, and
    they display strong resource restrictions. Moreover, the gathered data
    comes in various degrees of uncertainty, due to noisy and dropped
    measurements, interference, and the unavoidable discretization of the
    examined domain. A basic task in sensor networks is to interactively
    gather data from a subset of nodes in the network. Surprisingly, this
    problem is non-trivial to implement efficiently and robustly, even for
    relatively static networks.

    In this thesis we address the traditional database problem of query
    optimization in this new setting. We identify the characteristics of
    sensor network environments and the requirements of applications that are
    relevant to querying. We focus on making queries more energy efficient by
    means of minimizing the communication and sensing that is required to
    provide sufficient answers. Our contributions include theoretical,
    algorithmic and empirical results. We provide complexity analysis for
    common data gathering tasks, develop algorithms that approximate the
    optimal query plans, and apply our techniques to a prototype
    implementation that tests our theory and algorithms over real world data,
    demonstrating the feasibility of our approach. },
    Author = {Meliou, Alexandra},
    School = {University of California, Berkeley},
    Title = {\href{http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-144.html}{Querying Uncertain Data in Resource Constrained Settings}},
    Venue = {PhD},
    address = {Berkeley, CA},
    month = dec,
    Year = {2009}
}