# The SSP-Tree: A Method for Distributed Processing of Range Monitoring Queries in Road Networks
## 6 Related Work  
Most of the early researches on spatial databases assumed the static objects in Euclidean space and focused on (i) developing efficient spatial access methods (e.g., the R-tree [17] and its variants [18; 19]) and (ii) processing of snapshot queries, which retrieves the results of queries only once at a specific snapshot in time. [PERSON] et al. incorporated the road network into the existing spatial databases and proposed two basic methods for processing several types of snapshot queries (e.g., range queries, nearest neighbor queries, spatial join queries, and closest pair queries) in the road network [20]. The first method is the _Euclidean Restriction_ (_ER_). ER first identify the candidate objects  
Figure 11: Construction time of the SSP-tree and CPU-time consumed by a moving object. (**a**) Construction time of the SSP-tree vs. the number of queries; (**b**) The amount of CPU-time consumed by a moving object in DM\({}_{\text{(SSP-tree)}}\) vs. the minimum computational capability; all other parameters have their default values (see the values stated in boldface in Table 2). by their Euclidean distance from the query point, after which it discards the false positives based on their network distances from the query point. The second method is the _Network Expansion (NE)_, which performs the search directly from the query point by gradually expanding the nearby vertices in the order of their network distances from the query point. Both ER and NE use the R-tree to speed up query processing. [PERSON] et al. proposed the _G-tree_, a hierarchy structure, for processing nearest neighbor queries in the road network [21]. Assuming only the broadcast communication is available, [PERSON] et al. proposed the _Network Partition Index (NPI)_ for processing range queries and nearest neighbor queries in the road network [22]. Later on, the focus was extended to indexing moving objects. Assuming that the trajectories of moving objects are known a priori or predictable, [PERSON] et al. proposed the _Time-Parameterized R-tree (TPR-tree)_ for indexing moving objects, where the location of each moving object is transformed into a linear function of time [23]. [PERSON] et al. proposed the improved version of the TPR-tree, called the _TPR\({}^{*}\)-tree_, which uses the exactly same data structure as the TPR-tree but applies new insert and delete algorithms [24]. However, the known-trajectory assumption does not hold for most real-life application scenarios (e.g., the velocity of a typical customer on the road are frequently changed), which leads those index structures to become prohibitively expensive to update. To deal with a large number of moving objects that move arbitrarily, [PERSON] et al. proposed a generalized bottom-up update strategy for the R-tree [25]. [PERSON] and [PERSON] introduced the dual index design for snapshot range queries over moving objects in the road network, which utilizes the R-tree to index the road network and the in-memory grid structure to index the points of moving objects' location [26]. Motivated by LBSs, another research direction has recently focused on processing monitoring queries. Many methods for monitoring queries have been proposed, which can be broadly classified into two categories according to the mobility of query points and objects. The first category focuses on static queries over moving objects, and the second category deals with moving queries over static/moving objects. Because our work belongs to the first category, we elaborate on the review of the representative methods in the first category and briefly review the methods in the second category. Indexing queries, instead of indexing frequently moving objects, has been considered to be an attractive strategy, which reduces the server computation cost for updating index structures because monitoring queries remain active for a long period of time and are static. [PERSON] et al. suggested to use the R-tree to index queries [5], while [PERSON] et al. used the in-memory grid structure [6].