{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:42:22Z","timestamp":1760197342306,"version":"build-2065373602"},"reference-count":35,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2018,3,30]],"date-time":"2018-03-30T00:00:00Z","timestamp":1522368000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["41572314","U1711267"],"award-info":[{"award-number":["41572314","U1711267"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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\u2019s 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.<\/jats:p>","DOI":"10.3390\/a11040041","type":"journal-article","created":{"date-parts":[[2018,3,30]],"date-time":"2018-03-30T12:43:48Z","timestamp":1522413828000},"page":"41","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Distributed Indexing Method for Timeline Similarity Query"],"prefix":"10.3390","volume":"11","author":[{"given":"Zhenwen","family":"He","sequence":"first","affiliation":[{"name":"School of Computer Science, China University of Geosciences (Wuhan), 388 Lumo Road, Wuhan 430074, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9110-7369","authenticated-orcid":false,"given":"Xiaogang","family":"Ma","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Idaho, 875 Perimeter Drive MS 1010, Moscow, ID 83844-1010, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,3,30]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"2151","DOI":"10.1109\/TVCG.2016.2614803","article-title":"Timelines revisited: A design space and considerations for expressive storytelling","volume":"23","author":"Brehmer","year":"2017","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Camerra, A., Palpanas, T., Shieh, J., and Keogh, E. (2010, January 14\u201317). Isax 2.0: Indexing and Mining One Billion Time Series. Proceedings of the 2010 10th IEEE International Conference on Data Mining (ICDM), Sydney, NSW, Australia.","DOI":"10.1109\/ICDM.2010.124"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1007\/s00778-016-0442-5","article-title":"Ads: The adaptive data series index","volume":"25","author":"Zoumpatianos","year":"2016","journal-title":"VLDB J."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Yagoubi, D.E., Akbarinia, R., Masseglia, F., and Palpanas, T. (2017, January 18\u201321). Dpisax: Massively distributed partitioned isax. Proceedings of the 2017 17th IEEE International Conference on Data Mining (ICDM), New Orleans, LA, USA.","DOI":"10.1109\/ICDM.2017.151"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"677","DOI":"10.14778\/3199517.3199519","article-title":"Coconut: A scalable bottom-up approach for building data series indexes","volume":"11","author":"Kondylakis","year":"2018","journal-title":"Proc. VLDB Endow."},{"key":"ref_6","first-page":"481","article-title":"Interval sequences: An object-relational approach to manage spatial data","volume":"Volume 2121","author":"Jensen","year":"2001","journal-title":"Proceedings of the 2001 7th International Symposium Advances in Spatial and Temporal Databases (SSTD)"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1007\/3-540-47724-1_27","article-title":"Object-relational indexing for general interval relationships","volume":"Volume 2121","author":"Kriegel","year":"2001","journal-title":"Advances in Spatial and Temporal Databases"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"679","DOI":"10.2298\/CSIS101020035S","article-title":"Advanced indexing technique for temporal data","volume":"7","author":"Stantic","year":"2010","journal-title":"Comput. Sci. Inf. Syst."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1016\/j.isprsjprs.2013.01.014","article-title":"Parallel indexing technique for spatio-temporal data","volume":"78","author":"He","year":"2013","journal-title":"ISPRS J. Photogramm. Remote Sens."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s12145-013-0110-x","article-title":"Recent progress on geologic time ontologies and considerations for future works","volume":"6","author":"Ma","year":"2013","journal-title":"Earth Sci. Inform."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1602","DOI":"10.1016\/j.cageo.2011.02.011","article-title":"A skos-based multilingual thesaurus of geological time scale for interoperability of online geological maps","volume":"37","author":"Ma","year":"2011","journal-title":"Comput. Geosci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1481","DOI":"10.1007\/s10586-015-0475-3","article-title":"Decomposition tree: A spatio-temporal indexing method for movement big data","volume":"18","author":"He","year":"2015","journal-title":"Clust. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/s00778-016-0425-6","article-title":"Elite: An elastic infrastructure for big spatiotemporal trajectories","volume":"25","author":"Xie","year":"2016","journal-title":"VLDB J."},{"key":"ref_14","unstructured":"Elmasri, R., Wuu, G., and Kim, Y. (1990, January 13\u201316). The Time Index: An Access Structure for Temporal Data. Proceedings of the 16th International Conference on Very Large Databases, Brisbane, Australia."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1145\/119995.115807","article-title":"Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data","volume":"20","author":"Curtis","year":"1991","journal-title":"SIGMOD Rec."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Chaabouni, M., and Chung, S.M. (1993, January 25\u201328). The point-range tree: A Data Structure for Indexing Intervals. Proceedings of the 1993 ACM Conference on Computer Science, Washington, DC, USA.","DOI":"10.1145\/170791.170897"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0020-0190(94)00176-Y","article-title":"The interval B-tree","volume":"53","author":"Ang","year":"1995","journal-title":"Inf. Process. Lett."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1109\/69.404032","article-title":"Efficient management of time-evolving databases","volume":"7","author":"Tsotras","year":"1995","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1145\/119995.115861","article-title":"Fully Persistent B+-Trees","volume":"20","author":"Lanka","year":"1991","journal-title":"SIGMOD Rec."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Brodal, L., Tsakalidis, K., Sioutas, S., and Tsichlas, K. (2012, January 17\u201319). Fully Persistent B-Trees. Proceedings of the 23rd annual ACM-SIAM Symposium on Discrete algorithms, Kyoto, Japan.","DOI":"10.1137\/1.9781611973099.51"},{"key":"ref_21","unstructured":"Kriegel, H.-P., P\u00f6tke, M., and Seidl, T. (2000, January 10\u201314). Managing intervals efficiently in object-relational databases. Proceedings of the 26th International Conference on Very Large Data Bases, San Francisco, CA, USA."},{"key":"ref_22","unstructured":"Enderle, J., Schneider, N., and Seidl, T. (September, January 30). Efficiently processing queries on interval-and-value tuples in relational databases. Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Wang, G., Zomaya, A., Martinez Perez, G., and Li, K. (2015, January 18\u201320). SHB+-tree: A segmentation hybrid index structure for temporal data. Proceedings of the 2015 15th International Conference on Algorithms and Architectures for Parallel (ICA3PP), Zhangjiajie, China.","DOI":"10.1007\/978-3-319-27119-4"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","article-title":"Organization and maintenance of large ordered indexes","volume":"1","author":"Bayer","year":"1972","journal-title":"Acta Inform."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/356770.356776","article-title":"Ubiquitous B-tree","volume":"11","author":"Douglas","year":"1979","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/971697.602266","article-title":"R-trees: A dynamic index structure for spatial searching","volume":"14","author":"Guttman","year":"1984","journal-title":"SIGMOD Rec."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1195","DOI":"10.1016\/j.jpdc.2013.03.015","article-title":"Parallel multi-dimensional range query processing with R-trees on GPU","volume":"73","author":"Kim","year":"2013","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Eldawy, A., and Mokbel, M.F. (2015, January 13\u201317). Spatialhadoop: A mapreduce framework for spatial data. Proceedings of the 2015 31st IEEE International Conference on Data Engineering, Seoul, Korea.","DOI":"10.1109\/ICDE.2015.7113382"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1327452.1327492","article-title":"Mapreduce: Simplified data processing on large clusters","volume":"51","author":"Dean","year":"2008","journal-title":"Commun. ACM"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1009","DOI":"10.14778\/2536222.2536227","article-title":"Hadoop gis: A high performance spatial data warehousing system over mapreduce","volume":"6","author":"Aji","year":"2013","journal-title":"Proc. VLDB Endow."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Gertz, M., Renz, M., Zhou, X., Hoel, E., Ku, W.-S., Voisard, A., Zhang, C., Chen, H., Tang, L., and Huang, Y. (2017, January 21\u201323). St-hadoop: A mapreduce framework for spatio-temporal data. Proceedings of the 2017 15th International Symposium Advances in Spatial and Temporal Databases (SSTD), Arlington, VA, USA.","DOI":"10.1007\/978-3-319-64367-0"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Yu, J., Wu, J.X., and Sarwat, M. (2015). Geospark: A Cluster Computing Framework for Processing Large-Scale Spatial Data, Assoc Computing Machinery.","DOI":"10.1145\/2820783.2820860"},{"key":"ref_33","unstructured":"Wang, F., Luo, G., Weng, C., Khan, A., Mitra, P., and Yu, C. (September, January 31). Sparkgis: Efficient comparison and evaluation of algorithm results in tissue image analysis studies. Proceedings of the Biomedical Data Management and Graph Online Querying: VLDB 2015 Workshops, Big-O(Q) and DMAH, Waikoloa, HI, USA. Revised Selected Papers."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.ins.2017.01.016","article-title":"Parallel trajectory search based on distributed index","volume":"388\u2013389","author":"Wang","year":"2017","journal-title":"Inf. Sci."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.ins.2016.08.085","article-title":"Indexing next-generation sequencing data","volume":"384","author":"Jalili","year":"2017","journal-title":"Inf. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/4\/41\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:59:06Z","timestamp":1760194746000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/11\/4\/41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,30]]},"references-count":35,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,4]]}},"alternative-id":["a11040041"],"URL":"https:\/\/doi.org\/10.3390\/a11040041","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2018,3,30]]}}}