Journal of Korea Spatial Information System Society (한국공간정보시스템학회 논문지)

Korea Spatial Information System Society (대한공간정보학회)
권호 표지

UIL：A Novel Indexing Method for Spatial Objects and Moving Objects

  • Huang, Xuguang (Inha University Dept. of Computer Science and Information Engineering) ;
  • Baek, Sung-Ha (Inha University Dept. of Computer Science and Information Engineering) ;
  • Lee, Dong-Wook (Inha University Dept. of Computer Science and Information Engineering) ;
  • Chung, Weon-Il (Hoseo Universitry Dept. of Information Security Engineering) ;
  • Bae, Hae-Young (Inha University Dept. of Computer Science and Information Engineering)
  • Published : 2009.06.30
Download PDF
⟨ Previous Next ⟩

Abstract

Ubiquitous service based on Spatio-temporal dataspaces requires not only the moving objects data but also the spatial objects. However, existing methods can not handle the moving objects and spatial objects together. To overcome the limitation of existing methods, we propose a new index structure called UIL (Union Indexing Lists) which contains two parts: MOL (Moving Object List) and SOL (Spatial Object List) to index the moving objects and spatial objects together. In addition, it can suppose the flexible queries on these data. We present the results of a series of tests which indicate that the structure perform well.

Keywords

References

  1. X. Xu, J. Han, W. Lu, RT-tree: an improved R-tree index structure for spatiotemporal databases, Proceedings of the 4th Intl. Symposium on Spatial Data Handling, SDH’90, Zurich, Switzerland,1990, pp. 1040-1049.
  2. Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts.
  3. David B. Lomet, Betty Salzberg, Transaction time database, Temporal databases, 1993, pp. 388-417.
  4. Theodoridis, Y., Vazirgiannis, M., and Sellis, T.: Spatio-Temporal Indexing for Large Multimedia Applications. In Proc. of the 3rd IEEE Int'l Conference on Multimedia Computing and Systems, 1996, pp. 441-448.
  5. Mario A. Nascimento, Jefferson R.O. Silva, Towards historical R-trees, Proceeding of the 1998 ACM Symposium on Applied Computing, Atlanta, GA, February 1998, pp. 235-240.
  6. Yufei Tao, Dimitris Papadias, MV3R-tree: a spatio- temporal access method for timestamp and interval queries, Proceedings of 27th International Conference on Very Large Data Bases, Roma,Italy,September2001.
  7. Dong Xin, Halevy Alon. Indexing dataspaces. In: Proc. of the 27th Int'l Conf. on Management of Data (SIGMOD 2007). NewYork:ACMPress, 2007. 43-54.
  8. Jon Louis Bentley, Donald F. Stanat, E. Hollings Williams Jr., The complexity of finding fixed-radius near neighbors, Information Processing Letters 6 (6), 1977 209-212. https://doi.org/10.1016/0020-0190(77)90070-9
  9. Patel, J.M., Chen, Y., Chakka, V.P., STRIPES: an efficient index for predicated trajectories. In: Proceedings of SIGMOD, 2004, pp. 637-646.
  10. Jensen, C.S., Lin, D., Ooi, B.C., Query and update efficient B+-tree based indexing of moving objects. VLDB 2004, pp. 768-779.
  11. Theodoridis, Y., Silva, J. Nascimento, M. On the Generation of Spatiotemporal Datasets. SSD, 1999
  12. Nascimento, M., Silva, J., Thedoridis, Y. Evaluation of Access Structures ofor Discretely Moving Points. International Workshop on Spatio-Temporal Database Management, 1999.
  13. Pfoser, D., Jensen, C., Theodoridis, Y. Novel Approaches to the Indexing of Moving Object Trajectories. VLDB, 2000.
  14. Miller, Catherine L. TIGER/Line Files Technical Documentation. UA 2000. U.S. Department of Commerce, Geography Division,U.S. Census Bureau. http://www.census.gov/geo/www/TIGER/ TIGERua/ua2ktgr.pdf
  15. J.R. Smith and S.-F. Chang. Quad-Tree Segmentation for Texture-Based Image Query, ACM 2nd Multimedia Conference Proceedings, 1994.
  16. J.T. Robinson. The k-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes, Proc. ACM SIGMOD, 1981, pp. 10-18.