# Pruning Optimization over Threshold-Based Historical Continuous Query
## 4 Pruning Optimization
### Best-First Traversal Algorithm  
We designed a best-first traversal algorithm that traverses _drtree_ and _qrtree_ simultaneously to handle the pruning process. Compared to the pruning method that traverses _drtree_ alone, it can generate an accurate result with accessing fewer nodes. Its basic principle is to select the accessed objects of the next iteration according to the heights of the accessed _drtree_ node and the _qrtree_ node. As the number of iterations increases, the pruning precision continues to rise, a set of candidate trajectory segments is eventually generated for each trajectory segment of \(T_{q}\). To support the best-first traversal algorithm, we use a first priority queue (FirstPQ) and multiple secondary priority queues (SecPQ) to record the intermediate results during the traversal process [18]. FirstPQ is used to control the traversal order of the _qrtree_ nodes, and SecPQ is used to control the traversal of the _drtree_ nodes. First, the data structures of FirstPQ entry (F-entry) and SecPQ entry (S-entry) are introduced. **Definition 3**. : _Attributes of each F-entry \((N_{q},h_{q},t_{q},SPQ)\) are described as follows:_  
1. _Node_ \(N_{q}\)_--a_ _qrtree node, which can be an index node or a trajectory segment;_
2. _Height_ \(h_{q}\)_--the height from_ \(N_{q}\) _to the trajectory segment layer of_ _qrtree. if_ \(h_{q}=0\)_, then_ \(N_{q}\) _is a trajectory segment. In addition, the F-entries in a FirstPQ are sorted by_ \(h_{q}\) _value (largest to smallest)._
3. _Timestamp_ \(t_{q}\)_--the starting timestamp of the time interval of_ \(N_{q}\)_. In addition,_ \(t_{q}\) _is the secondary keyword for sorting F-entries, when two F-entries have the same_ \(h_{q}\) _value, they are sorted by_ \(t_{q}\) _value (smallest to largest)._
4. _SecPQ_ \(SPQ\)_--a_ _SecPQ_ _that records the_ _qrtree nodes which pass the pruning check with_ \(N_{q}\)_._  
**Definition 4**. : _Attributes of each S-entry \((N_{d},h_{d},t_{d})\) are described as follows:_  
1. _Node_ \(N_{d}\)_--a_ _qrtree node, which can be an index node or a trajectory segment;_
2. _Height_ \(h_{d}\)_--the height from_ \(N_{d}\) _to the trajectory segment layer of_ _drtree. if_ \(h_{d}=0\)_, then_ \(N_{d}\) _is a trajectory segment. In addition, the S-entries in a SecPQ are sorted by_ \(h_{d}\) _value (largest to smallest)._
3. _Timestamp_ \(t_{d}\)_--the starting timestamp of the time interval of_ \(N_{d}\)_. In addition,_ \(t_{d}\) _is the secondary keyword for sorting S-entries, when two S-entries have the same_ \(h_{d}\) _value, they are sorted by_ \(t_{d}\) _value (smallest to largest)._  
Algorithm 2 gives its detailed flow of the best first traversal algorithm, it is divided into two steps of initialization (lines 1 to 8) and iteration (lines 9 to 19) and using a collection \(Ps\) to collect all pruning results. In the initialization step, an E3 DR tree _qrtree_ is first created for the query trajectory \(T_{q}\) (line 1). A SecPQ \(SPQ\) and a FirstPQ \(FPQ\) are then initialized (lines 2 to 3). Next, the root nodes of _qrtree_ and _drtree_ are obtained, and the pruning check is performed. If the root node of _drtree_ is not be pruned, an S-entry and an F-entry are created and inserted in \(SPQ\) and \(FPQ\), respectively. Otherwise, the algorithm ends (lines 4 to 8). For each iteration of the while loop, the first F-entry \(fe_{1}\) is dequeued from \(FPQ\), and the head S-entry \(se_{1}\) of the \(fe_{1}.SPQ\) is also checked without dequeuing (lines 10 to 11). Based on the values of \(fe_{1}.h_{q}\) and \(se.h_{d}\), a decision is made whether to traverse _qrtree_, to traverse _drtree_ or to add a pruning result to \(Ps\), the processing of the three cases are as follows:* Case 1 (At least one of \(fe_{1}.h_{q}\) and \(se_{1}.h_{d}\) is not 0, and \(fe_{1}.h_{q}\geq se_{1}.h_{d}\). ): The child nodes of \(fe_{1}.N_{q}\) are traversed by the function TRA-Q(\(FPQ\), \(fe_{1}\), \(d\)), and when each child node is accessed, the pruning check is performed for the _drtree_ node of each S-entry in \(fe_{1}.SPQ\) (lines 12 to 13).