# Pruning Optimization over Threshold-Based Historical Continuous Query
## 2 Related Work  
At present, there are many studies on historical continuous query, in addition to threshold-based historical continuous query, it also includes k nearest neighbor historical continuous query.  
[PERSON] et al. [6] introduced a depth-first traversal algorithm to support \(k\) nearest neighbor history continuous query and proposes a new line-to-rectangular Mindist (minimum distance) calculation method [7] to improve pruning efficiency. Moreover, they apply the above method in the two index structures of TB-tree [8] and 3 DR-tree and verify the feasibility on the real and synthetic data sets.  
[PERSON] et al. [9] researched pruning optimization of \(k\) nearest neighbor historical continuous query. They propose an extended 3 DR-tree structure to quickly determine the number of candidate trajectories, design a time-based index named BB-tree to achieve high-precision pruning, and based on this, implement a breadth-first large-scale node traversal algorithm to efficiently obtain candidate trajectory data.  
[PERSON] et al. [10] conducted a study on threshold-based historical continuous query. In order to reduce the I/O overhead for query processing, they propose a memory-based R-tree structure to index the trajectory data and use a query algorithm based on MBR overlap to process the pruning and refinement. Compared to the first two studies, this study does not focus on the improvement of the algorithm but does a lot of experiments on real datasets to determine the appropriate parameters for the construction of memory-based R-tree. In addition, they also explore the parallelization of query based on OpenMP [11].  
[PERSON] et al. [12] propose a new threshold-based historical continuous query operation. For this query operation, a pruning method based on Mindist-Maxdist (minimum distance-maximum distance) and a refinement method based on dynamic time warping are introduced. In addition, this study also discusses the impact of trajectory segmentation on query and evaluates the performance of the query algorithm on the indexes of 3 DR-tree, TB-tree and SETI [13], respectively.  
With the rapid development of GPU technology, a series of methods [14; 15; 16] which use GPU to process the threshold-based historical continuous queries in parallel are proposed. On the one hand, considering that the GPU does not have branch prediction capabilities, these methods avoid using the tree-like structure to index the trajectory data, using the grid structure instead. On the other hand, considering that the GPU memory is limited, different from the snapshot queries taken by the above four methods, these methods divide the trajectory data contained in the mobile object database into multiple batches and iteratively process them.  
Aside from the GPU-based methods, the above methods have more or less the following shortcomings: (1) Calculating the values of Mindist or Maxdist requires high computational costs [6; 9; 12]. (2) During the pruning step, the pruning candidate set generated by taking the whole query trajectory as a whole is not accurate enough [6; 12]. Conversely, the pruning method that takes each segment of the query trajectory as a basic unit can obtain a more accurate candidate set, but the number of the accessed nodes is greatly increased [9; 10]. In response to these two shortcomings, we will discuss the solutions in detail later.