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
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%.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:59491", author = "Maruto Masserie Sardadi and Mohd Shafry bin Mohd Rahim and Zahabidin Jupri and Daut bin Daman", title = "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", 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.", volume = "2", number = "10", pages = "3450-9", }
