# A Distributed Indexing Method for Timeline Similarity Query
###### Abstract
Generally, it can be represented by two attributes: _start value_ and _end value_. Interval is a fundamental data type for temporal, spatial, and scientific databases that are essential to solve the problem of representing temporal knowledge and reasoning arising in a wide range of disciplines [6; 7; 8; 9], especially in computer science and geoinformatics [10; 11]. Since the 1990s, research on interval data management has made significant progress in various aspects and many remarkable results have been reported, however, many challenges in this filed still remain [8; 9; 12; 13]. According to the reference [8], the existing interval indexes, including the Time Index [14], Segment R-tree [15], PR-tree [16], Interval B-Tree [17], Snapshot index [18], Fully Persistent B\({}^{+}\)-tree [19; 20], RI-tree [21; 22], TD-Tree [8], TB-Tree [9], and the SHB\({}^{+}\)-tree [23], etc. can be categorized into four groups [8]. Most existing interval index methods are extensions of traditional B\({}^{+}\)-tree [24; 25] or R-tree [26]. In general, the tree-like index structures are a kind of centralized data structure. They are hierarchical and are not efficient for parallel implementations due to high concurrency control cost [9; 27; 28]. How to transform the tree-like structure into linear structure effectively and efficiently is one of the key solutions to this problem. Another noteworthy issue is that most space partitioning indexes, such as TD-Tree and TB-Tree, often have a predefined space region for the root node. It limits the scalability to indexing dynamic interval data set. However, the timeline data are extremely large when all of them are converted into intervals with labels, and the data processing needs more computation, where it exceeds the capacity of traditional centralized technologies that are mentioned above. Some efforts have been performed to handle large-scale data. MapReduce [29] and MapReduce-Merge are two useful programming paradigms to handle large-scale data. Hadoop GIS [30], SpatialHadoop [28], and ST-Hadoop [31] were proposed to adapt the traditional spatial index structure, such as Quad-Trees and R-trees for MapReduce environments. The main drawback of these methods is that a large number of I/O disks is involved due to MapReduce's requirement in reloading data from disk in each job. Apache Spark ([[https://spark.apache.org/](https://spark.apache.org/)]([https://spark.apache.org/](https://spark.apache.org/))) succeed in dealing with the limitation by introducing a resilient distributed dataset (RDD). GeoSpark [32] and SparkGIS [33] were proposed to adapt the traditional spatial index structure for Apache Spark environments. In addition, some trajectory indices, for instance, the distributed R-tree [34] based spark were proposed recently. Di3 [35] is reported to be the first comprehensive indexing framework for interval-based next generation sequence (NGS) data. The Di3 is mainly a chromosome-level parallelism index that is based on B\({}^{+}\)-Tree, and its future work is to support Apache Spark and Hadoop for specialized indexing on very large datasets. Furthermore, it refers to indexing NGS data rather than timelines. We present the \"Distributed Triangle Increment Tree\" (DTI-Tree) access method that is based on Apache Spark to index timeline datasets in this paper. In contrast to the above-mentioned tree-like index structures for interval data, this method is scalable and can efficiently answer all of the 15 interval relationships queries proposed in our previous work [9]. In addition, it also has the ability to index timeline datasets based on the interval-based representation of timelines. Our contributions in this paper are summarized below:  
1. The triangle increment partition strategy (TIPS) is proposed to support the representation and partition of the interval dataset for indexing timeline datasets. 2. The DTI-Tree based on TIPS is proposed to effectively and efficiently index timelines.