# The SSP-Tree: A Method for Distributed Processing of Range Monitoring Queries in Road Networks
## 3 The Proposed Method
### The Segment-Based Space Partitioning Tree (SSP-Tree)
#### 3.2.1 Description
Assuming \(\theta=3\), Figure 6 shows an example of the SSP-tree built on two queries \(q_{1}\) and \(q_{2}\) in the road network \(G\) in Figure 2a, where the original query segments of \(q_{1}\) and \(q_{2}\) are \(\{qs[v_{5},v_{6}],qs[v_{6},p_{1}],qs[v_{6},p_{8}]\}\) (\(=QR(q_{1})\)) and \(\{qs[v_{5},p_{2}],qs[v_{5},p_{3}],qs[v_{5},p_{5}]\}\) (\(=QR(q_{2})\)), respectively. To track each query \(q\) and its query segments (including the original query segments and the newly generated query segments), the server maintains the _Query Relevance Table_ (QRT). We say that a query \(q\) is _relevant_ to a query segment \(qs\) or vice versa if \(qs\) belongs to \(QR(q)\) (i.e., \(qs\in QR(q)\)). For example, in Figure 6, the query \(q_{1}\) is relevant to the query segments \(qs[v_{5},p_{4}]\), \(qs[v_{6},p_{1}]\), \(qs[v_{6},p_{6}]\), \(qs[v_{6},p_{7}]\), and \(qs[p_{7},p_{8}]\). On the other hand, the query \(q_{2}\) is relevant to the query segments \(qs[v_{5},p_{2}]\), \(qs[v_{5},p_{3}]\), \(qs[v_{5},p_{4}]\), and \(qs[p_{4},p_{5}]\). A query segment \(qs\) can have more than one relevant queries. For example, \(qs[v_{5},p_{4}]\) is relevant to both \(q_{1}\) and \(q_{2}\). Each row of QRT is a tuple of the form \((qs,qid\_list)\)  
Figure 5: Simple intersection relationships between \(qs\) and \(N\). (**a**) \(qs\) is inside \(N\) or \(N\) contains \(qs\); (**b**) \(qs\) partially intersects \(N\) or vice versa; (**c**) \(qs\) fully intersects \(N\) or vice versa. indexed by \(qs\), where \(qs\) is a _distinct_ query segment and \(qid\_list\) is a list that stores the identifiers of the queries that are relevant to \(qs\). The server also maintains the _Segment Relevance Table_ (_SRT_) to identify the relevance between each original query segment \(qs\) and the newly generated query segments. Similarly to the above, we say that an original query segment \(qs\) is relevant to a newly generated query segment \(q\)s or vice versa if \(q\)s is split from \(qs\). For example, in Figure 6, the original query segment \(qs[v_{5},v_{6}]\) is relevant to the newly generated query segments \(qs[v_{5},p_{4}]\) and \(qs[v_{6},p_{6}]\), while the original query segment \(qs[v_{5},p_{5}]\) is relevant to the newly generated query segments \(qs[v_{5},p_{4}]\) and \(qs[p_{4},p_{5}]\). It is important to note that in contrast to the original query segments that partially intersect a node \(N\) of the SSP-tree, the original query segments that fully intersect \(N\) are not split but stored in \(N.FL\). For example, the query segment \(qs[p_{4},p_{6}]\) is not generated because \(qs[v_{5},v_{6}]\) fully intersects the tree node \(N_{221}\); instead, \(qs[v_{5},v_{6}]\) is stored in \(N_{211}.FL\). A newly generated query segment \(q\)s can have more than one relevant original query segments. For example, \(qs[v_{5},p_{4}]\) is relevant to both \(qs[v_{5},v_{6}]\) and \(qs[v_{5},p_{5}]\). Each row of SRT is a tuple of the form \((qs,qs\_list)\) indexed by \(q\)s, where \(q\)s is a distinct newly generated query segment and \(qs\_list\) is a list that stores the original query segments that are relevant to \(q\)s.  
Given a (leaf or non-leaf) node \(N\) of the SSP-tree and a moving object \(o\), \(N\) can become a candidate for \(o\)'s vicinity region if \(N\) contains (i) \(o.p\) and (ii) \(N.C\leq o.cap\). In this connection, the first advantage of maintaining \(N.FL\) at each node \(N\) is that the server can assign a larger (but still appropriate) vicinity region to each moving object \(o\) than not maintaining it. This is because each query segment \(qs\) that fully intersects \(N\) does not lead to the generation of a new query segment \(qs\cap N\), and thus the value of \(N.C\) is not increased. Assuming \(o\) is assigned \(N\) as its vicinity region, the second advantage is that \(o\) can reduce the number of sending unnecessary UpdateResult messages to the server because \(qs\cap N\) is not generated and assigned to \(o\). Here, it should be validated that \(qs\cap N\) need not be assigned to \(o\).