# 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  
The SSP-tree can be manipulated with a set of algorithms, which specify how a query segment is inserted into and deleted from the SSP-tree, and how overflow or underflow of a SSP-tree node is managed. ```
1:update QT and QRT;
2:if\(N\) is a non-leaf node then
3:ifqs fully intersects \(N\)then
4:insertqs into \(N.FL\);
5:for each entry \((ptr,N)\) stored in \(N\)do
6:ifqs intersects \(N\)then// ifqs is inside, partially intersects, or fully intersects \(N\)
7:Insert(\(N\),qs);
8:else\(//\) if\(N\) is a leaf node
9:ifqs fully intersects \(N\)then
10:insertqs into \(N.FL\);
11:else// ifqs is inside or partially intersects \(N\)
12:if the tuple \((qs\cap N,flag)\) is not already stored in \(N\)then
13:insert a tuple \((qs\cap N,flag)\) into \(N\) and increases \(N.C\) by 1;
14:ifqs partially intersects \(N\)then
15:update QT, QRT, and SRT;
16:repeat
17:set \(\tilde{N}\) to \(N\)'s parent;
18:increase \(\tilde{N}.C\) by 1;
19:until(\(\tilde{N}\) is the root)
20:if\(N.C>\theta\)then
21:SplitNode(\(N\));
```  
**Algorithm 3**Insert(\(N\),qs)  
Algorithm 3 is the pseudocode of the insert algorithm Insert. Given an original query segment \(qs\) of a query \(q\), Insert first updates QT and QRT (line 1). Then, Insert recursively 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, Insert checks if \(qs\) fully intersects \(N\). If so, Insert inserts \(qs\) into \(N.FL\) (lines 3-4). When reaching a leaf node \(N\) in the path, Insert checks if \(qs\) fully intersects \(N\). If this is the case, Insert inserts \(qs\) into \(N.FL\) (lines 9-10). On the other hand, if \(qs\) is inside or partially intersects \(N\), Insert inserts a new tuple \((qs\cap N,flag)\) into \(N\) and increases \(N.C\) by 1 only when it is not already stored in \(N\) (lines 12-13). Here, if \(qs\) is inside \(N\), i.e., \(qs\cap N=qs\), \(flag\) is set. In case that \(qs\) partially intersects \(N\), Insert additionally updates QT, QRT, and SRT (lines 14-15). Finally, Insert increases \(\tilde{N}.C\) of each node \(\tilde{N}\) in the path from \(N\)'s parent to the root by 1 (lines 16-19). When \(N\) overflows (i.e., \(N.C>\theta\)), Insert invokes the split algorithm SplitNode (lines 20-21). Algorithm 4 is the pseudocode of SplitNode. Given an overflowed leaf node \(N\), SplitNode creates (i) two new empty leaf nodes \(N_{left}\) and \(N_{right}\), and (ii) a new non-leaf node \(N_{new}\) that stores entries \((ptr,N_{left})\) and \((ptr,N_{right})\), where \(N_{left}\) or \(N_{right}\) represents one of the equal halves of \(N\) (lines 1-3). Now, \(N_{left}\) and \(N_{right}\) become \(N_{new}\)'s children. Next, SplitNode inserts all the query segments stored in \(N.FL\) (i.e., all the original query segments that fully intersect \(N\)) into \(N_{left}.FL\), \(N_{right}.FL\), and \(N_{new}.FL\), after which it finds the entry \((ptr,N)\) stored in \(N\)'s parent to redirect \(ptr\) to point to \(N_{new}\) (lines 4-5). Now, \(N\)'s parent becomes \(N_{new}\)'s parent. Then, SplitNode checks for each tuple \((qs,flag)\) stored in \(N\) if \(qs\) intersects each of \(N_{new}\)'s children \(\tilde{N}_{new}\). (Note: For the ease of description, we use \(\tilde{N}_{new}\) to denote both \(N_{left}\) and \(N_{right}\) when necessary.) If so, according to two cases, SplitNode proceeds as follows:  
1. If \(flag\) is set, indicating that \(qs\) is the original query segment, SplitNode checks if \(qs\) fully intersects \(\tilde{N}_{new}\). If so, SplitNode inserts \(qs\) into \(\tilde{N}_{new}\) (lines 10-11). Otherwise, SplitNode inserts a tuple \((qs\cap\tilde{N}_{new},flag)\) into \(\tilde{N}_{new}\) and increases \(\tilde{N}_{new}.C\) by 1 only when\((qs\cap\dot{N}_{new},flag)\) is not already stored in \(\dot{N}_{new}\) (lines 12-13). In case that \(qs\) partially intersects \(\dot{N}_{new}\), SplitNode additionally updates QT, QRT, and SRT (lines 14-15). 2.