# A Distributed Indexing Method for Timeline Similarity Query
## 4 The Structure of DTI-Tree
### The Construction of DTI-Tree  
The DTI-Tree construction is carried out by the Spark cluster. The DTI-Tree could be built in three phases: data partition, T-Tree construction and TI-Trees construction. The first phase is collaboratively executed in parallel in the Spark cluster, and the other two phases are separately executed on the slaves.  
According to Equation (4), a DTI-Tree has a global index, T-Tree, in the master node, and a series of TI-Trees in \(n\) slave nodes. Assume that \(TD\) is a timeline data set, the total number of timeline objects is \(TN\), \(T_{t}\) is a timeline in \(TD\) and \(t\in[0,TN-1]\). The first step of the data partition is to load the timeline data set from HDFS and to call the function _flapMap_ in Table 3 to execute a mapping from timeline data set to interval data set \(IDS\). Then, we get the minimum and maximum values of the interval data set \(IDS\) from the interval Spark Resilient Distributed Datasets (RDD) by calling the functions \(max\) and \(min\) in Table 3. A root triangle of the T-Tree will be set up on the base of the minimum value and maximum value by the algorithm that is presented in [9]. The root triangle will be partitioned into \(n\) sub triangles by the partition strategy that is mentioned in Section 3.1. Each sub triangle is related to a slave node. The last step is to call the function \(groupBy\) listed in Table 3 to form \(n\) groups according to the interval point location in a certain sub triangle. The main construction process is shown in Figure 10. The second phase is the construction of T-Tree according to the sub triangles. Its construction is simple because the T-Tree is an absolute binary search tree. The last phase is the constructions of TI-Trees. The TI-Tree is an extension of the TD-Tree's [8]. They share almost all the algorithms except the construction methods. The Algorithm 2 shows the process for constructing TI-Trees.  
```
Input:\(IDS\): an interval data set; Output: TI-Tree {
1. initial the root triangle variable root;
2.\(i=0\);
3.while(\(i<IDS\_size()\)) if(\(root\_triangle\_constains(IDS\) {\(i\)}))  call the TD-Tree's insertion procedure;  i++; else  call Algorithm 1;
4. return TI-Tree. }
```  
**Algorithm 2** TI-Tree construction  
The partition strategy that is used by the construction may result in skewing due to the unbalanced distribution of the interval points. A distributed index has a good balance when the standard deviation \(\sigma\leq 1\%\)[35]. The Equations (5) and (6) calculate the standard deviation by calling the function \(count\)  
Figure 10: DTI-Tree construction process.  
to return the number of interval points in slave \(S_{i}\). If the standard deviation \(\sigma\) is larger than the threshold given, the slave that has the maximum value of \(count(S_{i})\) should be partitioned into two parts, reconstruct two TI-Trees in the same slave node, and inform the T-Tree in the master node to adjust tree. The Algorithm 3 shows the construction method of the DTI-Tree.  
\[u=\frac{1}{n}\sum_{i=0}^{n-1}(count(S_{i})) \tag{5}\]  
\[\sigma=\sqrt{\frac{1}{n}\sum_{i=0}^{n-1}\left(count(S_{i})-u\right)^{2}} \tag{6}\]  
```
Input: TD: a timeline data set; Output: DTI-Tree {
1. IDS= flapMap(TD); // convert timeline set into interval set.
2 initialize and recursively binary split the root triangle by TIPS until the number of the leaf node triangle is equal to the number of all the slaves \(SN\) in the cluster;
3 call the function groupBy to split IDS into SN groups according to the leaf nodes' triangles generated in Step 2;
4 executes load balance evaluation and avoid adjustment after construction;
5 for each group, call Algorithm 2 to construct TI-Tree on the corresponding slave; }
```  
**Algorithm 3**DTI-Tree construction shown in Figure 10