An efficient approach for approximate keyword query in geographic information system

Spatial-Keyword (SK) queries, which are queries on spatial objects associated with textual attributes, have received significant attention in geographic information system (GIS) recently. Many hybrid index structures have been proposed to answer SK queries. To the best of our knowledge, however, few of them are adequate to handle approximate keyword matching in space database efficiently. This means they are not error-tolerant for users. In this paper we propose a novel approach for Approximate SK queries—ASK queries, whose motivation is to find the spatial objects with their textual attributes similar to the user-specified keyword and their locations satisfied with the regional requirement. To do so, a 3-level hybrid index structure is introduced. This structure combines R*-tree and inverted lists with the q-grams of the keywords of the objects. R*-tree partitions the objects as well as regional q-grams, which are the qgrams of the keywords of the objects assigned to a leaf node of the R*-tree. Moreover, the regional q-grams are index by inverted lists whose entries are the objects associated with the regional q-gram. Based on the 3-level structure, we give an algorithm for ASK query. Experiments show our approach is efficient because of the reduction of search space.