T.K. Srivani and K.T. Jagdish (India)
Multidimensional databases, Hilbert Curves, Trees, Storage and Retrieval
Mapping from multidimensional data to one-dimensional using Hilbert Index has been studied as a way of indexing for storage and retrieval of multidimensional data. There are mainly two approaches towards Storage and Retrieval of Multidimensional data [5] one is the Tree Based Approach and other is Bitmap Indexing. One main benefit of the tree-based approach over the bit map indexing is that they have superior storage property and the insert/update operations are efficient on the other hand the bitmap indexing provides for faster retrieval. Our data structure is mainly based on the tree-based approach in which every node of the tree contains a bit array. The presence of a bit array in every node provides for faster retrieval thereby giving the benefit of both the approaches. After the tree is grown it is divided into sub trees and stored. This provides for optimal searching. In this paper, we present a tree (HT-tree) based on Hilbert Curves for efficient data storage and retrieval of Multidimensional data. The HT-tree data search method mainly makes use of the bit representation of the Hilbert Index values to search for the data, instead of using conventional point search methods as used in most of the R-trees. The proposed data structure overcomes the disadvantages of the HG-tree namely, extra computation of minimum bounding rectangle from the range of Hilbert values required for point search, range search and nearest neighbour search and also the problems occurring from the overlap area and redundant searches.
Important Links:
Go Back
