Journal of Information Systems Engineering and Management

Journal of Information Systems Engineering and Management, 2021 - Volume 6 Issue 3, Article No: em0142
https://doi.org/10.21601/jisem/11007

Published Online: 23 Jun 2021

Views: 1131 | Downloads: 839

Index structures were often used to optimise fetch operations to external storage devices (secondary memory). Nowadays, this also holds for increasingly large amounts of data residing in main-memory (primary memory). Within this scope, this work focuses on index structures that efficiently insert, query and delete valid-time data from very large datasets. This work performs a comparative study on the performance of the Interval B+ tree (IB+ tree) and the Improved Interval B+ tree (I2B+ tree): a variant that improves the time-efficiency of the deletion operation by reducing the number of traversed nodes to access siblings. We performed an extensive analysis of the performance of two operations: insertions and deletions, on both index structures, using multiple datasets with growing volumes of data, distinct temporal distributions and tree parameters (time-split alpha and node order). Results confirm that the I2B+ tree globally outperforms the IB+ tree, since, on average, deletion operations are 7% faster, despite insertions requiring 2% more time. Furthermore, results also allowed to determine the key factors that augment the performance difference on deletions between both trees.

data structure indexing B+ tree time intervals temporal data performance analysis

• Bozkaya, T. and Ozsoyoglu, Z. M. (1998). Indexing valid time intervals. In G. Quirchmayr, E. Schweighofer, & T. J. Bench-Capon (Eds.), Database and expert system applications (pp. 541-550). DEXA 1998. Lecture Notes in Computer Science, vol 1460. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054512
• Carneiro, E., Carvalho, A. V. d. and Oliveira, M. A. (2020). I2B+tree: Interval B+ tree variant towards fast indexing of time-dependent data. 2020 15th Iberian Conference on Information Systems and Technologies (CISTI), Sevilla, Spain, 2020, pp. 1-7. https://doi.org/10.23919/CISTI49556.2020.9140897
• Carvalho, A. V. d., Oliveira, M. A. and Rocha, A. (2014). Improvements to efficient retrieval of very large temporal datasets with the TravelLight method. s.l., 9th Iberian Conference on Information Systems and Technologies (CISTI). https://doi.org/10.1109/CISTI.2014.6876986
• Comer, D. E. (1979). Ubiquitous B-Tree. ACM Computing Surveys, 11(2), 121-137. https://doi.org/10.1145/356770.356776
• Cudre-Mauroux, P., Wu, E. and Madden, S., 2010. Trajstore: An adaptive storage system for very large trajectory data sets. 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), March, pp. 109-120. https://doi.org/10.1109/ICDE.2010.5447829
• de Berg, M., van Kreveld, M., Overmars, M. and Schwarzkopf, O. (2008). Computational Geometry: Algorithms and Applications. Springer-Verlag. https://doi.org/10.1007/978-3-540-77974-2
• Elmasri, R., Wuu, G. T. J. and Kim, Y.-J. (1990). The time index: An access structure for temporal data. Brisbane, Queensland, Australia, 16th International Conference on Very Large Data Bases.
• Gamma, E., Helm, R., Johnson, R. and Vlissides, J. (1994). Design patterns: Elements of reusable object-oriented software. s.l.: Addison-Wesley Professional Computing Series, Pearson Education.
• Goyal, M. (2009). Numerical Methods and Statistical Techniques Using ‘C’. s.l., Laxmi Publications.
• Guo, T., Papaioannou, T. G. and Aberer, K. (2014). Efficient indexing and query processing of model-view sensor data in the cloud. Big Data Research, 1, 52-65. https://doi.org/10.1016/j.bdr.2014.07.005
• Guttman, A. (1984). R trees: A dynamic index structure for spatial searching. ACM SIGMOD Record, 14. https://doi.org/10.1145/971697.602266
• He, Z., Kraak, M.-J., Huisman, O., Ma. and Xiao, J. (2013). Parallel indexing technique for spatio-temporal data. International Journal of Photogrammetry and Remote Sensing, 78, 116-128. https://doi.org/10.1016/j.isprsjprs.2013.01.014
• Katti, S. K. and Rao, A. V. (1968). Handbook of the poisson distribution. Technometrics, 10(2), 412-412. https://doi.org/10.1080/00401706.1968.10490580
• Liu, Q. and Yuan, H., 2019. A high performance memory key-value database based on redis. Journal of Computers, 14, 170-183. https://doi.org/10.17706/jcp.14.3.170-183
• Lock, H. C. and Booss, D. (2010). Indexing stored data. US, Patent No. 7,761,474.
• Mahmood, A. R., Aly, A. M., Kuznetsova, T., Basalamah, S. and Aref, W. G. (2018). Disk-Based Indexing of Recent Trajectories. ACM Transactions on Spatial Algorithms and Systems, 4(3), 7. https://doi.org/10.1145/3234941
• Mahmood, A. R., Punni, S. and Aref, W. G. (2019). Spatio-temporal access methods: a survey (2010 - 2017). Geoinformatica, 23(1), 1-36. https://doi.org/10.1007/s10707-018-0329-2
• Nascimento, M. A. and Dunham, M. (1999). Indexing valid time databases via B/sup +/-trees. IEEE Transactions on Knowledge and Data Engineering, 11(6), 929-947. https://doi.org/10.1109/69.824609
• Reinsel, D., Gantz, J. and Rydning, J. (2018). The digitization of the World – From edge to core, s.l.: Seagate, IDC Information and Data.
• Theodoridis, Y., Silva, J. R. and Nascimento, M. A. (1999). On the generation of spatiotemporal datasets. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and LectureNotes in Bioinformatics), 1651, 147-164. https://doi.org/10.1007/3-540-48482-5_11
• Valdés, F. and Güting, R. (2017). Index-supported pattern matching on tuples of time-dependent values. GeoInformatica, 21. https://doi.org/10.1007/s10707-016-0286-6
• Vutukuri, T. R. (2018). Q+ IB+ tree: Indexing technique for moving regions (PhD thesis), Southern Illinois University.

This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.