A Data Structure for I/O Efficient Search of Objects Moving on a Graph

Description

We present a spatio-temporal data structure called minimum I/O Graph Strip Tree (minGStree) to index moving objects on a graph. The minGStree is designed to efficiently answer time instance and time interval queries about the past positions of moving objects. The minGStree uses Θ( n ) blocks of external memory, where n B is the number of moving object instances (unique entries of moving objects) and B is the I/O block size. For n moving object instances randomly distributed on the E edges of a graph over a time domain [0, T ], the expected number of I/Os required to determine the moving objects intersecting one edge (for both time instance queries and time interval queries) in a minGStree is O(logB ( n ) + k), where k is the number E of disk blocks required to store the answer. We anticipate this data structure will be practical to implement.