Indications of a plurality of events whose occurrence is detected in a particular execution of a program are obtained. One or more partitions of a trace object corresponding to the execution are constructed, including a first partition corresponding to a first subset of the events. The first partition comprises a header portion which includes a compressed representation of one or more event chains, and a data portion comprising a compressed events record indicating an occurrence, during the execution, of a particular sequence of events indicated by an event chain. The trace object is stored.