An Integration Algorithm of X-tree and kd-tree for Efficient Retrieval of Spatial Database


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 6, No. 12, pp. 3469-3476, Dec. 1999
10.3745/KIPSTE.1999.6.12.3469,   PDF Download:

Abstract

In spatial database based on spatial data structures, instead of one-dimensional indexing structure, new indexing structure which corresponds to multi-dimensional features of spatial object if required. In order to meet those requirements. in this paper we proposed new indexing structure for efficient retrieval of spatial database by carrying through the feature analysis of conventional multi-dimensional indexing structures. To improve the sequential search method of supernodes in the conventional X-tree and to reduce the retrieval time in case of generating the huge supernodes, we proposed a indexing structure integrating the kd-tree based on point index structure into the X-tree. We implemented the proposed indexing structure and analyzed its retrieval time according to the dimension and distribution of experimental data.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
J. W. Yoo, Y. J. Shin, S. K. Jung, "An Integration Algorithm of X-tree and kd-tree for Efficient Retrieval of Spatial Database," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 6, no. 12, pp. 3469-3476, 1999. DOI: 10.3745/KIPSTE.1999.6.12.3469.

[ACM Style]
Jang Woo Yoo, Young Jin Shin, and Soon Key Jung. 1999. An Integration Algorithm of X-tree and kd-tree for Efficient Retrieval of Spatial Database. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 6, 12, (1999), 3469-3476. DOI: 10.3745/KIPSTE.1999.6.12.3469.