<  Back to the Polytechnique Montréal portal

R-SHT: A state history tree with R-Tree properties for analysis and visualization of highly parallel system traces

Loïc Prieur-Drevon, Raphaël Beamonte and Michel R. Dagenais

Article (2018)

Accepted Version
Terms of Use: Creative Commons Attribution Non-commercial No Derivatives.
Download (1MB)
Cite this document: Prieur-Drevon, L., Beamonte, R. & Dagenais, M. R. (2018). R-SHT: A state history tree with R-Tree properties for analysis and visualization of highly parallel system traces. Journal of Systems and Software, 135, p. 55-68. doi:10.1016/j.jss.2017.09.023
Show abstract Hide abstract


Understanding the behaviour of distributed computer systems with many threads and resources is a challenging task. Dynamic analysis tools such as tracers have been developed to assist programmers in debugging and optimizing the performance of such systems. However, complex systems can generate huge traces, with billions of events, which are hard to analyze manually. Trace visualization and analysis programs aim to solve this problem. Such software needs fast access to data, which a linear search through the trace cannot provide. Several programs have resorted to stateful analysis to rearrange data into more query friendly structures. In previous work, we suggested modifications to the State History Tree (SHT) data structure to correct its disk and memory usage. While the improved structure, eSHT, made near optimal disk usage and had reduced memory usage, we found that query performance, while twice as fast, exhibited scaling limitations. In this paper, we proposed a new structure using R-Tree techniques to improve query performance. We explain the hybrid scheme and algorithms used to optimize the structure to model the expected behaviour. Finally, we benchmark the data structure on highly parallel traces and on a demanding trace visualization use case. Our results show that the hybrid R-SHT structure retains the eSHT’s optimal disk usage properties while providing several orders of magnitude speed up to queries on highly parallel traces.

Uncontrolled Keywords

data structures; tree; stateful analysis

Open Access document in PolyPublie
Subjects: 2700 Technologie de l'information > 2700 Technologie de l'information
2700 Technologie de l'information > 2704 Traitement réparti et simultané
2700 Technologie de l'information > 2706 Génie logiciel
2700 Technologie de l'information > 2715 Optimisation
Department: Département de génie informatique et génie logiciel
Research Center: Non applicable
Grant number: CRDPJ468687-14
Date Deposited: 09 Mar 2020 12:56
Last Modified: 08 Apr 2021 10:43
PolyPublie URL: https://publications.polymtl.ca/4214/
Document issued by the official publisher
Journal Title: Journal of Systems and Software (vol. 135)
Publisher: Elsevier
Official URL: https://doi.org/10.1016/j.jss.2017.09.023


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only