Query as Region Partition in Managing Moving Objects for Concurrent Continuous Query

Download Full Text
Ming Qi, Guangzhong Sun, Yun Xu
Published Date:
December 30, 2011
Volume 2, Issue 1
1 - 6

spatial data indexing, continuous query, query as region partition, parallel computing
Ming Qi, Guangzhong Sun, Yun Xu, "Query as Region Partition in Managing Moving Objects for Concurrent Continuous Query". International Journal of Research in Computer Science, 2 (1): pp. 1-6, December 2011. doi:10.7815/ijorcs.21.2011.008 Other Formats


Applications in location-based services rely on the efficient management of large scale moving objects, and one of the most important operations is real-time continuous query over moving objects, such as monitoring the objects of a certain region. In order to satisfy the high throughput and handle real-time updates and queries, it is a good choice to introduce multi-core parallel processing and managing spatial indices in main memory. In this paper, we propose a new scheme of processing continuous query on a novel spatial index based on uniform grid which is proved to be a good indexing scheme in main memory. The novelty of our index is to manage query region as the partition in the spatial index, which unified the index updating and query processing. Our experiments indicate that this sophisticated approach has better performance especially when the query is rather stationary.

  1. Volker Gaede, Oliver G¨unther. Multidimensional Access Methods. In ACM Computing Surveys (CSUR) , Volume 30 Issue 2, June 1998. doi:10.1145/280277.280279
  2. D. Kalashnikov, S. Prabhakar, S. Hambrusch, Main Memory Evaluation of Monitoring Queries Over Moving Objects, Distributed and Parallel Databases: An International Journal, Vol. 15, No. 2, pages 117-136, 2004. doi:10.1023/B:DAPD.0000013068.25976.88
  3. Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Elsevier 2008.
  4. Hector Garcia-Molina, Jeffret D. Ullman, Jennifer Widom. Database System: Implementation, Second Edition. Pearson Education Inc. 2009.
  5. Darius ˇ Sdlauskas, Simonas ˇ Sltenis, Christian W. Christiansen, Jan M. Johansen, Donatas ˇ Sulys. Trees or Grids? Indexing Moving Objects in Main Memory. In ACM GIS’09, November 4-6, 2009. Seattle, WA, USA.
  6. Hanan Samet. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann Publishers, 2006.
  7. John T. Robinson. The K-D-B-Tree: A Search Structure for Large Multideminsional Dynamic Indexes. In Proceedings of the ACM SIGMOD International conference on Management of data , 1981.
  8. Diane Greene. An Implementation and Performance Analysis of Spatial Data Access Methods. In Proceedings. Fifth International Conference on Data Engineering, 1989. doi:10.1109/ICDE.1989.47268
  9. Antonin Guttman. R-trees: a dynamic index structure for spatial searching. SIGMOD Rec. 14, 2 (June 1984), 47-57. doi:10.1145/971697.602266
  10. Xiaopeng Xiong, Mohamed F. Mokbel, etc. Scalable Spatio-temporal Continuous Query Processing for Location-aware Services. In Proceedings of 16th International Conference on Scientific and Statistical Database Management 2004,(SSDBM04).
  11. Jing Dai, Chang-Tien Lu. CLAM: Concurrent Location Management for Moving Objects. In ACM International Symposium on Advances in Geographic Information Systems, New York, NY, USA, 2007.
  12. Chang-Tien Lu, Jing Dai, Ying Jin, Janak Mathuria. GLIP: A Concurrency Control Protocol for Clipping Indexing, IEEE Transaction on Knowledge and Data Engineering, Vol.21, No.5, 2009. doi:10.1109/TKDE.2008.183
  13. Jing Dai, Chang-Tien Lu, Lien-Fu Lai. A Concurrency Control Protocol for Continuously Monitoring Moving Objects. In Tenth International Conference on Mobile Data Management: Systems, Services and Middleware 2009. doi:10.1109/MDM.2009.24
  14. digu.com http://2011.digu.com/indexMap
  15. Nievergelt, J., Hinterberger, H., and Sevcik, K. C. 1984. The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 1984. doi:10.1145/348.318586
  16. Harris, T. L., Fraser, K., and Pratt, I. A. 2002. A Practical Multi-word Compare-and-Swap Operation. In Proceedings of the 16th international Conference on Distributed Computing, 2002
  17. Thomas Brinkhoff. Generating Network-Based Moving Objects. In Proceedings 12th International Conference on Scientific and Statistical Database Management, 2000, IEEE Computer Society Press. doi:10.1109/SSDM.2000.869794

    Sorry, there are no citation(s) for this manuscript yet.