# Pruning Optimization over Threshold-Based Historical Continuous Query
## 4 Pruning Optimization
### Extended MBR Overlap Based Pruning Strategy
**_Given a drtree node \(N_{d}\) and a query trajectory \(T_{q}\), a distance threshold \(d\), if \(M(N_{d})\cap M(R(T_{q},d))=\varnothing\), then \(N_{d}\) must not contain data related to the query results, and it should be pruned._  
Pruning strategy 1 does not involve complex calculations, so it can effectively reduce computational overhead. However, \(M(R(T_{q},d))\) increases the coverage area compared to \(R(T_{q},d)\), for such a _drtree_ node whose MBR overlaps with \(M(R(T_{q},d))\) but does not overlap with \(R(T_{q},d)\), Pruning strategy 1 cannot prune it. For example, in Figure 4, Pruning strategy 1 cannot prune the node \(N_{d}\). Therefore, the candidate set generated by using Pruning strategy 1 may contain more irrelevant candidates, which increases the processing overhead of refinement to some extent. To overcome this problem, an intuitive method is to further check the _drtree_ node that has passed the check of Pruning strategy 1 by calculating Mindist. However, as mentioned earlier, Mindist calculation requires a lot of CPU time and should be avoided during the pruning process. In this regard, we consider the property to be one or more rectangular areas that are fully covered by \(R(T_{q},d)\), if \(M(N_{d})\) overlaps with any of them, then \(Mindist(M(N_{d}),M(T_{q}))\leq d\). Further, to ensure the pruning effect, these rectangular areas should fully cover \(M(T_{q})\). Such a rectangular spatial area can be obtained by expanding the spatial range of each dimension of \(M(T_{q})\) by using \(d\). Assuming that the coordinates of the lower left corner and the upper right corner of \(M(T_{q})\) are \((x_{q1},y_{q1})\) and \((x_{q2},y_{q2})\), respectively. Therefore, the coordinates of the lower left corner and upper right corner of \(M_{1}(T_{q},d)\) are \((x_{q1}-d,y_{q1})\) and \((x_{q2}+d,y_{q2})\), and the coordinates of the lower left corner and upper right corner of \(M_{2}(T_{q},d)\) are \((x_{q1},y_{q1}-d)\) and \((x_{q2},y_{q2}+d)\). It is easy to know that \(M_{1}(T_{q},d)\) and \(M_{2}(T_{q},d)\) are fully covered by \(R(T_{q},d)\), and \(M(T_{q})\) is fully covered by them. Hence, we obtain Pruning strategy 2. **Pruning strategy 2. **_Given a query trajectory \(T_{q}\), a distance threshold \(d\), a drtree node \(N_{d}\) which has passed the check by Pruning strategy 1. If \((M(N_{d})\cap M_{1}(T_{q},d))\cup(M(N_{d})\cap M_{2}(T_{q},d))\
eq\varnothing\), then the value of Mindist between \(M(N_{d})\) and \(M(T_{q})\) is not greater than \(d\). Otherwise, we should calculate \(Mindist(M(N_{d}),M(T_{q}))\) to determine whether pruning \(N_{d}\)._  
For example, in Figure 4, nodes \(N_{3}\) and \(N_{5}\) overlap with \(M_{1}(T_{q},d)\), they need not be pruned, while nodes \(N_{2}\) and \(N_{4}\) do not overlap with \(M_{1}(T_{q},d)\) and \(M_{2}(T_{q},d)\), and it is necessary to further calculate the value of Mindist to decide whether pruning \(N_{2}\) and \(N_{4}\). Figure 4: Example of extended MBR overlap based pruning strategy. In summary, we name this method which combines Pruning strategy 1 and Pruning strategy 2 as Extended MBR overlap based pruning strategy (EMOB pruning strategy), Algorithm 1 gives its detailed flow. This algorithm is triggered when traversing each _drtree_ node \(N_{d}\). If the return value is true, then \(N_{d}\) should not be pruned. Otherwise, \(N_{d}\) should be pruned. The general flow of the algorithm is as follows:  
1. The algorithm first determines whether the time interval of \(N_{d}\) overlaps with the time interval of \(T_{q}\). If there is overlap between the two, the algorithm will perform the next step, and return false otherwise (line 1 to 3). 2. Whether \(M(N_{d})\) overlaps with \(M(R(T_{q},d))\) is checked. If any exist, the algorithm will continue to the next step. Otherwise, the false is returned (line 4 to 6). 3. The algorithm judges whether \(M(N_{d})\) overlaps with \(M_{1}(T_{q},d)\) or \(M_{2}(T_{q},d)\). If no overlaps exist, the next step will be performed. Otherwise true is returned (line 7 to 9). 4.