Product
Introducing SSO
Streamline your login process and enhance security by enabling Single Sign-On (SSO) on the Socket platform, now available for all customers on the Enterprise plan, supporting 20+ identity providers.
i2bplustree
Advanced tools
Readme
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 |
---|---|---|
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.
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.
Example:
import { IBplusTree, FlatInterval } from 'i2bplustree';
// Create a class that inherits from the FlatInterval
class MyInterval extends FlatInterval {
// This is just an example property
// Like this there could be many more
private myProperty: any;
constructor(val1: number, val2: number, myPropertyValue: any) {
super(val1, val2);
this.myProperty = myPropertyValue;
}
// This is just an example method
public exampleMethod(): void {
// Do stuff
}
// Overriding equals method to take into account the new property
equals(int: MyInterval): boolean {
return this.upperBound == int.getUpperBound() &&
this.lowerBound == int.getLowerBound() &&
this.myProperty == int.getProperty();
}
}
// Now we create our I2BplusTree object and insert a `MyInterval` object
const threshold = 30;
const alpha = 0.2;
const tree: IBplusTree<MyInterval> = new IBplusTree<MyInterval>(threshold, alpha);
// Introduce an object
tree.insert(new MyInterval(0, 2, "example-property"));
/**
And do many other operations such as:
- Delete an interval from the tree
- Delete all intervals contained in a range
- Verify if a interval exists in the tree
- Search all intervals with equal bounds to the ones provided
- Find the first interval that intersects the given bounds
- Find all intervals intersecting the given range
- Find all intervals contained in the given range
*/
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.
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.
OR
Carneiro, Edgar, Alexandre Valle de Carvalho, and Marco Amaro Oliveira. "A Comparative Study on the Performance of the IB+ Tree and the I2B+ Tree." Journal of Information Systems Engineering and Management 6.3 (2021): em0142.
FAQs
A package to implement the Improved Interval B+ tree, in TypeScript
The npm package i2bplustree receives a total of 436 weekly downloads. As such, i2bplustree popularity was classified as not popular.
We found that i2bplustree demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Product
Streamline your login process and enhance security by enabling Single Sign-On (SSO) on the Socket platform, now available for all customers on the Enterprise plan, supporting 20+ identity providers.
Security News
Tea.xyz, a crypto project aimed at rewarding open source contributions, is once again facing backlash due to an influx of spam packages flooding public package registries.
Security News
As cyber threats become more autonomous, AI-powered defenses are crucial for businesses to stay ahead of attackers who can exploit software vulnerabilities at scale.