<  Back to the Polytechnique Montréal portal

State history tree: an incremental disk-based data structure for very large interval data

Alexandre Montplaisir-Gonçalves, Naser Ezzati-Jivan, Florian Wininger and Michel R. Dagenais

Conference or Workshop Item - Paper (2014)

Accepted Version
Terms of Use: All rights reserved.
Download (341kB)
Cite this document: Montplaisir-Gonçalves, A., Ezzati-Jivan, N., Wininger, F. & Dagenais, M. R. (2013, September). State history tree: an incremental disk-based data structure for very large interval data. Paper presented at International Conference on Social Computing (SocialCom 2013), Alexandria, VA, USA (9 pages). doi:10.1109/socialcom.2013.107
Show abstract Hide abstract


In this paper, we propose the State History Tree, a disk-based data structure to manage large streaming interval data. The State History Tree provides an efficient way to store interval data on permanent storage with a logarithmic access time. The disk-based structure ensures that extremely large data sets can be accommodated. The State History Tree stores intervals in blocks on disk in a tree organization. Unlike other interval management data structures like R-Trees, our solution avoids re-balancing the nodes, speeding up the tree construction. The proposed method is implemented in Java, and evaluated using large data sets (up to one terabyte). Those data sets were obtained from the state intervals computed from system events traced with the LTTng kernel tracer. The evaluation results demonstrate the performance and efficiency of the method, as compared with other solutions to managing huge interval data sets.

Open Access document in PolyPublie
Subjects: 2700 Technologie de l'information > 2700 Technologie de l'information
2700 Technologie de l'information > 2710 Conception de systèmes d'information
2700 Technologie de l'information > 2713 Algorithmes
Department: Département de génie informatique et génie logiciel
Research Center: Non applicable
Grant number: CRDPJ424666-11
Date Deposited: 13 Feb 2018 10:31
Last Modified: 08 Apr 2021 10:43
PolyPublie URL: https://publications.polymtl.ca/2983/
Document issued by the official publisher
Conference Title: International Conference on Social Computing (SocialCom 2013)
Conference Location: Alexandria, VA, USA
Conference Date(s): 2013-09-08 - 2013-09-14
Official URL: https://doi.org/10.1109/socialcom.2013.107


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only