Open Access Open Access  Restricted Access Subscription Access

A Proposed Hybrid Spatial Indexing: QX Tree

Jnyanaranjan Dash, Dipa Patra, Chittaranjan Pradhan


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.


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

Full Text:



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.


  • There are currently no refbacks.