npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

i2bplustree

v1.0.2

Published

A package to implement the Improved Interval B+ tree, in TypeScript

Downloads

1,338

Readme

Improved Interval B+ tree implementation (I2B+ tree)

npm npm NPM

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.

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
*/

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.

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.