Wavelet Tree based Dual Indexing Technique for Geographical Search

Today's information retrieval systems are facing new challenges in indexing the massive geographical information available on internet. Though in past, solutions for it, based on R-tree family and B-tree has been given, but due to increased size of index, they are found to be less efficient and time consuming. This paper presents a dual indexing technique for Geographical Information Retrieval. It uses wavelet tree data structure for both, textual and spatial indexing. It also allows dynamic insertion of Minimum Bounding Rectangle (MBR) in the wavelet tree during index construction. The proposed technique has been evaluated in terms of efficiency and time complexity. For pure spatial indexing, using this technique, the search time complexity is reduced and takes even less than one third time of that of spatial indexing performed using R-tree or R*-tree. Even in case of dual indexing (textual and spatial) using wavelet tree, the search time is reduced by half in comparison to other techniques such as B/R, B/R* when the search query length is larger than 2 keywords. In case the query is of 1 or 2 keywords, the search time remains approximately similar to that of other techniques.