Scalable processing of trajectory-based queries in space-partitioned moving objects databases

ABSTRACT

Space-partitioned Moving Objects Databases (SP-MODs) allow for the scalable, distributed management of large sets of mobile objects' trajectories by partitioning the trajectory data to a network of database servers.

Processing a spatio-temporal query q therefore requires efficiently routing q to the servers storing the affected trajectory segments. With a coordinate-based query --- like a spatio-temporal range query --- the relevant servers are directly determined by the queried range. However, with trajectory-based queries --- like retrieving the distance covered by a certain object during a given time interval --- the relevant servers depend on actual movement of the queried object. Therefore, efficient routing mechanisms for trajectory-based queries are an important challenge in SP-MODs.

In this paper, we present the Distributed Trajectory Index (DTI) that allows for such efficient query routing by creating an overlay network for each trajectory. We further present an enhanced index called DTI+S. It accelerates the processing of queries on aggregates of dynamic attributes, like the maximum speed during a time interval, by augmenting DTI with summaries of trajectory segments. Our simulations with a network of 1000 database servers show that DTI+S can reduce the overall processing time by more than 98%.

REFERENCES

• 1: R. H. Güting and M. Schneider. Moving Objects Databases. Morgan Kaufmann Publishers, 2005.
• 2: Z. J. Haas. The Routing Algorithm for the Reconfigurable Wireless Networks. In Proc. of 6th ICUPC, Oct. 1997.
• 3: Marios Hadjieleftheriou , George Kollios , J. Tsotras , Dimitrios Gunopulos, Indexing spatiotemporal archives, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.143-164, June 2006 [doi>10.1007/s00778-004-0151-3]
• 4: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 5: Alexander Leonhardi , Kurt Rothermel, A Comparison of Protocols for Updating Location Information, Cluster Computing, v.4 n.4, p.355-367, October 2001 [doi>10.1023/A:1011872831932]
• 6: Alexander Leonhardi , Kurt Rothermel, Architecture of a Large-Scale Location Service, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.465, July 02-05, 2002
• 7: Michael Liljenstam , Jason Liu , David M. Nicol, Simulation of large scale networks II: development of an internet backbone topology for large-scale network simulations, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
• 8: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for ad-hoc sensor networks, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844142]
• 9: M. F. Mokbel, T. M. Ghanem, and W. G. Aref. Spatio-Temporal Access Methods. IEEE Data Eng. Bull., 26(2):40--49, June 2003.
• 10: Jinfeng Ni , Chinya V. Ravishankar, Indexing Spatio-Temporal Trajectories with Efficient Polynomial Approximations, IEEE Transactions on Knowledge and Data Engineering, v.19 n.5, p.663-678, May 2007 [doi>10.1109/TKDE.2007.1006]
• 11: Mindaugas Pelanis , Simonas Šaltenis , Christian S. Jensen, Indexing the past, present, and anticipated future positions of moving objects, ACM Transactions on Database Systems (TODS), v.31 n.1, p.255-298, March 2006 [doi>10.1145/1132863.1132870]
• 12: Dieter Pfoser , Christian S. Jensen , Yannis Theodoridis, Novel Approaches in Query Processing for Moving Object Trajectories, Proceedings of the 26th International Conference on Very Large Data Bases, p.395-406, September 10-14, 2000
• 13: Evaggelia Pitoura , George Samaras, Locating Objects in Mobile Computing, IEEE Transactions on Knowledge and Data Engineering, v.13 n.4, p.571-592, July 2001 [doi>10.1109/69.940733]
• 14: William Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, v.33 n.6, p.668-676, June 1990 [doi>10.1145/78973.78977]
• 15: G. Trajcevski, H. Ding, P. Scheuermann, and I. F. Cruz. BORA: Routing and Aggregation for Distributed Processing of Spatio-Temporal Range Queries. In Proc. of 8th MDM, May 2007.
• 16: X. Xiong, H. G. Elmongui, X. Chai, and W. G. Aref. PLACE*: A Distributed Spatio-temporal Data Stream Management System for Moving Objects. In Proc. of 8th MDM, May 2007.
• 17: Jianjun Zhang , Gong Zhang , Ling Liu, GeoGrid: A Scalable Location Service Network, Proceedings of the 27th International Conference on Distributed Computing Systems, p.60, June 25-27, 2007 [doi>10.1109/ICDCS.2007.113]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
MOD, distributed query processing, moving objects database, spatio-temporal indexing, trajectory-based query