# Pruning Optimization over Threshold-Based Historical Continuous Query
## 4 Pruning Optimization
### Best-First Traversal Algorithm
The pseudo code of the function TRA-Q(\(FPQ\), \(fe_{1}\), \(d\)) is shown in Algorithm 3. * Case 2 (At least one of \(fe_{1}.h_{q}\) and \(se_{1}.h_{d}\) is not 0, and \(fe_{1}.h_{q}<se_{1}.h_{d}\)): The child nodes of \(se_{1}.N_{d}\) are traversed by the function TRA-D(\(FPQ\), \(fe_{1}\), \(d\)), and the pruning check is performed when each child node is accessed (lines 14 to 15). The pseudo code of the function TRA-D(\(FPQ\), \(fe_{1}\), \(d\)) is shown in Algorithm 4. * Case 3 (Both of \(fe_{1}.h_{q}\) and \(se_{1}.h_{d}\) are 0): Namely both of \(fe_{1}.N_{q}\) and \(se_{1}.N_{d}\) are the trajectory segments. Moreover, according to the ordering rule of SecPQ, the _drtree_ node of any S-entry in \(fe_{1}.SPQ\) is also a trajectory segment and is a candidate of \(fe_{1}.N_{q}\). Therefore, \(fe_{1}\) can be regarded as a pruning result and added to \(Ps\) (line 16 to 17). ```
Input: Query Trajectory \(T_{q}\), distance threshold \(d\), _drtree_; Output: Pruning results \(Ps\);
1 _qrtree_\(\leftarrow\)Create an E3 DR-tree for trajectory \(T_{q}\);
2 _SPQ_\(\leftarrow\)initialize an instance of SecPQ;
3 _FPQ_\(\leftarrow\)initialize an instance of FirstPQ;
4 \(N_{d}\)\(\leftarrow\)Root(_drtree_);
5 \(N_{q}\)\(\leftarrow\)Root(_qrtree_);
6 ifEMOB(\(N_{d}\), \(N_{q}\), \(d\))=true then
7 _SPQ_.enqueue((\(N_{d}\), \(H(N_{d})\), \(TS(N_{d})\)));
8 _FPQ_.enqueue((\(N_{q}\), \(H(N_{q})\), \(TS(N_{q})\), \(SPQ\)));
9 while\(FPQ\
eq\varnothing\)do
10 \(fe_{1}\)\(\leftarrow\)\(FPQ\).dequeue();
11 \(se_{1}\)\(\leftarrow\)\(fe_{1}.SPQ\).getFirst();
12 if\((fe_{1}.h_{q}\
eq 0\lor se_{1}.h_{d}\
eq 0)\land(fe_{1}.h_{q}\geq se_{1}.h_{d})\)then
13 TRA-Q(\(FPQ\), \(fe_{1}\), \(d\));
14 **else if\((fe_{1}.h_{q}\
eq 0\lor se_{1}.h_{d}\
eq 0)\land(fe_{1}.h_{q}<se_{1}.h_{d})\)then**
15 TRA-D(\(FPQ\), \(fe_{1}\), \(d\));
16 **else if\(fe_{1}.h_{q}=0\land se_{1}.h_{d}=0\)then**
17 _Ps_.add(\(fe_{1}\));
18 endif
19 endwhile
20 endif
21 returnPs;
```  
**Algorithm 2**Best-First Traversal Algorithm  
In the function TRA-Q(\(FPQ\), \(fe_{1}\), \(d\)), for each child node \(C_{q}\) of the node \(fe_{1}.N_{q}\), the following processing is performed:  
1. Initialize a SecPQ \(CSPQ\) (line 2);
2. Loop read each S-entry of \(fe_{1}.SPQ\) (without dequeuing), let \(cse\) be the current read S-entry if \(cse.N_{d}\) is not pruned, then \(cse\) is inserted into \(CSPQ\) (lines 3 to 7). 3. Create a new F-entry for \(C_{q}\) by using the relevant parameters and insert it into \(FPQ\) (line 8). ```
Input: FirstPQ \(FPQ\), F-entry \(fe_{1}\), distance threshold \(d\); Output: Null;
1 foreach child node \(C_{q}\) of \(fe_{1}\).\(N_{q}\)do
2\(CSPQ\)= initialize an instance of SecPQ;
3 foreach entry \(cse\) of \(fe_{1}\).\(SPQ\)do
4 ifEMOB(\(cse\).\(N_{d}\), \(C_{q}\), \(d\))=true then
5\(CSPQ\).enqueue(\(cse\));
6 endif
7 endfor
8\(FPQ\).enqueue(\(C_{q}\), \(H(C_{q})\), \(TS(C_{q})\), \(CSPQ\)));
9 endfor
```  
**Algorithm 3** TRA-Q(\(FPQ\), \(fe_{1}\), \(d\))  
with \(ti_{c}\) (naming the overlap time Interval as \(ti_{o}\)), then the moving object \(l_{d}\)_.oid_ is a query result of \(ti_{o}\). After all the data of \(Ps\) is processed, all the query results are returned to the user, and the query ends.