# A Distributed Indexing Method for Timeline Similarity Query
## 3 Distributed Triangle Increment Tree (DTI-Tree)
### The Strategy of Partition  
To manage interval data, we convert the interval object into a two-dimensional (2D) point in a 2D plane, as shown in Figure 4, and assume that all the interval points are in the basic triangle _OEM_ shown in Figure 7a. The line _OM_ is a segment in line _NP_ shown in Figure 4. For the convenience of computing, we make _OEM_ to be an isosceles right-angled triangle. To construct a binary tree indexing data objects, a recursive decomposition of the triangle is implemented. If the maximum number of interval points that a leaf triangle can contain is \(N\) = 2, then it is a recursive binary decomposition that all the leaf triangles will be decomposed recursively until each number of the interval points in a leaf triangle is less than \(N\). Then, the decomposition will construct a binary tree shown in Figure 7b. This is the partition strategy that TD-Tree [8] used, we called it TD-tree's partition strategy (TDPS).  
Figure 6: Distributed Triangle Increment Tree (DTI-Tree) system architecture.  
Figure 7: TD-tree’s partition strategy (TDPS) and triangle binary tree. (**a**) TD-Tree’s triangle decomposition; (**b**) Triangle binary tree with codes.  
The TDPS leads to a limitation that the range of interval dataset must be evaluated before index creation. That is, the minimum and maximum values of the original intervals should be known. It is easy for a small and static dataset, but not for a big or dynamic dataset. A tentative solution is to give a range that is as large as possible. However, it will result in another problem that the TD-Tree's node identifier may overflow. Because the identifier is an integer that is represented by a binary string, the length of the binary string may be larger than 32 bits or 64 bits when the data set is very large. It is no longer easy to use an integer to represent a node's identifier. All the benefits of using an integer as an identifier will disappear.  
Hence, we design a partition strategy, called triangle increment partition strategy (TIPS), which is extended from TDPS. The only difference between TIPS and TDPS is that the root triangle area can be increased when the inserting interval point is out of the scope of the root triangle in the TIPS, while the TDPS cannot. That is, the TIPS compose of a triangle increment process and a decomposition process. The decomposition process is the same as the TDPS when the inserting interval points are in the root triangle.  
Here, we only show that increment process. The process consists of a left extension procedure and a right extension. Assume that there is an isosceles right-angled triangle \(ABC\) called _initial triangle_ or _root triangle_, and \(BC\) is always on the line \(NP\) (Figure 4). If there is an interval point located at the left of line \(AB\), the left extension of \(ABC\) will be executed and results in a new isosceles right-angle root triangle \(GKC\), as shown in Figure 7(a). If there is a point located above the line \(AC\), then the right extension of \(ABC\) will be carried out and it will result in a new isosceles right-angle root triangle \(DBE\), as shown in Figure 7(b). The TIPS is the basic ideas of the indexing method, TI-Tree, used as local index on slave node presented in this paper. The TIPS algorithm shown in Algorithm 1.  
```
Input:\(pi\): an interval [\(l_{s}\), \(l_{e}\)]: root node of TI-Tree or T-Tree; Output:\(root\): the new root node {
1. read the _root_ node from disk;
2. if(\(root\_triangle\) contains \(pi\)) return \(root\);
3. if(pi is located at the left of line \(AB\))  executes left extension shown in Figure 7(a); else  executes right extension shown in Figure 7(b);
4. while(\(root\_triangle\) does not contain \(pi\))  call Algorithm 1 recursively;
5. return\(root\); }
```  
**Algorithm 1**Tips  
Figure 8: Extensions of the triangle \(ABC\) for TIPS. **(a)** Left extension; **(b)** Right extension.