# 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.3 SSP-Tree Manipulations
If \(flag\) is not set, SplitNode checks for each of \(qs\)'s relevant original query segments \(\
ot\)s fully intersects \(\dot{N}_{new}\). If so, SplitNode inserts \(\
ot\)s into \(\dot{N}_{new}\).\(FL\) (lines 18-19). Otherwise, similarly to the former case, SplitNode inserts a tuple \((qs\cap\dot{N}_{new},flag)\) into \(\dot{N}_{new}\) and increases \(\dot{N}_{new}\).C by 1 only when \((\
ot\)s \(\cap\dot{N}_{new},flag)\) is not already stored in \(\dot{N}_{new}\) (lines 20-21). In case that \(\
ot\)s partially intersects \(\dot{N}_{new}\), SplitNode additionally updates QT, QRT, and SRT (lines 22-23). Then, SplitNode sets \(N_{new}\).C to \((N_{left}\).C + \(N_{right}\).C) and increases \(\dot{N}\).C of each node \(\dot{N}\) in the path from \(N_{new}\)'s parent to the root by \((N_{new}\).C - \(N\).C) (lines 24-28). Finally, SplitNode discards \(N\) (line 29). This split process propagates downward if necessary (lines 30-31). ```
1:create two new empty leaf nodes \(N_{left}\) and \(N_{right}\);
2:create a new empty non-leaf node \(N_{new}\);
3:insert entries \((ptr,N_{left})\) and \((ptr,N_{right})\) into \(N_{new}\);
4:insert all the query segments stored in \(N\).\(FL\) into \(N_{left}\).\(FL\), \(N_{right}\).\(FL\), and \(N_{new}\).\(FL\);
5:find the entry \((ptr,N)\) stored in \(N\)'s parent and redirect \(ptr\) to point to \(N_{new}\);
6:for each entry \((ptr,\dot{N}_{new})\) stored in \(N_{new}\)do//\(\dot{N}_{new}:N_{left}\) or \(N_{right}\)
7:for each tuple \((qs,flag)\) stored in \(N\)do
8:ifqs intersects \(\dot{N}_{new}\)then//ifqs is inside, partially intersects, or fully intersects \(\dot{N}_{new}\)
9:if\(flag\) is set then
10:ifqs fully intersects \(\dot{N}_{new}\)then
11:insert \(qs\) into \(N_{new}\).\(FL\);
12:else//ifqs is inside or partially intersects \(\dot{N}_{new}\)
13:insert a tuple \((qs\cap\dot{N}_{new},flag)\) into \(\dot{N}_{new}\) and increase \(\dot{N}_{new}\).C by 1 if it is not stored in \(\dot{N}_{new}\);
14:ifqs partially intersects \(\dot{N}_{new}\)then
15:update QT, QRT, and SRT;
16:else//\(flag\) is not set
17:for each \(qs\)'s relevant original query segment \(\
ot\)s \(\in\)\(\
ot\)s\(\_list\) of the tuple \((qs,\)\(\
ot\)s\(\_list)\) in SRT do
18:ifqs fully intersects \(\dot{N}_{new}\)then
19: insert \(\
ot\)s into \(\dot{N}_{new}\).\(FL\);
20:else//ifqs is inside or partially intersects \(\dot{N}_{new}\)
21:insert a tuple \((qs\cap\dot{N}_{new},flag)\) into \(\dot{N}_{new}\) and increase \(\dot{N}_{new}\).C by 1 if it is not stored in \(\dot{N}_{new}\);
22:if\(\
ot\)s partially intersects \(\dot{N}_{new}\)then
23:update QT, QRT, and SRT;
24:set \(N_{new}\).C to \((N_{left}\).C + \(N_{right}\).C);
25:repeat
26:set \(\dot{N}\) to \(N_{new}\)'s parent;
27:increase \(\dot{N}\).C by \((N_{new}\).C - \(N\).C);
28:until (\(\dot{N}\) is the root)
29: discard \(N\);
30:for each entry \((ptr,\dot{N}_{new})\) stored in \(N_{new}\)do//\(\dot{N}_{new}:N_{left}\) or \(N_{right}\)
31:SplitNode(\(N_{new}\)) if \(N_{new}\).C \(>\)\(\theta\);
```  
**Algorithm 4****SplitNode(\(N\))**  
Algorithm 5 is the pseudocode of the delete algorithm Delete. Given an original query segment \(qs\) of a query \(q\), Delete first updates QRT (line 1). Then, Delete follows the paths of the SSP-tree, each of which consists of non-leaf and leaf nodes with which \(qs\) intersects. At a non-leaf node \(N\) in each path, Delete checks if \(qs\) fully intersects \(N\). If so, Delete deletes \(qs\) from \(N\).\(FL\) (lines 3-4). When reaching a leaf node \(N\) in this path, Delete checks the intersection relationships between \(qs\) and \(N\). Then, according to three cases, Delete proceeds as follows:1. If \(qs\) fully intersects \(N\), Delete \(qs\) from \(N.FL\) (lines 10-11). 2. If \(qs\) is inside \(N\) (i.e., \(qs\cap N=qs\)), Delete deletes the tuple \((qs\cap N,flag)\) from \(N\) and decreases \(N.C\) by 1 if \(q\) is the only relevant query of \(qs\cap N\) (lines 12-14). 3. If \(qs\) partially intersects \(N\), Delete updates QRT and SRT (line 16).