# A Distributed Indexing Method for Timeline Similarity Query
## 2 Timeline's Representation and Similarity Function  
A timeline composed of a sequence of interval event data. Therefore, a timeline is a set of intervals with labels. Consider the timeline _China_ in Figure 2; it is made up of three intervals:  
\(I1=[1279,1368]\), and the label is [PERSON] dynasty, and the attachment data is a historical e-book of [PERSON] dynasty. \(I2=[1368,1644]\), and the label is [PERSON] dynasty, and the attachment data a historical e-book of Ming dynasty. \(I3=[1644,1911]\), and the label is [PERSON] dynasty, and the attachment data a historical e-book of Qing dynasty. Generally, a timeline can be represented as follow:  
\[T=[ID,<\!\!I0,L0,D0\!\!>,<\!\!I1,L1,D1\!\!>,<\!\!I2,L2,D2\!\!>,\ldots,<\!\!Ij,Lj,Dj\!\!>,\ldots\,\ldots\,<\!\!Ik,Lk,Dk\!\!>];\]  
in which \(T\) is a timeline, \(k+1\) is the number of intervals in timeline \(T\). \(ID\) is the identifier of the timeline \(T\). \(lj\) is an interval, \(Lj\) is a label, \(Dj\) is an attachment data of the interval, \(<\!\!Ij,Lj,Dj\!\!>\) is a three-dimensional tuple, and \(0\leq j\leq k\). An interval represents a range of values. In general, each interval in a timeline can be described in a uniform:  
\[[T_{idt},I_{idt},I_{s},I_{e},I_{t},I_{l},I_{d}],I_{Min}\leq I_{s}\leq I_{e} \leq I_{Max},\]  
in which \(I_{Max}\) is the maximum value of the intervals, \(I_{Min}\) is the minimum value of the intervals, \(T_{id}\) is the identifier of the timeline that the interval belongs to, \(I_{id}\) is the identifier of the interval, here it is the order in a timeline, \(I_{s}\) is the starting of interval, \(I_{e}\) is the ending of interval, \(I_{t}\) is the type of the interval, \(I_{l}\) is the label of the interval, and \(I_{d}\) is the attachment data of the interval shown in Table 1.  
If an interval represents a two-dimensional (2D) point value, its type must be IT_CLOSED, and \(I_{s}=I_{e}\). An interval can be described as a point in a 2D plane, as shown in Figure 4[9]. The axis \(S\) is the starting value of the interval, and axis \(E\) is the ending value of the interval. Because \(I_{e}\) is always larger than or equal to \(I_{s}\), the region below the line \(NP\) is always empty in the two-dimensional space. This offers the possibility for reducing the query computation by skipping the empty region. Our previous work [9] described 15 distinct algebra relationships between two intervals. Each of the 15 interval algebra relationships can be represented as a point, line, and region in the 2D space. If the universal interval is [\(I_{s}\), \(I_{e}\)], and the input interval of a query is [\(Q_{s}\), \(Q_{e}\)], we can represent the relationships of two interval objects in two-dimensional space, as defined in Table 2. \begin{table}
\begin{tabular}{c c} \hline
**Interval Type** & **Expression** \\ \hline IT\_CLOSED & \([I_{s},I_{e}]\) \\ IT\_LEFTOPEN & \((I_{s},I_{e}]\) \\ IT\_RIGHTOPEN & \([I_{s},I_{e})\) \\ IT\_OPEN & \((I_{s},I_{e})\) \\ \hline \end{tabular}
\end{table} 
Table 1: Interval types. Theoretically, every query of timeline can be transformed into a set of interval operators [9]. For example, assume that we want to find the timeline which is most like the timeline \(S\) in Figure 3, and we employ the summary of the overlaps with same labels of the intervals to evaluate the similarity. The bigger the overlaps of same labels are, the more similar they are. Given a timeline \(T\), the similarity between \(T\) and \(S\) can be calculated by the formula (in the form of functional programming):  
\[\text{similarity }(T,S)=\text{cartesian }(T,S).\text{filter}(L^{T}==L^{S}).\text{ map }(\text{overlaps }(I^{T},IS)).\text{ reduce }( + \_) \tag{1}\]  
Here, the function _cartesian_ converts the timelines \(T\) and \(S\) into two intervals sets and calculates the cartesian product of the two interval sets. The result of the function _cartesian_ is a pair set of intervals. The function _filter_ filters out all the pairs whose \(L^{T}\) (Label of an interval in \(T\)) is not equal \(L^{S}\) (Label of an interval in \(S\)).