# The SSP-Tree: A Method for Distributed Processing of Range Monitoring Queries in Road Networks
## 6 Related Work
[PERSON] and [PERSON] extended [26] for processing monitoring queries in the road network [7]. These methods assume that moving objects periodically send location-updates to the server. The server, meanwhile, continually (i) receives the location-update stream; (ii) determines the queries that are affected by the movements of the objects; and (iii) updates their results if necessary. However, constant location-updates generated by a huge number of moving objects may incur significant communication bottleneck and greatly increase the overhead at the server for determining the affected queries and keeping their results up to date. In addition, because the transmission of a location-update message over a wireless connection takes a substantial amount of energy, the handheld device carried by each moving object exhausts its battery life quickly. To help each moving object reduce the number of sending location-updates to the server, the _safe region_ method was proposed in [4; 5]. The safe region, assigned to each moving object \(o\), is the area that (i) contains the point of \(o\)'s current location and (ii) guarantees that the current results of all the queries will remain valid as long as \(o\) does not leave it. Therefore, \(o\) need not send a location-update to the server as long as it does not leave its safe region. Although the safe region method improves the overall system performance to a certain degree, because the size of a safe region assigned to each object \(o\) is typically small, \(o\) easily leaves its current safe region and contacts the server in order to receive a new safe region. Recently, the distributed methods, namely the _Monitoring Query Management (MQM)_ method [2] and the _Query Region-tree (QR-tree)_ method [3] were proposed. Unfortunately, these distributed methods only deal with the objects moving freely in Euclidean space. Focusing on processing moving monitoring queries over static objects, the safe region methods were also proposed in [8; 9]. Similarly to the safe region assigned to a moving object, the safe region assigned to a query \(q\) is the region that (i) contains \(q.p\) and (ii) guarantees that while \(q.p\) remains inside it, the result of \(q\) remain unchanged. More recently, several algorithms were proposed to compute the _safe exits_ of a query \(q\) in the road network [10; 11; 12]. Safe exits are a set of points that guarantee the result of \(q\) remains unchanged before \(q.p\) reaches any of these points. There were also proposed methods for processing moving monitoring queries over moving objects in the road network [13; 14]. [PERSON] et al. proposed the _Incremental Monitoring Algorithm_ (_IMA_) and the _Group Monitoring Algorithm_ (_GMA_) [13]. IMA is based on NE [20], while GMA extends IMA with the shared execution paradigm. [PERSON] and [PERSON] proposed the distributed method that utilizes the computational capabilities of moving objects [14]. However, this method is not comparable to our proposed method (i.e., DM\({}_{\text{(SSP-tree)}}\)) because it assumes that there is no restriction on the number of queries the server can assign to moving objects. Specifically, in this method, although the number of queries a moving object \(o\) can process is at most \(n\), the server can assign \(o\) more than \(n\) queries. On the other hand, in our proposed method, the server must assign \(o\) no more than \(n\) query segments.