Semantic Spatial Objects Data Structure for Spatial Access Method

Authors: Kalum Priyanath Udagepola, Zuo Decheng, Wu Zhibo, Yang Xiaozong

Abstract:

Modern spatial database management systems require a unique Spatial Access Method (SAM) in order solve complex spatial quires efficiently. In this case the spatial data structure takes a prominent place in the SAM. Inadequate data structure leads forming poor algorithmic choices and forging deficient understandings of algorithm behavior on the spatial database. A key step in developing a better semantic spatial object data structure is to quantify the performance effects of semantic and outlier detections that are not reflected in the previous tree structures (R-Tree and its variants). This paper explores a novel SSRO-Tree on SAM to the Topo-Semantic approach. The paper shows how to identify and handle the semantic spatial objects with outlier objects during page overflow/underflow, using gain/loss metrics. We introduce a new SSRO-Tree algorithm which facilitates the achievement of better performance in practice over algorithms that are superior in the R*-Tree and RO-Tree by considering selection queries.

Keywords: Outlier, semantic spatial object, spatial objects, SSRO-Tree, topo-semantic.

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

References:

[1] N. An, K. Kanth, and S. Ravada, ''Improving Performance with Bulk-Inserts in Oracle R-Trees,'' In VLDB, 2003.
[2] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, ''The R*-tree: An efficient and robust access method for points and rectangles,'' In Proceedings of the ACM SIGMOD international conference on Management of data, pp.322-331, 1990.
[3] T. Brinkhoff, H. Kriegel, and R. Schneider, ''Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems,'' IEEE, 1993.
[4] C. Böhm, ''A cost model for query processing in high-dimensional data spaces,'' ACM Transactions on Database Systems,vol. 25, no. 2, pp.129-178,2000.
[5] E. Chavez, G. Navarro, R. Baeza-Yates, and J. Marroquin, ''Searching in metric spaces,'' Technical Report TR/DCC-99-3, Dept. of Computer Science, Univ. of Chile, 1999.
[6] S. Chen, X. Wang, N. Rishe, and M.A.W. Weiss, ''A Web Based spatial data access system using semantic R-Trees,'' Elsevier Science, 2003.
[7] V. Gaede, and O. G├╝nther, ''Multidimensional access methods,'' ACM Computing Surveys, vol. 30, no. 2, pp.170-231,1998.
[8] G├╝nther, O.: 'Efficient Computations of Spatial Joins', Proc. 9th Int. Conf. on Data Engineering, Vienna, Austria, 1993.
[9] A. Guttman, ''R-trees: A dynamic index structure for spatial searching,'' In proceedings of the ACM SIGMOD International Conference on Management of Data, pp.47-57, 1984.
[10] I. Kame, and C. Faloutsos, ''On Packing RTrees,'' CIKM, pp. 490-499, 1993.
[11] K. V. R. Kanth, A. E. Abbadi, D. Agrawal, and A. K. Singh, ''Indexing Non-Uniform Spatial Data,'' In Proceedings of International Database Engineering & Applications Symposium,1997.
[12] K. V. R. Kanth, S. Ravada, J. Sharma, and J. Banerjee. ''Indexing Medium-dimensionality Data in Oracle,'' In Proceedings of ACM/SIGMOD Annual Conference on Management of Data, pp.521-522, 1999.
[13] K. V. R. Kanth, S. Ravada, and D. Abugov, ''Quadtree and R-tree Indexes in Oracle Spatial: A Comparison using GIS Data,'' In Proceedings of ACM/SIGMOD Annual Conference on Management of Data, pp. 546-557, 2002.
[14] S. T. Leutenegger, and M. A. Lopez, ''The Effect of Buffering on the Performance of R-Trees,'' International IEEE Transactions on Knowledge and Data Engineering, vol. 12, no. 1, pp. 33-44, 2000.
[15] A. Noske, ''Dynamic Range Queries in Vector Space,'' http://www.andrewnoske.com/professional/publications/Lit_Review_-_Dynamic_Range_Queries_in_Vector_Space.doc.
[16] Orenstein J. ''A.: 'Spatial Query Processing in an Object-Oriented Database System,'' Proc. ACM SIGMOD Int. Conf. on Management of Data, pp. 326-333, 1986.
[17] A. Papadopoulos, P. Rigaux, and M. Scholl, ''A performance evaluation of spatial join processing strategies,'' Proceedings of the 6th International Symposium on Advances in Spatial Databases, pp.286-307,1999.
[18] S. Prabhakar, Y. Xia, D. V. V. Kalashnikov, W. G. G. Aref and S. E. E. Hambrusch, ''Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects,'' IEEE Transactions on Computers archive, vol. 51, no.10, pp.1124-1140, 2002.
[19] D. Rotem,''Spatial Join Indices,'' Proc. Int. Conf. on Data Engineering, pp. 500-509,1991.
[20] N. Roussopoulos, D. Leifker, Direct Spatial Search on Pictorial Database Using Packed R-Trees, Proceeding ACM SIGMOD, 1985.
[21] N. Roussopoulos, S. Kelley, and F. Vincent, ''Nearest neighbor queries*,'' Proceedings of ACM SIGMOD, 1995.
[22] S. Servigne, T. Ubeda, A. Puricell, and R. Laurini, ''A Methodology for Spatial Consistency Improvement of Geographic Databases,'' Geoinformatica, vol. 4, no. 1, pp. 7-34, 2000.
[23] K.P. Udagepola, L. Xiang, A.W. Wijeratne, and Y. Xiaozong, ''MSRIC: A Model for Spatial Relations and Integrity Constraints in Topographic Databases,'' 5th Int. Conf. on Artificial Intelligence, Knowledge Engineering and Database. Research conference, 2006.
[24] K.P. Udagepola, L. Xiang, A.W. Wijeratne, and Y. Xiaozong, ''Semantic Integrity Constraint Violations Check for Spatial Database,'' MMT-2007, to be published.
[25] J. S. Vitter, ''External Memory Algorithms and Data Structures,'' ACM Computing Surveys, vol. 33, no. 2, pp.209-271, 2001.
[26] S. Wang, J. M. Hellerstein, and I. Lipkind, ''Near-neighbor query performance in search trees,'', http://citeseer.ist.psu.edu/92931.html.
[27] T. Xia, , and D. Zhang, ''Improving the R*-tree with Outlier Handing Techniques,'' GIS?05, 2005.
[28] D. Zhang, and T. Xia, ''A Novel Improvement to the R*tree Spatial Index using Gain/Loss Metrics,'' GIS'04, 2004.