# THBase: A Coprocessor-Based Scheme for Big Trajectory Data Management
## 6 Query Processing Module
### k-NN Query  
The \(k\)-NN query is defined as follows: Given a time range \(\mathit{tr}_{\mathit{k}}\) and a spatial location \(q_{\mathit{k}}\), according to the selected distance function, the \(k\) trajectories are queried which are nearest to \(q_{\mathit{k}}\) within \(\mathit{tr}_{\mathit{k}}\). Here, the distance between a trajectory and \(q_{\mathit{k}}\) is computed as the distance from \(q_{\mathit{k}}\) to the nearest trajectory point. Existing \(k\)-NN spatial or spatiotemporal query algorithms do not support \(k\)-NN trajectory query well. Because they do not consider MOID attribute, some candidate elements may belong to the same MO, and it is time-consuming to merge and count the trajectories across nodes [26]. In THBase, we implement an Endpoint-based parallel \(k\)-NN query algorithm, which takes full advantage of the parallelism of HBase cluster and reduces the overhead caused by data transfer. Like spatiotemporal range query, we can also divide the \(k\)-NN query task into several independent subtasks, and each subtask can be independently performed through the Endpoint on the corresponding tRegion without cross-node communication. After the executions of all subtasks, we complete the global count task by the client. Here, we introduce the steps of a subtask in \(k\)-NN query as follows:  
1. Range-based pruning: We first query L-index by \(\mathit{tr}_{\mathit{k}}\) and an estimated spatial range \(\mathit{sr}_{\mathit{k}}\) (see Section 5.2 for query process in L-index). For the obtained candidate SE elements, we group them according to the MOID attribute, and obtain a set \(\mathit{sess}\) = {\(\mathit{sess}_{1}\), \(\mathit{sess}_{2}\),..., \(\mathit{sess}_{n}\)}, where each \(\mathit{sess}_{i}\) = {\(\mathit{se}_{i1}\),..., \(\mathit{se}_{im}\)} (1 \(\leq\)\(\mathit{I}\)\(\leq\)\(\mathit{n}\)) is a set of candidate SE elements of the same MO. 2. Pruning for the data of the same MO: Since only one point is generated as a result in the trajectory data of the same MO, we can prune those irrelevant \(\mathit{sess}_{j}\) (1 \(\leq\)\(\mathit{j}\)\(\leq\)\(\mathit{m}\)) elements in \(\mathit{sess}_{i}\) according to 1-NN query to further reduce the query range. On the abovementioned principle, we calculate the Mindist and MinMaxdist from the MBR of each \(\mathit{se}_{ij}\) to \(q_{\mathit{k}}\), and then select the minimum MinMaxdist (named as _mMMd_) and the minimum Mindist (named as _mMd_). Based on Lemma 1, if the Mindist of a \(\mathit{se}_{ij}\) is above _mMMd_, it should be removed from \(\mathit{sess}_{i}\). 3. Pruning for the data of different MOs: We first count the number of elements \(n_{k}\) contained in _sess_, namely, the number of candidate trajectories. If \(n_{k}\) is above \(k\), according to Lemma 1, we can remove such \(\textit{ses}_{i}\) element whose \(\textit{mMd}\) is greater than the \(k\)-th minimum \(\textit{mMMd}\). Finally, we extract rowkeys from _sess_ to get the ordered rowkey set \(\textit{ors}_{k}\) for querying the corresponding tRegion. 4. Distance calculation: At first, the tRegion is queried by the interested \(\textit{ors}_{k}\) to obtain trajectory points \(\textit{ps}_{k}\). After that, this Endpoint calculates the distance from each trajectory point in \(\textit{ps}_{k}\) to \(q_{k}\). For the trajectory points that belong to the same MO, the point with the smallest distance is selected. Finally the number of the selected trajectory points is counted; if it is above \(k\), only the first \(k\) minimum distances and their corresponding points are returned to the client. Here, we use \(\textit{lps}_{k}\) to represent the return results. **Lemma 1**.