Location Based Hybrid Indexing Structure - R k-d Tree

Location based spatial object selection and searching is emerging as an important search paradigm in indexing of multimedia database systems. The technique used is to map the objects as points into a two dimensional space which is indexed using a multidimensional data structure. Although several data structures have been proposed for location and spatial indexing, none of them is known to index points in both overlapping and non-overlapping regions in an optimum query retrieval time. This paper introduces the hybrid tree - a multidimensional data structure for indexing two dimensional location spaces. Unlike other multidimensional data structures, the hybrid tree cannot be classified as either a pure data partitioning (DP) index structure (e.g., R-tree, SS-tree, SR tree) or a pure space partitioning (SP) one (e.g., KD tree, hB tree);rather, it “combines” positive aspects of the two types of index structures a single data structure to achieve search performance is increased by a time complexity of O (nlog(log n)) than either of the above techniques (hence, the name “hybrid”). Our experiments on “real” distributed large size spatial databases demonstrate that the fan out is independent of dimensionality and enables fast intra node search. It significantly outperforms purely k-d tree space partitioning and R-tree data partitioning-based index mechanisms as well as linear scan at all dimensionalities for large sized databases.