Abstract
We consider the problem of indexing a set of objects moving in d-dimensional spaces along linear trajectories. A simple external-memory indexing scheme is proposed to efficiently answer general range queries. The following are examples of the queries that can be answered by the proposed method: report all moving objects that will (i) pass between two given points within a specified time interval; (ii) become within a given distance from some or all of a given set of other moving objects. Our scheme is based on mapping the objects to a dual space, where queries about moving objects are transformed 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 guarantee an average search time that 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. The proposed index is also dynamic in the sense that it allows object insertion and deletion in an amortized update cost of log B (N) I/O's. Experimental results are presented to show the superiority of the proposed index over other methods based on R-trees.
This is a preview of subscription content, log in via an institution to check access.
References
P.K. Agarwal, L. Arge, and J. Erickson, “Indexing moving points,” in 19th ACM-PODS Symposium on Principles of Database Systems, 2000, pp. 175–186.
P.K. Agarwal, L. Arge, J. Erickson, P. Franciosa, and J.S. Vitter, “Efficient searching with linear constraints,” 17th ACM-PODS Symposium on Principles of Database Systems, 1998, pp. 169–178.
R. Alonso and H.F. Korth, “Database system issues in nomadic computing,” in ACM-SIGMOD International Conference on Management of Data, 1993, pp. 388–392.
A. Aggarwal and J.S. Vitter, “The input/output complexity of sorting and related problems,” Communications of the ACM, vol. 31, no. 9, pp. 1116–1127, 1988.
ArcView GIS, ArcView Tracking Analyst, 1998.
N. Beckmann, H.P. Kriegel, R. Schneider, and B. Seeger, “The R*-tree: An efficient and robust access method for points and rectangles,” in ACM-SIGMOD International Conference on Management of Data, 1990, pp. 322–331.
B. Chazelle and B. Rosenberg, “Lower bounds on the complexity of simplex range reporting on a pointer machine,” in 19th ICALP International Colloquium on Automata, Languages and Programming, LNCS, vol. 693, 1992, pp. 439–449.
K. Elbassioni, A. Elmasry, and I. Kamel, “Efficient answering of polyhedral queries in ℝd using BBS-trees,” in 14th CCCG Canadian Conference on Computational Geometry, 2002, pp. 54–57.
K. Elbassioni, A. Elmasry, and I. Kamel, “An efficient indexing scheme for multi-dimensional moving objects,” in 9th ICDT International Conference on Database Theory, LNCS 2572, 2003, pp. 425–439.
V. Gaede and O. Gunther, “Multidimensional access methods,” ACM Computing Serveys, vol. 30, no. 2, pp. 170–231, 1998.
J. Goldstein, R. Ramakrishnan, U. Shaft, and J.B. Yu, “Processing queries by linear constraints,” in 16th ACM-PODS Symposium on Principles of Database Systems, 1997, pp. 257–267.
A. Guttman, “R-trees: A dynamic index structure for spatial searching,” in ACM-SIGMOD International Conference on Management of Data, 1984, pp. 47–57.
G. Kollios, D. Gunopulos, and V. Tsotras, “On Indexing Mobile Objects.” in 18th ACM-PODS Symposium on Principles of Databases Systems, 1999, pp. 261–272.
H.V. Jagadish, “On Indexing Line Segments,” in 16th VLDB International Conference on Very Large Data Bases, 1990, pp. 614–625.
I. Kamel and C. Faloutsos, “On packing R-trees,” in 2nd International Conference on Information and Knowledge Management, 1993, pp. 490–499.
V. Kouramajian, I. Kamel, R. Elmasri, and S. Waheed, “The time index+: An incremental access structure for temporal databases,” in 3rd International Conference on Information and Knowledge Management, 1994, pp. 296–303.
J. Matoušek, “Efficient partition trees,” Discrete and Computational Geometry, vol. 8, pp. 315–334, 1992.
S. Saltenis, C.S. Jensen, S.T. Leutenegger, and M.A. Lopez, “Indexing the positions of continuously moving objects,” in Proc. ACM-SIGMOD International Conference on Management of Data, 2000, pp. 331–342.
B. Salzberg and V.J. Tsotras, “A comparison of access methods for time evolving data,” ACM Computing Surveys, vol. 31, no. 2, pp. 158–221, 1999.
A. Schrijver, Theory of Linear and Integer Programming, 1986.
J. Tayeb, O. Ulusoy, and O. Wolfson, “A quadtree-based dynamic attribute indexing method,” The Computer Journal, vol. 41, no. 3, pp. 185–200, 1998.
Author information
Authors and Affiliations
Corresponding author
Additional information
recommend Ahmed Elmagarmid
Rights and permissions
About this article
Cite this article
Elbassioni, K., Elmasry, A. & Kamel, I. An Indexing Method for Answering Queries on Moving Objects. Distrib Parallel Databases 17, 215–249 (2005). https://doi.org/10.1007/s10619-005-6830-2
Issue Date:
DOI: https://doi.org/10.1007/s10619-005-6830-2