Swarthmore College Department of Computer Science

Talk by Sorelle Friedler, Computer Science Department, Univeristy of Maryland

How Many Birds Are Overhead? Spatio-temporal Range Searching Over Compressed Kinetic Sensor Data
Monday, February 22, 2009
SCI 240, 4:00 pm (cookies at 3:45)

Abstract

How can we use the observations of traffic cameras to find congestion? If we know where fish are, can we identify schools as they move through the ocean? How about the migratory paths of birds? Sensor networks observe and record the motion of objects within their detection region. We introduce a framework for storing and processing the data generated by these moving objects, known as kinetic data. 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.

These sensor networks generate vast quantities of data, which motivates a significant need for data compression. After compressing the data, we present an efficient algorithm for answering spatio-temporal range queries. These queries answer questions like "How many birds are overhead?" or "How many cars have driven through this town in the past hour?" Our algorithm operates on the 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.