Snapshot location-based query processing on moving objects in road networks

ABSTRACT

Location-based services are increasingly popular and it is a key challenge to efficiently support query processing. We present a novel design to process large numbers of location-based snapshot queries on MOVing objects in road Networks (MOVNet, for short). MOVNet's dual-index design utilizes an on-disk R-tree to store the network connectivities and an in-memory grid structure to maintain moving object position updates. A method to speedily compute the overlapping grid cells in the network relates these two indices. Based on the above features we propose algorithms to support mobile network distance range queries. We demonstrate via experimental results that MOVNet yields excellent performance while scaling to a very large number of moving objects.

REFERENCES

• 1: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 2: Thomas Brinkhoff, A Framework for Generating Network-Based Moving Objects, Geoinformatica, v.6 n.2, p.153-180, June 2002 [doi>10.1023/A:1015231126594]
• 3: Hae Don Chon , Divyakant Agrawal , Amr El Abbadi, Range and kNN query processing for moving objects in grid model, Mobile Networks and Applications, v.8 n.4, p.401-412, August 2003 [doi>10.1023/A:1024535730539]
• 4: X. Huang, C. S. Jensen, H. Lu, and S. Saltenis. S-GRID: A Versatile Approach to Efficient Query Processing in Spatial Networks. In SSTD, 2007.
• 5: Kyriakos Mouratidis , Dimitris Papadias , Marios Hadjieleftheriou, Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066230]
• 6: Kyriakos Mouratidis , Man Lung Yiu , Dimitris Papadias , Nikos Mamoulis, Continuous nearest neighbor monitoring in road networks, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 7: Dimitris Papadias , Jun Zhang , Nikos Mamoulis , Yufei Tao, Query processing in spatial network databases, Proceedings of the 29th international conference on Very large data bases, p.802-813, September 09-12, 2003, Berlin, Germany
• 8: Yufei Tao , Dimitris Papadias , Jimeng Sun, The TPR*-tree: an optimized spatio-temporal access method for predictive queries, Proceedings of the 29th international conference on Very large data bases, p.790-801, September 09-12, 2003, Berlin, Germany
• 9: H. Wang and R. Zimmermann. Framework for Snapshot Location-based Query Processing on Moving Objects in Road Networks. Technical Report 08-899, University of Southern California, 2008.
• 10: Xiaopeng Xiong , Mohamed F. Mokbel , Walid G. Aref, SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases, Proceedings of the 21st International Conference on Data Engineering, p.643-654, April 05-08, 2005 [doi>10.1109/ICDE.2005.128]
• 11: Xiaohui Yu , Ken Q. Pu , Nick Koudas, Monitoring k-Nearest Neighbor Queries over Moving Objects, Proceedings of the 21st International Conference on Data Engineering, p.631-642, April 05-08, 2005 [doi>10.1109/ICDE.2005.92]

INDEX TERMS

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

Keywords:
location-based services, spatial data management