Efficient Search of Path-Constrained Moving Objects

dc.contributor.authorNickerson, Bradford, G.
dc.contributor.authorThi Thu Le, Thuy
dc.description.abstractWe 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.
dc.description.copyrightCopyright @ Bradford G. Nickerson and Thuy Thi Thu Le, 2008.
dc.subject.disciplineComputer Science
dc.titleEfficient Search of Path-Constrained Moving Objects
dc.typetechnical report


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
1.6 MB
Adobe Portable Document Format