# Pruning Optimization over Threshold-Based Historical Continuous Query
## 3 Background  
The real trajectory of the moving object is a continuous curve in space and time, but the sampling and storage of the trajectory data are carried out in discrete form, this is because the sensor device can only collect and send discrete samples. For example, a taxi equipped with a GPS device reports its position information every 10 s. The discrete position samples of a moving object constitute an ordered sequence of segments. When the sampling frequency is high enough, this sequence of segments can be relatively accurately approximated to the real trajectory of the moving object. Therefore, we used a segment-based data model to represent the trajectory of a moving object, defined as follows:  
**Definition 1**. : _The trajectory \(T\) of a moving object contains a sequence of trajectory segments (\(l_{1}\), \(l_{2}\),..., \(l_{M}\)) arranged chronologically. Each trajectory segment \(l\) records the linear motion of a moving object in a time interval, which can be expressed as \(l=\{\mathit{oid},p_{s},p_{e},t_{s},t_{e}\}\), \((t_{s}\leq t_{e})\), where \(\mathit{oid}\) is the identifier of the moving object and it can represent the moving object, \(p_{s}\) and \(p_{e}\) respectively represent the spatial position of the moving object at time instance \(t_{s}\) and \(t_{e}\)._  
According to the data model of trajectory described in Definition 1, the spatial position of the moving object at a certain historical time instance can be obtained by linear interpolation. In the two-dimensional Euclidean space, given a trajectory segment \(l=\{\mathit{oid},p_{s},p_{e},t_{s},t_{e}\}\), the spatial coordinates of \(p_{s}\) and \(p_{e}\) are expressed as \(p_{s}=(q_{s1},q_{s2})\) and \(p_{e}=(q_{e1},q_{e2})\), let \(loc(t,\mathit{oid})\) represent the spatial position of \(\mathit{oid}\) at the time instance \(t\), and \(loc_{k}(t,\mathit{oid})\) denote the \(k\)-th dimension coordinate of \(loc(t,\mathit{oid})\). For any time instance \(t\) in the time interval \([t_{s},t_{e}]\), We compute the value of \(loc_{k}(t,\mathit{oid})\) as  
\[loc_{k}(t,\mathit{oid})=\left\{ \begin{array}{ll}\frac{q_{s}-q_{s}}{t_{e}-t_{ s}}(t-t_{s})+q_{sk}&t_{s}<t_{e}\\ q_{sk}&t_{s}=t_{e}\end{array} \right.. \tag{1}\]  
Using Formula (1), we can calculate the spatial positions of two moving objects at a timestamp, and then obtain the distance between them. In this paper, we used Euclidean distance as the distance metric, let \(d(loc(t,\mathit{oid}_{1}),loc(t,\mathit{oid}_{2}))\) denote the distance between \(\mathit{oid}_{1}\) and \(\mathit{oid}_{2}\) in the time instance \(t\), according to the Euclidean distance formula  
\[d(loc(t,\mathit{oid}_{1}),loc(t,\mathit{oid}_{2}))=\sqrt{\sum_{k=1}^{2}{(loc_ {k}(t,\mathit{oid}_{1})-loc_{k}(t,\mathit{oid}_{2}))}^{2}}. \tag{2}\]  
In the two query requests listed in Section 1, the stationary object can be taken as a moving object that stays in a spatial position, so a uniform query definition can be given. **Definition 2**. : _Given a moving object \(\mathit{oid}_{q}\), a moving object database \(D\), a time interval \([t_{sq},t_{eq}]\), a distance threshold \(d\), the historical trajectory \(T_{q}\) of \(\mathit{oid}_{q}\) in \([t_{sq},t_{eq}]\), the threshold-based historical continuous query return a collection of query results \(R\)s, the element re of \(R\)s is expressed as a tuple (\(t\)i, oids), where \(t\) is a time interval, and oids is a set of moving objects. \(R\)s satisfies the following two conditions: (1) Given two elements \(re_{1},re_{2}\in Rs\), such that \(re_{1}.t\cap re_{2}.t\)i = \(\varnothing\) and \(re_{1}.t\)i, \(re_{2}.ti\subseteq[t_{sq},t_{eq}]\). (2) Given an element \(re_{1}\in Rs\), a time instance \(t_{1}\in re_{1}.ti\), a moving object \(\mathit{oid}_{1}\in re_{1}.\mathit{oids}\), such that \(d(loc(t_{1},\mathit{oid}_{1}),loc(t_{1},\mathit{oid}_{q}))\leq d\)._With other words, the time intervals of different Rs elements do not overlap, and the time interval of any Rs element must be within the query time interval.