Spatio-temporal Range Searching Over Compressed Kinetic Sensor Data
Spatio-temporal Range Searching Over Compressed Kinetic Sensor Data
Files
Publication or External Link
Date
2010-06-09
Authors
Friedler, Sorelle A.
Mount, David M.
Advisor
Citation
DRUM DOI
Abstract
As sensor networks increase in size and number, efficient techniques are
required to process the very large data sets that they generate.
Frequently, sensor networks monitor objects in motion within their
vicinity; the data associated with the movement of these objects are
known as kinetic data. In an earlier paper we introduced an algorithm
which, given a set of sensor observations, losslessly compresses these
data to a size that is within a constant factor of the asymptotically
optimal joint entropy bound. In this paper we 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 a
natural measure of information content, the joint entropy of the sensor
outputs. We show that with space roughly equal to joint entropy,
queries can be answered in time that is roughly logarithmic in joint
entropy. In addition, we show experimentally that on real-world data our
range searching structures use less space and have faster query times
than the naive versions. These results represent the first solutions to
range searching problems over compressed kinetic sensor data.