I. Introduction
In recent years, many researchers focus their sparked enthusiasm on spatial keyword query [1]–[8], [16], and massive commercial applications provide the corresponding services. For example, the Google Maps and Foursquare enable the spatial keyword queries to help users search their interested information in a specific region. A typical spatial keyword query is boolean spatial keyword queries [4]–[7], which takes both the spatial range condition and keyword condition into account. Fig. 1 presents an example to show a boolean spatial keyword query Q with the ‘red rectangle’ as the spatial condition , and ‘hospital’ as the keyword condition . Suppose there are eight objects O1, ..., O8 in the spatio-textual dataset D. Each object has the spatial coordinates (i.e., latitude and longitude) and a keyword set (e.g., text description). So O7 will be returned as the result of the query as O7 locates in and its keyword set covers altogether.