Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

An Efficient Indexing Scheme for Multi-dimensional Moving Objects


Elbassioni,  Khaled M.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;


Elmasry,  Amr
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Elbassioni, K. M., Elmasry, A., & Kamel, I. (2003). An Efficient Indexing Scheme for Multi-dimensional Moving Objects. In Database Theory - ICDT 2003 (pp. 425-439). Berlin: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0019-EC13-9
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.