University of Maryland DRUM  
University of Maryland Digital Repository at the University of Maryland

Digital Repository at the University of Maryland (DRUM) >
College of Computer, Mathematical & Natural Sciences >
Computer Science >
Technical Reports of the Computer Science Department >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1903/10057

Title: Compressing Kinetic Data From Sensor Networks
Authors: Friedler, Sorelle A.
Mount, David M.
Type: Technical Report
Issue Date: 14-Sep-2009
Series/Report no.: UM Computer Science Department;CS-TR-4941
Abstract: We introduce a framework for storing and processing kinetic data observed by sensor networks. 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. In order to justify our locality assumptions, we provide a theoretical comparison with a variant of the kinetic data structures framework. We prove that the storage size required by an optimal system operating under our locality assumptions is on the order of the size required by our variant. Additionally, we provide experimental justification for our locality assumptions.
URI: http://hdl.handle.net/1903/10057
Appears in Collections:Technical Reports of the Computer Science Department

Files in This Item:

File Description SizeFormatNo. of Downloads
framework.pdf409.29 kBAdobe PDF325View/Open

All items in DRUM are protected by copyright, with all rights reserved.

 

DRUM is brought to you by the University of Maryland Libraries
University of Maryland, College Park, MD 20742-7011 (301)314-1328.
Please send us your comments