# 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  
The SSP-tree is a hierarchical data structure that recursively splits the workspace into two subspaces. It is a binary tree, where each node \(N\) represents a subspace of the workspace, and \(N\)'s two children represent equal halves of this subspace. Hereafter, we say that a tree node \(N\) corresponds to a subspace or vice versa if \(N\) represents this subspace, and without ambiguity, we use the symbol '\(N\)' to denote both a tree node and its corresponding subspace. Given a set of query segments on the workspace that corresponds to the root, if the number of these query segments is greater than the split threshold \(\theta\) (i.e., the minimum number of query segments each moving object should process), the workspace is split into two subspaces, each of which corresponds to a child node \(N\) of the root. When a query segment \(qs\)_partially intersects_\(N\), it is also split into two query segments \(qs\cap N\) and \(qs-(qs\cap N)\) so that \(qs\cap N\) is _inside_\(N\). When necessary, we refer to each query segment computed by ComputeSeg (e.g., \(qs\) that partially intersects \(N\)) as the _original query segment_ for distinguishing it from the _newly generated query segments_ (e.g., \(qs\cap N\) and \(qs-(qs\cap N)\)). The process recursively continues until each node has no more than \(\theta\) query segments inside it. We define the simple intersection relationships between a query segment \(qs\) and a node \(N\) of the SSP-tree. **Definition 8**. : _Given a query segment \(qs[p_{a},p_{b}]\) and a node \(N\) of the SSP-tree, let \(qs[p_{a},p_{b}]^{\circ}\) be the interior of \(qs[p_{a},p_{b}]\) (i.e., \(qs[p_{a},p_{b}]^{\circ}=qs[p_{a},p_{b}]-\{p_{a},p_{b}\}\)). Then, there can be three relationships as follows:_  
* _Inside or contain relationship (see Figure_ 5_a): We say that_ \(qs[p_{a},p_{b}]\) _is_ _inside_ \(N\) _or_ \(N\) _contains_ \(qs[p_{a},p_{b}]\) _if_ \(qs[p_{a},p_{b}]\cap N=qs[p_{a},p_{b}]\)_._
* _Partially intersect relationship (see Figure_ 5_b): We say that_ \(qs[p_{a},p_{b}]\) _partially intersects_ \(N\) _or vice versa if_ \((qs[p_{a},p_{b}]\cap N\
eq qs[p_{a},p_{b}])\land(qs[p_{a},p_{b}]^{\circ}\cap N \
eq\emptyset)\land(\{p_{a},p_{b}\}\cap N\
eq\emptyset)\)_._
* _Fully intersect relationship (see Figure_ 5_c): We say that_ \(qs\) _fully intersects_ \(N\) _or vice versa if_ \((qs[p_{a},p_{b}]\cap N\
eq qs[p_{a},p_{b}])\land(qs[p_{a},p_{b}]^{\circ}\cap N \
eq\emptyset)\land(\{p_{a},p_{b}\}\cap N=\emptyset)\)_._  
Now, we describe the structure and properties of the SSP-tree. A leaf node of the SSP-tree stores at most \(\theta\) tuples of the form \((qs,flag)\), where \(qs\) is a query segment inside \(N\) and \(flag\) is a single bit that is set (i.e., logical 1) if \(qs\) is an original query segment. A non-leaf node stores two entries of the form \((ptr,N)\), where \(ptr\) is a pointer to a child node and \(N\) is a subspace that corresponds to the child node pointed to by \(ptr\). The SSP-tree satisfies the following properties:  
* A tuple \((qs,flag)\) is stored in a leaf node \(N\) if \(qs\) is inside \(N\). * A tuple \((qs,flag)\) can be redundantly stored in two leaf nodes if \(qs\) lies along the splitting line \(SL\) that separates these two leaf nodes (i.e., if \(qs\cap SL=qs\)). * For each entry \((ptr,\dot{N})\) stored in a non-leaf node \(N\), \(\dot{N}\) represents one of the equal halves of \(N\)'s subspace. * Each (leaf and non-leaf) node \(N\) maintains (i) a variable, called the _count variable_ (denoted by \(N.C\)), which records the total number of query segments inside \(N\), and (ii) a list, called the _full list_ (denoted by \(N.FL\)), which stores the original query segments that fully intersects \(N\).