The Persistent Buffer Tree: An I/O-Efficient Index for Temporal Data

Title: The Persistent Buffer Tree: An I/O-Efficient Index for Temporal Data

Authors: Saju J. Dominic and G. Sajith

Main Research Question: How can we design an I/O-efficient data structure that supports insertions, updates, deletions, and range queries for temporal data while maintaining optimal I/O performance?

Methodology: The researchers proposed a probabilistic self-balancing persistent data structure called the Persistent Buffer Tree. This structure is designed to support insertions, updates, deletions, and range queries for versioned data. The Persistent Buffer Tree leverages random priorities to balance the search tree and allows search operations to be batched. It is partially persistent, meaning that updates can only be applied to the present version, while queries can be applied to any version, past or present.

Results: The researchers demonstrated that the Persistent Buffer Tree is I/O-optimal, meaning that it supports operations within an expected optimal number of I/O's in the worst case. They also showed that the structure can be used to solve offline problems more efficiently than previous persistent data structures, which were designed for on-line settings.

Implications: The Persistent Buffer Tree has significant implications for the field of I/O-efficient algorithms and data structures. It provides a new approach for maintaining and querying temporal data in external memory, which is particularly useful for applications involving large datasets and parallel computing. The structure's ability to support a wide range of operations and its I/O-optimality make it a promising tool for handling big data and time-oriented data.

Link to Article: https://arxiv.org/abs/0404033v1 Authors: arXiv ID: 0404033v1