# A Resilient Large-Scale Trajectory Index for Cloud-Based Moving Object Applications
## 3 Resilient Moving Object Index
### Index Construction  
Algorithm 1 outlines the fundamental steps for RMOI construction, which consists of four main stages: prediction, partitioning, building the local index, and building the global index. However, \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Dataset** & **Trajectories** & **GPS Points** & **Ellipsoid Area** & **Data Type** & **Moving Object Class** \\ \hline GT & 163 K & 132 M & 636,408 km\({}^{2}\) & real & mixed \\ UK + IE & 149 K & 179 M & 937,586 km\({}^{2}\) & real & mixed \\ RioBuses & 296 K & 114 M & 6588 km\({}^{2}\) & real & 1 \\ SF & 140 K & 119 M & 10,721 km\({}^{2}\) & generated & 20 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Moving object trajectory datasets used in training and evaluation. As seen in Algorithm 1, the driver node starts by reading the given trajectory dataset \(T\), on space \(S\), into Spark RDD. Then, it generates \(ST\subset T\) as a sample set, which can fit in the driver node's memory? For sampling, we use the Spark built-in function with replacement to capture the trajectories' characteristics. After that, RMOI computes the features ComR, MemR, and TOver based on Equations (1)-(3), respectively. The required parameters to conduct the computation of the feature are already given when initializing the cluster. These include executor number, cores number, executor memory size, and more. The time and space complexity to compute the features are dominated by the TOver, which is \(O(s^{\prime}+m^{\prime})\), where \(s^{\prime}=|ST|\) and \(m^{\prime}\) is the number of \(Traj\in ST\). After computing the necessary parameters, the prediction stage is started. As seen in Line 3, RMOI needs to determine whether to go with the compulsory or with the discrete prediction. In the case of compulsory prediction, Line 28, RMOI transfers the features into a vector of polynomial features with degree 2. After that, RMOI carries out the computation to predict \(LP\) as follows,  
\[LP=\ \left|\ \sum_{i=1}^{n}\text{{Coeff}}_{i}\times P_{i}\right|\ \, \tag{5}\]  
where \(P\) is the set of the polynomial features, and \(n\) is the vector size. However, in the case of discrete prediction (Line 32), RMOI needs the Query Frequency Table (QFT), which consists of Query Type (QT) and its Frequency (Freq). QFT could be dynamically collected from previous runs until it is needed, or the end-user could provide it. After transferring the features into a vector of polynomial features with degree 3, RMOI predicts the best locality pivot (\(LP_{1}\)) and the second best (\(LP_{2}\)) for every QT in QFT. While it loops over QTs, RMOI also predicts the query impact factor (ifFactor). Then, it updates the Freq of the associated QT based on its own iFactor, as in Line 40. All the models conduct the prediction computations, per Equation (5), on the transferred features and the corresponding vectors of the stored regression coefficients. The prediction results are rounded, except for iFactor. Next, RMOI accumulates the Freqs of different QTs that have the same \(LPs\). In cases where there is an identical Freq for different QTs, it returns the \(LP_{1}\) that is equal to the \(LP_{2}\) of the other QT. Otherwise, it returns the \(LP_{1}\) of the highest Freq. Finally, all the returned \(LPs\) from CPModel or DPModel are converted into \(\alpha\) and \(\beta\) based on Equation (4). The complexity of the prediction stage is constant, as the size of the polynomial vector and QFT are fixed. After the prediction stage, RMOI enters the partitioning stage, which consists of two steps: space splitting and hashing. On the driver node, when \(LP\
eq 1\), RMOI builds a binary skeleton tree (SK-tree) on \(ST\), shown in Line 8. The SK-tree is similar to k-d-B-tree [7] in the way it is constructed, but it is a lightweight tree which is only used to represent the required sub-regions (i.e., the required \(\alpha\) spatial group). SK-tree only contains \(\alpha\) leaf nodes. Each leaf node has a \(\text{{LeafNodeID}}\in\{0,\ \beta,\ 2\beta,\ 3\beta,\ \ldots,\ tpn-\beta\}\).