Choosing R-tree or Quadtree Spatial DataIndexing in One Oracle Spatial Database System to Make Faster Showing Geographical Map in Mobile Geographical Information System Technology

Authors: Maruto Masserie Sardadi, Mohd Shafry bin Mohd Rahim, Zahabidin Jupri, Daut bin Daman

Abstract:

The latest Geographic Information System (GIS) technology makes it possible to administer the spatial components of daily “business object," in the corporate database, and apply suitable geographic analysis efficiently in a desktop-focused application. We can use wireless internet technology for transfer process in spatial data from server to client or vice versa. However, the problem in wireless Internet is system bottlenecks that can make the process of transferring data not efficient. The reason is large amount of spatial data. Optimization in the process of transferring and retrieving data, however, is an essential issue that must be considered. Appropriate decision to choose between R-tree and Quadtree spatial data indexing method can optimize the process. With the rapid proliferation of these databases in the past decade, extensive research has been conducted on the design of efficient data structures to enable fast spatial searching. Commercial database vendors like Oracle have also started implementing these spatial indexing to cater to the large and diverse GIS. This paper focuses on the decisions to choose R-tree and quadtree spatial indexing using Oracle spatial database in mobile GIS application. From our research condition, the result of using Quadtree and R-tree spatial data indexing method in one single spatial database can save the time until 42.5%.

Keywords: Indexing, Mobile GIS, MapViewer, Oracle SpatialDatabase.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1075228

References:

