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

Simple item page
dc.contributor.authorLe, Thuy, T., T.
dc.contributor.authorNickerson, Bradford, G.
dc.date.accessioned2023-03-01T18:27:48Z
dc.date.available2023-03-01T18:27:48Z
dc.date.issued2009
dc.description.abstractWe 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.
dc.description.copyrightCopyright @ Thuy T. T. Le and Bradford G. Nickerson, 2009.
dc.identifier.urihttps://unbscholar.lib.unb.ca/handle/1882/14783
dc.rightshttp://purl.org/coar/access_right/c_abf2
dc.subject.disciplineComputer Science
dc.titleA Data Structure for I/O Efficient Search of Objects Moving on a Graph
dc.typetechnical report

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
item.pdf
Size:
245.54 KB
Format:
Adobe Portable Document Format
Download

Collections

Research Reports