Optimal Space Data Structures for I/O Efficient Search of Objects Moving on a Graph

Description

We present a space optimal spatio-temporal data structure called minimum I/O Graph Strip Tree (minGStree) to index objects assumed to move at constant velocity on the edges of 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 O(n/B) blocks of external memory, where n is the number of moving object instances (unique entries of moving objects) and B is the I/O block size. We propose two variations of the minGStree: minGStreeI and minGStreeR. For n moving object instances distributed in a uniform fashion 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 minGStreeI is O(logB(n/E)+k). In the minGStreeR variation, O(n/E + k[superscript ''']) I/Os are required for the same query. k and k[superscript '''] are the number of disk blocks required to store the time intervals intersecting the time query, and the rectangles intersecting the query, respectively. We anticipate this data structure will be practical to implement.