[1] Rajinder, S. N. (2004). Cartographic visualisation for mobile application. Master-s thesis, ITC/IIRS.
[2] Peng, Z. R. & Tsou, M. H. (2003). Internet GIS: Distributed Geographic Information Services for the Internet and Wireless Network. John Wiley and Sons Inc.
[3] Mensah, E. (2007). Designing a Prototype Mobile GIS to Support Cadastral Data Collection in Ghana, 44.
[4] Vckovski, A. (1999). Interoperability and spacial information theory. Interoperating Geographic Information Systems.
[5] Kraak, M. J. (2002). Current trends in visualisation of geographic data with special reference to cartography. Invited paper: In Proceedings of the XXIIth INCA Congress 2002, Indian National Cartographic Association: Convergence of Imagery Information and Maps, volume 22, 319-324.
[6] Chen, K., & Shi, W. (2002), A Study of Dynamic Database in Mobile GIS.
[7] Guttman, A. (1984). R-Trees: A Dynamic Index Structure for Spatial Searching. Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57. ISBN 0-89791-128-8.
[8] Zhu, Q., Gong, J., Zhang, J. (2007). An efficient 3D R-tree spatial index method for virtual geographic environments. ISPRS Journal of Photogrammetry and Remote Sensing, Volume 62, Issue 3, August 2007, pp 217-224.
[9] Lee, T., Moon, B., Lee, S. (2006). Bulk insertion for R-trees by seeded clustering. Data & Knowledge Engineering, Volume 59, Issue 1, October 2006, pp 86-106.
[10] Lee, M. L., Hsu, W., Jensen, C. S., Cui, B., Teo, K. L. (2003). Supporting Frequent Updates in R-Trees: A Bottom-Up Approach. Proceedings 2003 VLDB Conference, 2003, pp 608-619.
[11] An, N., Kothuri, R. K. V., Ravada, S. (2003). Improving Performance with Bulk-Inserts in Oracle R-Trees. Proceedings 2003 VLDB Conference, 2003, pp 948-951.
[12] Chan, E. P. F., & Chow, K. K. W. (2002). On multi-scale display of geometric objects. Data & Knowledge Engineering, Volume 40, Issue 1, January 2002, pp 91-119.
[13] Yun, J. K., Kim, D. O., Hong, D. S., Kim, M. H., Han, K.J. (2006). A real-time mobile GIS based on the HBR-tree next term for location based services. Computers & Industrial Engineering, Volume 51, Issue 1, September 2006, pp 58-71.
[14] Francis, D. H., Madria, S., Sabharwal, C. (2008). A scalable constraintbased Q-hash indexing for moving objects. Information Sciences, Volume 178, Issue 6, 15 March 2008, pp 1442-1460.
[15] Liu, C. M., & Fu, S. Y. (2008). Effective protocols for kNN search on broadcast multi-dimensional index trees. Information Systems, Volume 33, Issue 1, March 2008, pp 18-35.
[16] Finkel, R., & Bentley, J. L. (1974). Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Informatica 4 (1): 1-9.
[17] Oracle Spatial 10g White Paper (2006). Oracle Spatial Quadtree Indexing, 10g Release 1 (10.1).
[18] Chang, C. Y., Maciejewski, A. A., Balakrishnan, V., Roberts, R. G., Saitwal, K. (2006). Quadtree-based eigen decomposition for pose estimation in the presence of occlusion and background clutter.
[19] Geller, S., Talke, J., Krafczyk, M. (2007). Lattice-Boltzmann Method on Quadtree-Type Grids for Fluid Structure Interaction. Fluid-Structure Interaction, 270-293.
[20] Tzouramanis, T., Vassilakopoulos, M., Manolopoulos, Y. (2000). Multiversion Linear Quadtree for Spatio-Temporal Data. Current Issues in Databases and Information Systems, 279-292.
[21] Zhang, L. & Xi, L. F. (2007). A Novel Fractal Image Coding Based on Quadtree Partition of the Adaptive Threshold Value. Theoretical Advances and Applications of Fuzzy Logic and Soft Computing, 504- 512.
[22] Varas, J. (2007). Mobile Robot Path Planning Among Weighted Regions Using Quadtree Representations. Computer Aided Systems Theory - EUROCAST├óÔé¼™99, 239-249.
[23] Cheng, S. W. & Lee, K. H. (2008). Quadtree Decomposition, Steiner Triangulation, and Ray Shooting. Algorithms and Computation, 368- 377.
[24] Grbovic, J. P., Fagg, G. E., Angskun, T., Bosilca, G., Dongarra, J. J. (2006). MPI Collective Algorithm Selection and Quadtree Encoding. Recent Advances in Parallel Virtual Machine and Message Passing Interface, 40-48.
[25] Varas, J. (2007). Mobile Robot Path Planning Among Weighted Regions Using Quadtree Representations. Computer Aided Systems Theory - EUROCAST├óÔé¼™99, 239-249.
[26] Mir, Z. H. & Ko, Y. B. (2006). A Quadtree-Based Data Dissemination Protocol for Wireless Sensor Networks with Mobile Sinks. Personal Wireless Communications, 447-458.
[27] Samet, R. & Ozsavas, E. (2007). Optimization of Quadtree Triangulation for Terrain Models. Advanced Concepts for Intelligent Vision Systems, 48-59.
[28] Mir, Z. H. & Ko, Y. B. (2007). A quadtree-based hierarchical data dissemination for mobile sensor networks. Telecommunication Systems, 117-128.
[29] Reza, A. W., Eswaran, C., Hati, S. (2007). Diabetic Retinopathy: A Quadtree Based Blood Vessel Detection Algorithm Using RGB Components in Fundus Images. Journal of Medical Systems, 147-155.
[30] Tanin, E., Harwood, A., Samet, H. (2006). Using a distributed quadtree index in peer-to-peer networks. The VLDB Journal, The International Journal on Very Large Data Bases, 165-178.
[31] H. Samet (1989). The design and analysis of spatial data structures. Addison-Wesley Publishing Co..
[32] A. Guttman (1984). R-trees: A dynamic index structure for spatial searching. Proc. A CM SIGMOD Int. Conf. on Management of Data, pages 47-57.
[33] T. Sellis, N. Roussopoulos, and C. Faloutsos (1988). The r+-tree: A dynamic index for multi-dimensional objects. Procdf the Int. Conf. on Very Large Data Bases, 13:507-518.
[34] N. Beckmann, H. Kriegel, R. Schneider, B. Seeger (1990). The R* tree: An efficient and robust access method for points and rectangles. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 322-331.
[35] S. Berchtold, D. A. Keim, and H. P. Kreigel (1996). The X-tree: An index structure for high dimensional data. Procff the Int. Conf. on Very Large Data Bases.
[36] S. T. Leutenegger, M. A. Lopez, J. M. Edgington (1997). STR: A simple and efficient algorithm for R-tree packing. In Proe. Int. Conf. on Data Engineering.
[37] V. Gaede & O. Gunther (1998). Multidimensional access methods. ACM Computing Surveys, 30(2).
[38] K. V. Ravi Kanth, Siva Ravada, J. Sharma, J. Banerjee (1999). Indexing medium-dimensionality data in oracle. In Proc. ACM SIGMOD Int. Conf. on Management of Data.
[39] K. V. Ravi Kanth & Siva Ravada (2001). Efficient processing of large spatial queries using interior approximations. In Symposium on Spatial and Temporal Databases (SSTD).
[40] Oracle Application Server 10g White Paper (2007). Oracle Application Server 10g.