Indexing the Positions of Continuously Moving Objects

Simonas Saltenis and Christian Jenson and Scott Leutenegger and Mario Lopez

Back to index

Summary

Tracking wireless devices as they roam across networks, this paper describes the R* algorithm. The R* algorithm is a tree based indexing technique that supports efficient querying and updating of objects dynamically as they move through the system. Since the DARPA Grandchallenge does not exist in a network where the vehicle can transmit is current velocity and positional information, this paper is largely unrelated yet still algorithmically interesting.

Methods

The technique is simple: instead of storing positions, store functions that represent the object's position with respect to time, and update only the parameters when the object's motion changes. The index is maintained through a time-parameterized R-tree, which is adjusted to R*-tree for spatial data. A buckloading algorithm is provided for building and updating the index. Objects only report in when their velocity vectors change from their previously reported position, within a certain error margin. Querying is based on the current time index, applying the parameters to the function to gather the object's current position.

Keywords

R*, R-tree, time parameterization, wireless networks

Rating

5

Bibtex Entry

@article{ saltenis99indexing,

author = "Simonas Saltenis and Christian Jenson and Scott Leutenegger and Mario Lopez",

title = "Indexing the Positions of Continuously Moving Objects",

journal = "TimeCenter Technical Report",

year = "1999",

url = "http://www.cs.auc.dk/TimeCenter"

}

 

Back to index