Multilevel Label Placement for Execution Trace Events

Catalog abstract summary

The accessible abstract describes automatic label placement for points and lines representing execution-trace events.

Source: Public ResearchGate abstract mirror and DBLP/venue metadata reviewed; author abstract not reproduced because reuse permission for the publisher version was not established.

Problem and motivation

Large trace displays contain overlapping event labels, limited lane width, and multiple abstraction levels. Labels must be placed consistently for individual, synthetic, and communication events without making the visualization unreadable or recomputing an expensive all-pairs conflict graph.

Method and contribution

The approach models four candidate positions around a point event; synthetic events use midpoint placement and communication labels use side-aware placement. Candidate conflicts form a graph, priorities are updated dynamically, and a greedy maximal-independent-set heuristic selects non-conflicting labels. Instead of materializing all O(n²) conflicts, one-dimensional neighbor search with sorting and binary search yields the stated O(n log n) behavior. The layout is combined with generalization, static aggregation such as DNS events, and dynamic pattern-library aggregation across LTTng-derived process lanes.

Findings and evidence

In synthetic file/network syscall sequences, 100-run averages include an example with 200 items and 88.5% conflict-free labels. Generalization and aggregation improve label success, whereas tight lanes and smaller fonts reduce it. The algorithmic contribution is the reduction from all-pairs conflict checks to a sorted-neighbor strategy; the placement remains a heuristic and is not guaranteed to maximize a global readability objective.

Limitations and future directions

Limitations: The evaluation is synthetic and visualization-oriented, with limited human readability validation. Direct line/area items and simultaneous multi-label efficiency are not fully supported, and greedy local decisions can miss a globally better layout.

Future work: Add perceptual/user studies, support line and area geometries, optimize repeated multi-label placement, incorporate viewport-aware priorities, and evaluate interactive latency on traces with millions of events and multiple abstraction levels.

Sources and identifiers

• Published version published
• PolyPublie record public_source_record

When to cite this paper

Cite this paper when placing labels in dense, zoomable multilevel execution-trace visualizations.

• Four-position event-label candidates and semantic placement rules.
• Greedy conflict resolution without materializing all O(n²) conflicts.
• LTTng event aggregation/generalization and the 88.5% example.
• The heuristic and limited human-readability validation caveat.

Citation

@inproceedings{ezzatiJivan2013multilevellabel,
  author = {Naser Ezzati-Jivan and Alireza Shameli-Sendi and Michel R. Dagenais},
  title = {Multilevel Label Placement for Execution Trace Events},
  year = {2013},
  booktitle = {2013 IEEE 26th Canadian Conference on Electrical and Computer Engineering (CCECE)},
  pages = {1-6},
  publisher = {IEEE},
  doi = {10.1109/CCECE.2013.6567826},
  url = {https://doi.org/10.1109/CCECE.2013.6567826}
}

Ezzati-Jivan, N., Shameli-Sendi, A., & Dagenais, M. R. (2013). Multilevel Label Placement for Execution Trace Events. In 2013 IEEE 26th Canadian Conference on Electrical and Computer Engineering (CCECE) (pp. 1-6). https://doi.org/10.1109/CCECE.2013.6567826

N. Ezzati-Jivan, A. Shameli-Sendi, and M. R. Dagenais, "Multilevel Label Placement for Execution Trace Events," in 2013 IEEE 26th Canadian Conference on Electrical and Computer Engineering (CCECE), pp. 1-6, 2013, doi: 10.1109/CCECE.2013.6567826