Semantic Spatial Objects Data Structure for Spatial Access Method

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.

• Kalum Priyanath Udagepola
• Zuo Decheng
• Wu Zhibo
• Yang Xiaozong

• Outlier
• semantic spatial object
• spatial objects
• SSRO-Tree
• topo-semantic.

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