# A Resilient Large-Scale Trajectory Index for Cloud-Based Moving Object Applications
## 3 Resilient Moving Object Index
### Index Construction
Next, the driver node broadcasts SK-tree to each worker on the cluster and launches a Map transformation to tag each \(Seg\in T\), as shown in Line 9. Each worker traverses the SK-tree to tag each \(Seg\) as follows. \[Tag=\text{{LeafNodeID}}+(Seg.\text{{Tid\ mod\ }}\beta)\ . \tag{6}\]  
The \(Seg.Tag\) is essential as it represents the RDD partition id (\(Pid\)). The first term in Equation (6), _LeafNodeID_, acts as an offset for \(\alpha\) spatial groups where \(Seg.\text{{Tid\ mod\ }}\beta\) represents the object-based partitioning for each spatial group. In case of having a segment that does not fit in an SK-tree's leaf, the segment is split into two segments and then reinserted again. At the end, RMOI uses GroupBy transformation on the \(Seg.Tag\) to distribute \(Segs\) on new RDD partitions such that \(Seg.Tag=Pid\). Even though Algorithm 1 shows the general outlines of the partitioning stage, there is a special case when \(LP=1\). As mentioned before, this special case guarantees a full trajectory-preservation, which implies that the space-splitting is not needed. It does not require the construction of the SK-tree or the execution of the tagging procedure. Moreover, it combines the Map transformation and GroupBy transformation, Lines 9 and 12, whereas a GroupBy transformation only returns the result of \(Seg.\text{{Tid\ mod\ }}\beta\) as a key. There is no need for the _LeafNodeID_ offset, as there is only one spatial group. The first part of the partitioning stage is the construction of the SK-tree by the driver node. It has time complexity \(O(\log x^{\prime}(s^{\prime}\log s^{\prime}))\) and space complexity \(O(x^{\prime}+s^{\prime})\), where \(x^{\prime}\) is the number of nodes in the SK-tree (\(\approx\)2\(\alpha+1\)). The time complexity of the second part is \(O(s\log x^{\prime})\), where \(s=|T|\), as a result of the tagging and grouping procedures. However, they are carried out by the worker nodes which will parallelize the process over \(ExecCoreNum\times ExecNum\) processors. Parallelism processing is straightforward since there are no data dependencies. The space complexity is linear even though Spark uses immutable data structure. The next stage is building the local index (LocalRMOI). The data are already distributed over the cluster as RDD partitions. Each partition has a unique _Pid_ and an ArrayList of _Segs_. RMOI launches a MapPartitions transformation (Line 14), which slices the segments into intervals based on the segments' timestamps for each partition. Then, it builds STRtree by using the Sort-Tile-Recursive algorithm [35] for each interval (slice) such that STRtrees only contain the ArrayList indices. Each interval has direct access to the corresponding STRtree. After that, it collects the STRtrees' roots and continues to build the top part. Finally, it builds an interval B-tree [36] on the intervals. The time complexity to build a LocalRMOI is \(O(p\log p\log y)\), where \(p=|\)RDD partition\(|\) and \(y\) is the STRtree's node numbers. It is dominated by the STRtree construction complexity because \(p>|intervals|\). The space complexity is linear. There are \(tpn\) LocalRMOIs that will be built by \(ExecCoreNum\times ExecNum\) processors. In the final stage (Line 20), the driver node collects the overall interval, MBR, and _Pid_ from the roots of all the LocalRMOIs. After that, it checks whether the \(LP=1\) and proceeds to build the GlobalRMOI as an R-tree. Otherwise, it utilizes the SK-tree by reusing the tree hierarchy for the upper part. The lower part is built as R-tree, which contains the global nodes that do not exist in the SK-tree. If \(\beta<8\), then there is no need for the lower part. In general, the time complexity to build the GlobalRMOI is \(O(tpn\log tpn\log x)\), where \(x\) is the number of nodes of the GlobalRMOI. However, it reuses \(x^{\prime}\) nodes from SK-tree (\(x^{\prime}\leq x\)). The space complexity is also linear.