I2B+tree: Interval B plus tree variant towards fast indexing of time-dependent data

• Type: Article in International Conference Proceedings Book
• Date: 2020

Authors

Carneiro, E (Author) Other; Alexandre Carvalho (Author) FEUP; Oliveira, MA (Author) Other

Conference proceedings International

Title: 2020 15TH IBERIAN CONFERENCE ON INFORMATION SYSTEMS AND TECHNOLOGIES (CISTI'2020)

15th Iberian Conference on Information Systems and Technologies (CISTI)

ELECTR NETWORK, JUN 24-27, 2020

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 0 Citations

Other information

Authenticus ID: P-00S-F9T

DOI: 10.23919/cisti49556.2020.9140897

Abstract (EN): Index structures are fast-access methods. In the past, they were often used to minimise fetch operations to external storage devices (secondary memory). Nowadays, this also holds for increasingly large amounts of data residing in main-memory (primary memory). Examples of software that deals with this fact are in-memory databases and mobile device applications. Within this scope, this paper focuses on index structures to store, access and delete interval-based time-dependent (temporal) data from very large datasets, in the most efficient way. Index structures for this domain have specific characteristics, given the nature of time and the requirement to index time intervals. This work presents an open-source time-efficiency focused variant of the original Interval B+ tree. We designate this variant Improved Interval B+ tree (I2B+ tree). Our contribution adds to the performance of the delete operation by reducing the amount of traversed nodes to access siblings. We performed an extensive analysis of insert, range queries and deletion operations, using multiple datasets with growing volumes of data, distinct temporal distributions and tree parameters (time-split and node order). Results of the experiments validate the logarithmic performance of these operations and propose the best-observed tree parameter ranges.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 7