Article Preview
TopIntroduction
With the rapid development of wireless technology and the ubiquity of portable devices, Location-Based Service (LBS) (Lu et al., 2011; Usman et al., 2018; Zhu et al., 2017) is playing an increasingly important role in our daily life, such as navigation system (Win et al., 2011; Kawamata & Oku, 2019), location-based recommendation (Park et al., 2007; Ye et al., 2010) and traffic congestion prediction (Xu et al., 2020). As the primary data source for LBS, spatial-temporal data is known for its vital timeliness, which means its value decays quickly over time. Therefore, providing LBS-RT (Location Based Service in a real-time manner) by processing spatial-temporal data in real-time has become a hot topic.
Range query is a basic operation in LBS, and its function is to find all objects in a specified area. Spatial indexes are often used to speed up range query. Similarly, spatial indexes are often used in LBS-RT, and the following example of LBS-RT requires a spatial index. During a parade, the government monitors the size of the crowd in real-time to match the level of security measures. The crowd size can be accurately calculated by clustering the trajectory data generated in the last N minutes. The system needs to update the crowd size regularly to ensure timeliness. Trajectory clustering requires a large number of trajectory similarity searches. Many frameworks (Xie et al., 2017; Shang et al., 2018) that perform similarity search in a large trajectory set require a spatial index to speed up similarity search. LBS-RT only analyzes the data generated in the last N minutes. In Figure 1, those applications often use a sliding time window (Chen et al., 2019) to maintain data. Every time the window slides, outdated items slide out the time window, such as the two items at 9:02 and 9:03, new items slide into it, such as the two items at 9:31 and 9:34. Therefore, the index in LBS-RT needs to perform a lot of update operations.
R-tree (Guttman et al., 1984) and its variants (Leutenegger et al., 1997; A. Fu et al., 2000; Zhou et al., 2008; Kamel et al., 1994; Ciaccia et al., 1997; Y. Fu et al., 2003; Beckmann et al., 1990; Zaschke et al., 2014; Jung et al., 2014; Phan et al., 2017; Amaral et al., 2016; Xiong & Aref, 2006) are commonly used spatial indexes. Most variants are designed to improve the retrieval performance of R-tree, such as STR-tree (Leutenegger et al., 1997), VP-tree (A. Fu et al., 2000), KD-tree (Zhou et al., 2008), Hilbert-tree (Kamel et al., 1994), M-tree (Ciaccia et al., 1997), QR-tree (Y. Fu et al., 2003), R-star-tree (Beckmann et al., 1990) and PH-tree (Zaschke et al., 2014). These indexes don’t pay attention to improving update performance. Although some works (Zhang. F et al., 2014; Jo & Jung, 2018) use distributed methods to maintain index for improving update performance, they don’t reduce the resource consumption.