hide
Free keywords:
-
Abstract:
We consider the problem of indexing a set of objects moving in d-dimensional
space along linear trajectories. A simple disk-based indexing scheme is
proposed to efficiently answer queries of the form: report all objects that
will pass between two given points within a specified time interval. Our scheme
is based on mapping the objects to a dual space, where queries about moving
objects translate into polyhedral queries concerning their speeds and initial
locations. We then present a simple method for answering such polyhedral
queries, based on partitioning the space into disjoint regions and using a
B-tree to index the points in each region. By appropriately selecting the
boundaries of each region, we can guarantee an average search time that almost
matches a known lower bound for the problem. Specifically, for a fixed d, if
the coordinates of a given set of N points are statistically independent, the
proposed technique answers polyhedral queries, on the average, in
O((N/B)^1-1/d}.(\log_B N)^{1/d+K/B) I/O's using O(N/B) space, where B
is the block size, and K is the number of reported points. Our approach is
novel in that, while it provides a theoretical upper bound on the average query
time, it avoids the use of complicated data structures, making it an effective
candidate for practical applications.
