# Pruning Optimization over Threshold-Based Historical Continuous Query
## 4 Pruning Optimization
### Extended MBR Overlap Based Pruning Strategy  
Given a _drtree_ node \(N_{d}\), for \(N_{d}\) and query trajectory \(T_{q}\), the basic pruning strategy consists of the following two steps:  
1. Check whether the time interval of \(N_{d}\) overlaps with the time interval of \(T_{q}\), if \(TS(N_{d})\cap TS(T_{q})=\varnothing\), then \(N_{d}\) should be pruned. 2. Determine whether the Mindist between the MBR of \(N_{d}\) and the MBR of \(T_{q}\) is not greater than the distance threshold \(d\), if \(\textit{Mindist}(M(N_{d}),M(T_{q}))>d\), then \(N_{d}\) should be pruned. In the step (2) of the basic pruning strategy, although the Mindist-based method can effectively exclude the trajectory data that does not satisfy the query conditions, its calculation process is complicated and requires a lot of CPU time. When calculating the value of Mindist between \(M(N_{d})\) and \(M(T_{q})\), it first determines whether \(M(N_{d})\) is overlapped with \(M(T_{q})\), if so, then the value of Mindist is 0. Otherwise, it needs to calculate the minimum distance from any edge of \(M(N_{d})\) to \(M(T_{q})\), and chooses the minimum value as the value of Mindist, namely computing the MBR-to-MBR Mindist requires four times of Mindist calculations between a line segment and a rectangle. Moreover, a segment-to-rectangle Mindist calculation is subdivided into six times of distance calculations. As shown in Figure 3, when calculating the minimum distance between the line segment \(L\) and the rectangle \(M\), it is necessary to calculate two Mindists from each vertex of \(L\) to \(M\) and four Mindists from each vertex of \(M\) to \(L\), and then select the minimum value among them as the result. Hence, if \(M(N_{d})\) does not overlap with \(M(T_{q})\), 24 times of distance calculations are needed to get the value of Mindist between \(M(N_{d})\) and \(M(T_{q})\). Obviously, the cost of calculating Mindist between two MBRs is expensive, and if the computational cost can be optimized, the query efficiency can be significantly improved. In the process of calculating Mindist, it can be noticed that the cost for checking whether two MBRs overlap is much smaller than the multiple distance calculation, which only needs to compare the spatial positional relationship between the MBR vertices. Suppose the spatial coordinates of the lower left and upper right corners of \(M(N_{d})\) are \((x_{d1},y_{d1})\) and \((x_{d2},y_{d2})\), the spatial coordinates of the lower left and upper right corners of \(M(T_{q})\) are \((x_{q1},y_{q1})\) and \((x_{q2},y_{q2})\), if the result of Discriminant (3) is true, then \(M(N_{d})\) is overlapped with \(M(T_{q})\). Taking advantage of the low overhead of overlapping calculation, we propose a pruning strategy based on extended MBR overlap to optimize the computational overhead. \[!(((x_{d2}<x_{q1})\vee(y_{d1}>y_{q2}))\vee((x_{q2}<x_{d1})\vee(y_{q1}>y_{d2}))). \tag{3}\]  
First, we use the distance threshold \(d\) to extend the spatial range of \(M(T_{q})\). In the two-dimensional Euclidean space, we can get a coverage area \(R(T_{q},d)\) shaped as a rounded rectangle. It is easy to know that if the MBR of a _drtree_ node overlaps with \(R(T_{q},d)\), then the Mindist between it and \(M(T_{q})\) is no larger than \(d\). However, since the coverage area of \(R(T_{q},d)\) is not a rectangular area, determining whether \(M(T_{q})\) overlaps with \(R(T_{q},d)\) cannot be based only on the spatial positional  
Figure 3: The Mindist between a line segment and a rectangle. relationship between the vertices, and additional calculations are required. With this in mind, we use the circumscribed rectangle \(M(R(T_{q},d))\) of \(R(T_{q},d)\) to approximate \(R(T_{q},d)\), if \(M(N_{d})\) does not overlap with \(M(R(T_{q},d))\), then it also does not overlap with \(R(T_{q},d)\). Hence, we summarize the Pruning strategy 1. **Pruning strategy 1.