Alexandre Montplaisir-Gonçalves, Naser Ezzati-Jivan, Florian Wininger and Michel Dagenais
Paper (2013)
|
Open Access to the full text of this document Accepted Version Terms of Use: All rights reserved Download (171kB) |
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 |
Funders: | CRSNG/NSERC |
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 |
---|---|
Statistics
Total downloads
Downloads per month in the last year
Origin of downloads
Dimensions