The paper presents a new compressible memory data structure for trace events. Its primary intention is to aid the analysis of huge traces by reducing the memory requirements significantly. Furthermore, customized evaluation algorithms reduce the computational effort. The data structure as well as algorithms for construction and evaluation are discussed in detail. Experiments with real-life traces demonstrate the theoretically derived capabilities of the new approach. (c) 2004 Elsevier B.V. All rights reserved.