State History Tree: An Incremental Disk-Based Data Structure for Very Large Interval Data

Catalog abstract summary

The State History Tree is a disk-based structure for incrementally arriving, time-ordered interval data derived from LTTng system traces, designed to support very large histories.

Source: Public institutional accepted-version PDF reviewed; abstract paraphrased for this catalog.

Problem and motivation

Trace-derived, time-ordered interval histories can exceed memory capacity; generic R-trees rebalance repeatedly during chronological construction, while B-trees do not directly model intervals (pp. 2-5).

Method and contribution

The State History Tree stores key/value intervals in fixed-size disk blocks organized as a tree. Nodes are closed and committed without rebalancing when chronological end-time insertion fills them; sequence numbers and child time boundaries guide navigation. Full and key-specific ad-hoc queries traverse relevant branches (pp. 5-7).

Findings and evidence

The Java implementation integrates with Eclipse TMF/Linux Tools and manages state intervals extracted from LTTng traces. Tested block sizes are 16 KB, 64 KB, 256 KB, 1 MB, and 4 MB; 16-256 KB perform best on the tested traces, while 1 MB is slightly better above 10 GB. For 10-550 GB traces, the paper reports about 150 ms full-query and 2 ms ad-hoc-query times (pp. 7-9). R-tree queries are faster in memory, but construction is slower and capacity-limited; PostGIS has higher reported storage/query overhead.

Limitations and future directions

Limitations: The design assumes intervals arrive in ascending end-time order and short intervals dominate. Frequent insertion into the past can increase imbalance and, in the worst case, degenerate toward a linear list (pp. 5-6). The conclusion states no separate author future-work agenda.

Future work: Unknown / not explicitly stated by the authors. Do not convert generic modern-storage or modern-tracing ideas into author-attributed future work.

Sources and identifiers

• Published version published
• Public accepted full text · PDF public_full_text

When to cite this paper

Cite this paper when your work uses or compares incremental disk-based interval storage that avoids rebalancing under time-ordered insertion.

• Incremental disk-based interval storage that avoids rebalancing under time-ordered insertion.
• The State History Tree's full versus key-specific ad-hoc query distinction.
• LTTng-derived system-state interval storage integrated into Eclipse TMF/Linux Tools.
• The block-size and 10-550 GB scalability results, including the reported 150 ms full and 2 ms ad-hoc query values.

Citation

@inproceedings{ezzatiJivan2013statehistory,
  author = {Alexandre Montplaisir-Goncalves and Naser Ezzati-Jivan and Florian Wininger and Michel R. Dagenais},
  title = {State History Tree: An Incremental Disk-Based Data Structure for Very Large Interval Data},
  year = {2013},
  booktitle = {IEEE International Conference on Social Computing},
  pages = {716-724},
  publisher = {IEEE},
  doi = {10.1109/SocialCom.2013.107},
  url = {https://doi.org/10.1109/SocialCom.2013.107}
}

Montplaisir-Goncalves, A., Ezzati-Jivan, N., Wininger, F., & Dagenais, M. R. (2013). State History Tree: An Incremental Disk-Based Data Structure for Very Large Interval Data. In IEEE International Conference on Social Computing (pp. 716-724). https://doi.org/10.1109/SocialCom.2013.107

A. Montplaisir-Goncalves, N. Ezzati-Jivan, F. Wininger, and M. R. Dagenais, "State History Tree: An Incremental Disk-Based Data Structure for Very Large Interval Data," in IEEE International Conference on Social Computing, pp. 716-724, 2013, doi: 10.1109/SocialCom.2013.107