Article Preview
TopIntroduction
The rapid development of mobile devices has produced many location-based services, and an increasing number of online objects have both spatial and textual properties. For example, social services such as Twitter and Foursquare allow users to send their tweets with location; navigation services such as Google Maps and Baidu Map allow users to search for points of interest nearby. These applications require efficient spatio-textual indexes to support numerous spatial keyword queries.
There are three common spatial keyword queries: Boolean range query (BRQ), Boolean kNN query (BkQ) and the top-k kNN query (TkQ) (Chen et al., 2013). This paper focuses on BRQ, which is fundamental to many spatial textual applications (Salgado et al., 2018; Tampakis et al., 2021; Wang et al., 2021; Wang et al., 2020). Given a collection of spatio-textual data, a spatial keyword query 
(comprising a spatial region 
and a set of keywords 
), BRQ aims to find all objects, each of which is in 
and contains all keywords in 
.
In Figure 1, a user may want to find a restaurant in a certain area (query region in a dashed rectangle) that sells hamburgers and coffee (query keywords) together. He can issue his query to a BRQ server and obtain point 1 as the returned result. Although points 3 and 4 are also in this area, they do not contain all the query keywords. For example, P2 sells hamburgers and coffee together, but they are too far away.
The spatial keyword index is the heart of an efficient spatial keyword query. We can consider it a spatial and textual index combination, either in a space-first or text-first way. Based on the spatial indexes used, existing studies can be R-tree-based, grid-based, and space-filling curve-based. From the textual perspective, we can also classify these studies into inverted index-based and bitmap-based studies. Chen et al. (2013) experimentally evaluated 12 spatial-textual indexes, such as IR-Tree (Wu et al., 2012b), WIBR-Tree (Wu et al., 2012a), and SFC-Quad (Christoforaki et al., 2011), and the results show that SFC-Quad performs the best both in query time and space on BRQ.
The excellent performance of SFC-Quad is because of the simple core structure: an inverted index ordered by space-filling curves. The objects in each inverted list are sorted according to the Z-curve order, so the objects close in the original space are as close as possible in the inverted lists, thus leading to a better query performance.
Although many studies followed the study by Chen et al. (2013) into BRQ, most turn to in-memory or streaming data spatial keyword query (Chen et al., 2017; Mahmood et al., 2018), collaborative spatial keyword query (Zhao et al., 2017), semantic spatial keyword query (Qian et al., 2018; Sun et al., 2017), privacy-preserving spatial keyword query (Cui et al., 2019; Su et al., 2015), and spatial keyword query on road network (Han et al., 2015; Zheng et al., 2016). We can see from recent surveys (Chen et al., 2020; Chen et al., 2021) that SFC-Quad is still the best representative in disk-based BRQ algorithms.