Efficient Search of Path-Constrained Moving Objects

Description

We present a spatio-temporal data structure called the Graph Strip Tree (GStree) for indexing objects constrained to move on a planar graph. The GStree is designed to efficiently answer range queries about the current or past positions of moving objects. To test the efficiency of our data structure, a road network of 66,437 roads was used. A set of 443,983 moving objects was randomly positioned on edges of the planar graph, with location updates made over 5, 50 and 100 time steps. This resulted in 3.2 x 10[superscript 6], 32 x 10[superscript 6] and 64 x 10[superscript 6] location updates, respectively, indexed by the data structures. Average search times for random queries to find moving objects indexed by a GStree were compared to average search times for the same queries on moving objects indexed by a MON-tree. Results indicate that the GStree is up to 24 times faster than the MON-tree for internal memory searching, and visits between 3.6 and 38 times fewer nodes. Analysis indicates the GStree will be significantly faster for external memory search where the search time is dominated by the number of disk I/Os.