# A Distributed Indexing Method for Timeline Similarity Query
###### Abstract  
Timelines have been used for centuries and have become more and more widely used with the development of social media in recent years. Every day, various smart phones and other instruments on the internet of things generate massive data related to time. Most of these data can be managed in the way of timelines. However, it is still a challenge to effectively and efficiently store, query, and process big timeline data, especially the instant recommendation based on timeline similarities. Most existing studies have focused on indexing spatial and interval datasets rather than the timeline dataset. In addition, many of them are designed for a centralized system. A timeline index structure adapting to parallel and distributed computation framework is in urgent need. In this research, we have defined the timeline similarity query and developed a novel timeline index in the distributed system, called the Distributed Triangle Increment Tree (DTI-Tree), to support the similarity query. The DTI-Tree consists of one T-Tree and one or more TI-Trees based on a triangle increment partition strategy with the Apache Spark. Furthermore, we have provided an open source timeline benchmark data generator, named TimelineGenerator, to generate various timeline test datasets for different conditions. The experiments for DTI-Tree's construction, insertion, deletion, and similarity queries have been executed on a cluster with two benchmark datasets that are generated by TimelineGenerator. The experimental results show that the DTI-tree provides an effective and efficient distributed index solution to big timeline data. timelines; interval data; DTI-tree; distributed index; timeline generator +
Footnote †: journal:  
0000-0001-9991-4000-0000-0000-0000-0000-0000-0000-0000-0000-0  
approxXimation (SAX) strategy of iSAX [2]. However, a timeline is often a set of interval objects with labels and data. It is often not continuous, but rather discrete and hard to be organized as SAX words. In addition, the data volume of the timelines mainly concentrates on their labels and attachment data. The labels indicate the type of intervals that are contained by the timeline. The data is an attachment of the labeled interval. The data may be text, image, or some other row binary data. As demonstrated in Figure 2, China, Japan, and Korea are long period historical timelines. Timelines can also be short. As shown in Figure 3, \(T1\), \(T2\), and \(T3\) are daily timelines for worker, researcher, and pupil, respectively. A timeline often indicates the types of events being represented, the number of events, the chronological time when they occurred in, the order in which they occurred, how long they lasted, and whether any of them met or overlapped. For instance, suppose that the timeline \(S\) in Figure 3 represents a standard healthy daily timeline. We want to know which timeline in the tree timelines of \(T1\), \(T2\), and \(T3\) is the most like \(S\). Perhaps we can tell the result is \(T3\) at a glance, because there are more overlaps with same labels between \(S\) and \(T3\). However, such manual comparison will be hard to accomplish while the dataset is large. Hence, we defined a timeline similarity function that is shown in next section to evaluate it. Not only the storage of big timeline dataset but also the similarity query of timelines requires effective and efficient access methods. However, none of the existing special index structures have dealt with such methods yet. Figure 1: The difference between a timeline and a time series. Figure 3: Daily timelines of worker, researcher, and pupil. Figure 2: Some Empires of China, Japan, and Korea ([[https://timelinestoryteller.com/#examples](https://timelinestoryteller.com/#examples)]([https://timelinestoryteller.com/#examples](https://timelinestoryteller.com/#examples))). An alternative approach is to transform the timelines into intervals and then use interval indices. An interval stores a value that represents a span of measurement, such as time, distance, and temperature.