# 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
Then, it deletes the tuple \((qs\cap N,flag)\) from \(N\) and decrease \(N.C\) by 1 if \(qs\) is the only relevant original query segment of \(qs\cap N\) (lines 17-18). If the tuple \((qs\cap N,flag)\) is deleted from \(N\), Delete decreases \(\bar{N}.C\) of each node \(\bar{N}\) in the path from its parent to the root by 1 (lines 20-23). Finally, Delete invokes the merge algorithm MergeNode, which takes \(N\)'s parent as an input, to condense the tree if possible (line 24). ```
1:update QRT;
2:if\(N\) is a non-leaf node then
3:if\(qs\) fully intersects \(N\)then
4: delete \(qs\) from \(N.FL\);
5:else\(//\) if \(qs\) is inside or partially intersects \(N\)
6:for each entry \((ptr,\bar{N})\) stored in \(N\)do
7:if\(qs\) intersects \(\bar{N}\)then\(//\) if \(qs\) is inside, partially intersects, or fully intersects \(\bar{N}\)
8:Delete(\(\bar{N}\), \(qs\));
9:else\(//\) if \(N\) is a leaf node
10:if\(qs\) fully intersects \(N\)then
11: delete \(qs\) from \(N.FL\);
12:elseif\(qs\) is inside \(N\)then\(//\) if \(qs\cap N=qs\)
13:if\(q\) is the only relevant query of \(qs\cap N\) (\(=qs\))then
14: delete the tuple \((qs\cap N,flag)\) from \(N\) and decrease \(N.C\) by 1;
15:else\(//\) if \(qs\) partially intersects \(N\)
16: update QRT and SRT;
17:if\(qs\) is the only relevant original query segment of \(qs\cap N\)then
18: delete the tuple \((qs\cap N,flag)\) from \(N\) and decrease \(N.C\) by 1;
19:if the tuple \((qs\cap N,flag)\) is deleted from \(N\)then
20:repeat
21: set \(\bar{N}\) to \(N\)'s parent;
22: decrease \(\bar{N}.C\) by 1;
23:until (\(\bar{N}\) is the root)
24:MergeNode(\(N\)'s parent);
```  
**Algorithm 5****Delete(\(N\), \(qs\))**  
Algorithm 6****MergeNode(\(N\))  
Algorithm 6 is the pseudocode of MergeNode. Given a non-leaf node \(N\), MergeNode first checks if (i) \(N.C\leq\theta\) and (ii) both of \(N\)'s children are leaf nodes. If so, MergeNode creates a new empty leaf node \(N_{new}\), inserts all the original query segments stored in \(N.FL\) into \(N_{new}.FL\), and sets \(N_{new}.C\) to \(N.C\) (lines 2-4). Next, MergeNode finds the entry \((ptr,N)\) stored in \(N\)'s parent to redirect \(ptr\) to point to \(N_{new}\) (line 5). Now, \(N\)'s parent becomes \(N_{new}\)'s parent. Then, MergeNode inserts all the distinct tuples stored in each \(N\)'s child \(\hat{N}\) into \(N_{new}\) (lines 6-8). Finally, MergeNode discards \(N\) and its children (line 9). This merge process propagates upward until the node that does not satisfy the merge condition is reached (line 10). Now, we analyze the time costs of the SSP-tree manipulations in Lemma 5. For the simplicity of analysis, we assume (i) that each query segment is not redundantly stored in two leaf nodes; and (ii) that the SSP-tree is perfectly balanced, and thus its depth is \(\log_{2}(\frac{|QS_{set}|}{\theta})\), where \(|QS_{set}|\) denotes the total number of query segments stored in the leaf nodes. In addition, the number of original query segments \(\textit{qs\_list}\) of each tuple \((qs,\textit{qs\_list})\) in SRT is assumed to be almost same. **Lemma 5**. : _Let \(t_{insert}\), \(t_{split}\), \(t_{delete}\), and \(t_{merge}\) be the time costs of insert, split, delete, and merge operations, respectively. Then, \(t_{insert}\approx\alpha_{1}\log_{2}(\frac{|QS_{set}|}{\theta})+\alpha_{2}\log_{ 2}(\frac{|QS_{set}|}{\theta})\), \(t_{split}\approx 2\cdot\alpha_{3}(\theta+1)\cdot|\textit{qs\_list}|+\alpha_{4} \log_{2}(\frac{|QS_{set}|}{\theta})\), \(t_{delete}\approx\alpha_{5}\log_{2}(\frac{|QS_{set}|}{\theta})+\alpha_{6}\log _{2}(\frac{|QS_{set}|}{\theta})\), and \(t_{merge}\approx\alpha_{7}\theta\), where \(\alpha_{1}\), \(\alpha_{2}\),..., \(\alpha_{7}\) are constants._  
Proof.