A sensor-based framework for kinetic data compression

• Published in: Computational geometry : theory and applications 2015-03, Vol.48 (3), p.147-168
• Main Authors: Friedler, Sorelle A., Mount, David M.
• Format: Article
• Language: English
• Subjects: Algorithms; Constants; Data compression; Empirical analysis; Entropy; Information theory; Kinetic data; Lossless compression; Networks; Sensor data; Sensors; Streams
• ISSN: 0925-7721
• DOI: 10.1016/j.comgeo.2014.09.002

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 streams 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 streams are statistically dependent only if the two sensors are among the m 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 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 and experimental results demonstrating the existence of such locality properties in real-world data. We also give a relaxed version of our sensor stream independence property where even distant sensor streams are allowed some limited dependence. We extend the current understanding of empirical entropy to introduce definitions for joint empirical entropy, conditional empirical entropy, and empirical independence. We show that, even with the notion of limited independence and in both the statistical and empirical settings, the introduced compression algorithm achieves an encoding size that is within a constant factor of the optimal.