Swarthmore College Department of Computer Science

Talk by Sorelle Friedler, Haverford

Understanding Objects in Motion
Wednesday, February 13, 2013
SCI 240, 4:30 pm (cookies at 4:15)

Abstract

What can computer science tell us about the world around us? How can we use techniques from computer science to answer questions from other disciplines and how do questions from other disciplines inform fundamental computer science problems? 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? 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. 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. 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.