Skip to content
This repository has been archived by the owner on Aug 3, 2020. It is now read-only.

EdgarACarneiro/I2Bplus-tree

Repository files navigation

⚠️ This repository has been archived (02/08/2020). Further developments continue at https://github.com/most-inesctec/I2Bplus-tree! ⚠️

Improved Interval B+ tree implementation (I2B+ tree)

BCH compliance Build Status Coverage Status

The Interval B+ tree (IB+ tree) is a valid-time indexing structure, first introduced by Bozkaya and Ozsoyoglu. This indexing structure appears as a time-efficient indexing structure for the management of valid-time/ intervals.

In this repository, we present the Improved Interval B+ tree (I2B+ tree), an indexing structure based on the IB+ tree, but with minor structural changes to improve the performance of the deletion operation. For a more detailed analysis of the I2B+ tree, refer to the paper published in the CISTI'2020 Conference, available at IEEE.

This structure performs all operations (insertion, search and deletion) with logarithmic performance (O (log n)). Documentation is available here.

Insertion Range Search Deletion
I var dataset a0 3 RS var dataset a0 3 D var dataset a0 3

For an in-depth analysis of both the parameter tuning (such as the tree's order or the time-splits alpha value) and the conclusions obtained from the performance analysis of the I2B+ tree, check the benchmarks folder.

Usage

To suit the I2BplusTree to your needs, implement a class that extends the FlatInterval class, defining the information that will be stored on leaves there. One might also want to override the equals method, thus allowing the incorporation of the extra information stored in the Intervals in comparisons.

Acknowledgements

This work was financed by the ERDF – European Regional Development Fund through the Operational Programme for Competitiveness and Internationalisation - COMPETE 2020 Programme and by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia within project PTDC/CCI-INF/32636/2017 (POCI-01-0145-FEDER-032636).

This work is also part of MOST.

Citation

E. Carneiro, A. V. d. Carvalho and M. A. Oliveira, "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, doi: 10.23919/CISTI49556.2020.9140897.