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/10201

Title: Spatio-temporal Range Searching Over Compressed Kinetic Sensor Data
Authors: Friedler, Sorelle A.
Mount, David M.
Type: Technical Report
Issue Date: 9-Jun-2010
Series/Report no.: UM Computer Science Department;CS-TR-4960
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.
URI: http://hdl.handle.net/1903/10201
Appears in Collections:Technical Reports of the Computer Science Department

Files in This Item:

File Description SizeFormatNo. of Downloads
CS-TR-4960.pdf331.93 kBAdobe PDF214View/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