Browsing by Author "Le, Thuy, T., T."

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    A Data Structure for I/O Efficient Search of Objects Moving on a Graph
    (2009) Le, Thuy, T., T.; Nickerson, Bradford, G.
    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.
  • Thumbnail Image
    Item
    Optimal Space Data Structures for I/O Efficient Search of Objects Moving on a Graph
    (2009) Le, Thuy, T., T.; Nickerson, Bradford, G.
    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.