A Proposed Hybrid Spatial Indexing: QX Tree

Authors

  • Jnyanaranjan Dash School of Computer Engineering KIIT University, Bhubaneswar, India
  • Dipa Patra School of Computer Engineering KIIT University, Bhubaneswar, India
  • Chittaranjan Pradhan School of Computer Engineering KIIT University, Bhubaneswar, India

DOI:

https://doi.org/10.37591/rtpl.v2i1.363

Keywords:

Spatial indexing, Hybrid spatial indexing, Quad tree, X tree, R Tree, QR Tree, QX Tree.

Abstract

Out of different spatial indexing structures available for accessing spatial data, none of them is suitable for high dimensions. This is because the performance of the spatial indexing structures become poorer with the increase in dimension. Thus there is a need for a better spatial indexing structure for the same. Here we have proposed a hybrid indexing structure by combining the Quad Tree and X Tree. We have considered the X Tree over R Tree used in the previous hybrid indexing structure, QR Tree. This is due to the better performance of X Tree over the R Tree in case of highly overlapped data.

References

Guobin Li, Lin Li, “A Hybrid Structure of Spatial Index Based on Multi-Grid and QR-Tree, International Symposium of Computer Science and Computational Technology, 2010, pp. 447-450.

Yu-Chen Fu, Zhi-Yong Hu, Wei Guo, Dong-Ru Zhou, “QR-tree: a Hybrid Spatial Index Structure:, IEEE International Confeence on Machine Learning and Cybernetics, 2003, Vol. 1, pp. 459-463.

R. A. Finkel, J. L. Bentley, “Quad Trees: A Data Structure for Retrieval on Composite keys”, Springer Acta Informatica, 1974, Vol. 4, No. 1, pp. 1-9.

Hanan Samet, “The Quadtree and Related Hierarchical data Structures”, ACM Computing Surveys, 1984, Vol. 16, No. 2, pp. 187-260.

Stefan Berchtold, Daniel A. keim, Hans-Peter Kriegel, “The X-tree: An Index Structure for High-Dimensional Data”, ACM International Conference on Very Large data Bases, 1996, pp. 28-39.

Antonin Guttman, “R-trees: A Dynamic Index Structure for Spatial Searching”, ACM SIGMOD International Conference on Management of Data, 1984, Vol. 14, No. 2, pp. 47-57.

Douglas Comer, “Ubiquitous B-Tree”, ACM Computing Surveys, 1979, Vol. 11, No. 2, pp. 121-137.

Jon Louis Bentley, “Multidimensional Binary Search Trees used for Associative Searching”, ACM Communications, 1975, Vol. 18, No. 9, pp. 509-517.

Downloads

Published

2020-02-15

Issue

Vol. 2 No. 1 (2015)

Section

Research Articles

License

Declaration and Copyright Transfer Form

(to be completed by authors)

I/ We, the undersigned author(s) of the submitted manuscript, hereby declare, that the above manuscript which is submitted for publication in the STM Journals(s), is not published already in part or whole (except in the form of abstract) in any journal or magazine for private or public circulation, and, is not under consideration of publication elsewhere.

  • I/We will not withdraw the manuscript after 1 week of submission as I have read the Author Guidelines and will adhere to the guidelines.
  • I/We Author(s ) have niether given nor will give this manuscript elsewhere for publishing after submitting in STM Journal(s).
  • I/ We have read the original version of the manuscript and am/ are responsible for the thought contents embodied in it. The work dealt in the manuscript is my/ our own, and my/ our individual contribution to this work is significant enough to qualify for authorship.
  •  I/We also agree to the authorship of the article in the following order:

Author’s name                                    

 

1. ________________

2. ________________

3. ________________

4. ________________

 

We  Author(s) tick this box and would request you to consider it as our signature as we agree to the terms of this Copyright Notice, which will apply to this submission if and when it is published by this journal.