Wavelet Tree based Dual Indexing Technique
for Geographical Search
Arun Kumar Yadav1
and Divakar Yadav2
1Department of Computer
Science and Engineering, Ajay Kumar Garg Engineering College, India
2Department of
Computer Science and Engineering, Madan Mohan Malaviya University of Technology, India
Abstract:
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.
Keywords: Information
retrieval, wavelet tree, spatial search, indexing, Minimum bounding rectangles.
Received May 28, 2016; accepted May 1, 2017