<  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 Dagenais

Paper (2013)

Open Access document in PolyPublie
Open Access to the full text of this document
Accepted Version
Terms of Use: All rights reserved
Download (171kB)
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.

Subjects: 2700 Information technology > 2700 Information technology
2700 Information technology > 2710 Information systems design
2700 Information technology > 2713 Algorithms
Department: Department of Computer Engineering and Software Engineering
Grant number: CRDPJ424666-11
PolyPublie URL: https://publications.polymtl.ca/2983/
Conference Title: International Conference on Social Computing (SocialCom 2013)
Conference Location: Alexandria, VA, USA
Conference Date(s): 2013-09-08 - 2013-09-14
Publisher: IEEE
DOI: 10.1109/socialcom.2013.107
Official URL: https://doi.org/10.1109/socialcom.2013.107
Date Deposited: 13 Feb 2018 10:31
Last Modified: 18 Nov 2022 02:34
Cite in APA 7: Montplaisir-Gonçalves, A., Ezzati-Jivan, N., Wininger, F., & Dagenais, M. (2013, September). State history tree: an incremental disk-based data structure for very large interval data [Paper]. International Conference on Social Computing (SocialCom 2013), Alexandria, VA, USA (9 pages). https://doi.org/10.1109/socialcom.2013.107


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only

View Item View Item