# A Distributed Indexing Method for Timeline Similarity Query
## 5 Experimental Evaluation  
In order to verify the algorithm proposed in this paper, we performed an experimental evaluation of the DTI-Tree. DTI-Tree is an indexing method for interval-based discrete timelines similarity query based on Apache Spark. We performed an experimental evaluation of the DTI-Tree and compared it to the R-Tree in GeoSpark [33]. The R-Tree in GeoSpark was chosen because it provides the same properties as our approach that can index discrete interval data collections based on Spark. In addition, the family of R-Trees is still the most popular index structure that is used for general spatio-temporal data and is provided by platforms, such as Hadoop, MongoDB, Oracle, MySQL, PostgreSQL, Microsoft SQL Server, and more. An interval object will be treated as a two-dimensional point in R-Tree in our experimental evaluation. Furthermore, a timeline generator and two benchmark datasets will be presented in this experiment. As mentioned in the previous sections, the timeline data are stored in HDFS. We use Spark (version 2.2.1) RDD to load the dataset from HDFS (version 2.7.3). Without special instructions, all of the experimental results were computed on a cluster, including five computers, as shown in Figure 12. The HDFS name node, Spark master and index master are on the same node which is a workstation computer with the configuration of two 2.80 GHZ Intel(R) Xeon(R) CPUs, and 32 GB RAM. Each slave node is a computer which has 16 GB RAM, a 64-bit dual core i5 processor, and a 7200 rpm 1 TB disk. It plays roles of the HDFS data node, Spark worker, and index slave. The client is a computer that has an Intel(r) Core(tm) i7 processor and 8 GB RAM. The communications among the master node, the slave node, and the client are implemented by the Hadoop Remote Procedure Call (RPC) ([[https://wiki.apache.org/hadoop/HadoopRpc](https://wiki.apache.org/hadoop/HadoopRpc)]([https://wiki.apache.org/hadoop/HadoopRpc](https://wiki.apache.org/hadoop/HadoopRpc))). We design two protocol interfaces, called MasterProtocol and SlaveProtocol, to support the communications. The operation systems of the cluster are all Ubuntu 16.04. All the algorithms are implemented by java (JDK 1.8.0_144) using IntelliJ IDEA 2017 (community edition). To test the performance of the index method, we develop a timeline data generator, called TimelineGenerator ([[https://github.com/ZhenwenHe/gtl_for_java/tree/master/src/main/java/gtl/index/itree/TimelineGenerator](https://github.com/ZhenwenHe/gtl_for_java/tree/master/src/main/java/gtl/index/itree/TimelineGenerator)]([https://github.com/ZhenwenHe/gtl_for_java/tree/master/src/main/java/gtl/index/itree/TimelineGenerator](https://github.com/ZhenwenHe/gtl_for_java/tree/master/src/main/java/gtl/index/itree/TimelineGenerator))), for generating the simulated random dataset, which fits for  
Figure 12: Architecture of the experimental system. some special requirements. The random number generator used in TimelineGenerator is the UniformGenerator of Spark MLlib ([[https://spark.apache.org/mllib/](https://spark.apache.org/mllib/)]([https://spark.apache.org/mllib/](https://spark.apache.org/mllib/))). The TimelineGenerator belongs to the open source project gtl_for_java ([[https://github.com/ZhenwenHe/gtl_for_java.git](https://github.com/ZhenwenHe/gtl_for_java.git)]([https://github.com/ZhenwenHe/gtl_for_java.git](https://github.com/ZhenwenHe/gtl_for_java.git))) on GitHub. The TimelineGenerator generates various timeline test datasets by controlling the parameters that are listed in Table 4. The first experimental dataset, named DS1, was generated by the TimelineGenerator with the default parameters. It has 10,000,000 timelines and about 55.6 million intervals. The dataset DS1 is about 0.7 TB and represents short timelines. The second experimental dataset, named DS2, was generated by the TimelineGenerator, with the parameters _timelineMinLength_ = 50, _timelineMaxLength_ = 100, and _intervalAttachment_ = [5\(k\),10\(k\)]. The dataset DS2 also has 10,000,000 timelines, but it has about 1.3 billion intervals.