Campus Event Calendar
Event Entry
What and Who
A Sensor-Based Framework for Kinetic Data
Sorelle Friedler
University of Maryland
SWS Colloquium
Sorelle Friedler is a Ph.D. candidate in the Department of Computer
Science at the University of Maryland. She received her M.S. from the
University of Maryland in 2007 and her B.A. from Swarthmore College in
2004. Her main research interest is on algorithms for geometric problems
and she is currently interested in creating algorithms for calculating
statistical properties of moving points. Other research interests include
linear programming, programming languages, and computational analysis of
educational data. She is the recipient of numerous awards, including the
AT&T Labs Fellowship, awarded yearly to 5 graudate students chosen from a
US national pool.
SWS, RG1
Expert Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 2 February 2010
14:00
60 Minutes
E1 5
5th floor
Saarbrücken
Abstract
We introduce a framework for storing and processing kinetic data observed
by sensor networks, such as highway traffic or migratory birds. These
sensor networks generate vast quantities of data, which motivates a
significant need for data compression. We are given a set of sensors,
each of which continuously monitors some region of space. We are
interested in the kinetic data generated by a finite set of objects moving
through space, as observed by these sensors. Our model relies purely on
sensor observations; it allows points to move freely and requires no
advance notification of motion plans. Sensor outputs are represented as
random processes, where nearby sensors may be statistically dependent. We
model the local nature of sensor networks by assuming that two sensor
outputs are statistically dependent only if the two sensors are among the
k nearest neighbors of each other. We present an algorithm for the
lossless compression of the data produced by the network. We show that,
under the statistical dependence and locality assumptions of our
framework, asymptotically this compression algorithm encodes the data to
within a constant factor of the information-theoretic lower bound optimum
dictated by the joint entropy of the system.
We also present an efficient algorithm for answering spatio-temporal range
queries. Our algorithm operates on a compressed representation of the
data, without the need to decompress it. We analyze the efficiency of our
algorithm in terms of two natural measures of information content, the
statistical and empirical joint entropies of the sensor outputs. We show
that with space roughly equal to entropy, queries can be answered in time
that is roughly logarithmic in entropy. These results represent the first
solution to range searching problems over compressed kinetic sensor data
and set the stage for future statistical analysis.
This is joint work with David Mount.
by sensor networks, such as highway traffic or migratory birds. These
sensor networks generate vast quantities of data, which motivates a
significant need for data compression. We are given a set of sensors,
each of which continuously monitors some region of space. We are
interested in the kinetic data generated by a finite set of objects moving
through space, as observed by these sensors. Our model relies purely on
sensor observations; it allows points to move freely and requires no
advance notification of motion plans. Sensor outputs are represented as
random processes, where nearby sensors may be statistically dependent. We
model the local nature of sensor networks by assuming that two sensor
outputs are statistically dependent only if the two sensors are among the
k nearest neighbors of each other. We present an algorithm for the
lossless compression of the data produced by the network. We show that,
under the statistical dependence and locality assumptions of our
framework, asymptotically this compression algorithm encodes the data to
within a constant factor of the information-theoretic lower bound optimum
dictated by the joint entropy of the system.
We also present an efficient algorithm for answering spatio-temporal range
queries. Our algorithm operates on a compressed representation of the
data, without the need to decompress it. We analyze the efficiency of our
algorithm in terms of two natural measures of information content, the
statistical and empirical joint entropies of the sensor outputs. We show
that with space roughly equal to entropy, queries can be answered in time
that is roughly logarithmic in entropy. These results represent the first
solution to range searching problems over compressed kinetic sensor data
and set the stage for future statistical analysis.
This is joint work with David Mount.
Contact
Bettina Peden-Bennett
0631-9303-9602
--email hidden
Video Broadcast
Yes
Kaiserslautern
G26
206
passcode not visible
logged in users only
Rose Hoberman, 05/07/2010 14:45
Uwe Brahm, 02/18/2010 16:18
Bettina Peden-Bennett, 02/09/2010 11:49 -- Created document.
Uwe Brahm, 02/18/2010 16:18
Bettina Peden-Bennett, 02/09/2010 11:49 -- Created document.