research-article

Efficiently rewriting large multimedia application execution traces with few event sequences

Authors:

Christiane Kamdem Kengne,

Leon Constantin Fopa,

Alexandre Termier,

Marie-Christine Rousset,

Takashi Washio,

Miguel SantanaAuthors Info & Claims

KDD '13: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 1348 - 1356

https://doi.org/10.1145/2487575.2488211

Published: 11 August 2013 Publication History

Abstract

The analysis of multimedia application traces can reveal important information to enhance program execution comprehension. However typical size of traces can be in gigabytes, which hinders their effective exploitation by application developers. In this paper, we study the problem of finding a set of sequences of events that allows a reduced-size rewriting of the original trace. These sequences of events, that we call blocks, can simplify the exploration of large execution traces by allowing application developers to see an abstraction instead of low-level events.

The problem of computing such set of blocks is NP-hard and naive approaches lead to prohibitive running times that prevent analysing real world traces. We propose a novel algorithm that directly mines the set of blocks. Our experiments show that our algorithm can analyse real traces of up to two hours of video. We also show experimentally the quality of the set of blocks proposed, and the interest of the rewriting to understand actual trace data.

References

[1]

Gstreamer website. www.gstreamer.net. Accessed:20/02/2013.

[2]

B. Cornelissen, D. Holten, A. Zaidman, L. Moonen, J. J. van Wijk, and A. van Deursen. Understanding Execution Traces Using Massive Sequence and Circular Bundle Views. 15th IEEE International Conference on Program Comprehension (ICPC '07), pages 49--58, 2007.

Digital Library

[3]

J. Egeblad. Heuristics for Multidimensional Packing Problems. PhD thesis, University of Copenhagen, Department of Computer Science, 2008.

[4]

A. Hamou-Lhadj and T. C. Lethbridge. A survey of trace exploration tools and techniques. In Proceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research, CASCON '04, pages 42--55. IBM Press, 2004.

Digital Library

[5]

K. J. Hoffman, P. Eugster, and S. Jagannathan. Semantics-aware trace analysis. In ACM SIGPLAN Notices, volume 44, page 453, May 2009.

Digital Library

[6]

C. K. Kengne, L. C. Fopa, N. Ibrahim, A. Termier, M.-C. Rousset, and T. Washio. Enhancing the analysis of large multimedia applications execution traces with frameminer. In ICDM Workshops, pages 595--602, 2012.

Digital Library

[7]

H. Kim, S. Im, T. Abdelzaher, J. Han, D. Sheridan, and S. Vasudevan. Signature Pattern Covering via Local Greedy Algorithm and Pattern Shrink. 2011 IEEE 11th International Conference on Data Mining, pages 330--339, Dec. 2011.

Digital Library

[8]

Y.-C. Li, J.-S. Yeh, and C.-C. Chang. Isolated items discarding strategy for discovering high utility itemsets. 2007.

[9]

J. Liu, K. Wang, and B. Fung. Direct discovery of high utility itemsets without candidate generation. In Data Mining (ICDM), 2012 IEEE 12th International Conference on, pages 984--989. IEEE, 2012.

Digital Library

[10]

H. Pirzadeh and A. Hamou-Lhadj. A Novel Approach Based on Gestalt Psychology for Abstracting the Content of Large Execution Traces for Program Comprehension. In 2011 16th IEEE International Conference on Engineering of Complex Computer Systems, pages 221--230. IEEE, 2011.

Digital Library

[11]

H. Pirzadeh, S. Shanian, A. Hamou-Lhadj, and A. Mehrabian. The Concept of Stratified Sampling of Execution Traces. In 2011 IEEE 19th International Conference on Program Comprehension, pages 225--226. IEEE, 2011.

Digital Library

[12]

K. Smets and J. Vreeken. Slim: Directly mining descriptive patterns. In Proc of the SDM, volume 12, 2012.

[13]

B. D. O. Stein. Pajé trace file format. 2003.

[14]

N. Tatti and J. Vreeken. The long and the short of it: Summarising event sequences with serial episodes. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 462--470. ACM, 2012.

Digital Library

[15]

V. S. Tseng, C.-W. Wu, B.-E. Shie, and P. S. Yu. Up-growth: an efficient algorithm for high utility itemset mining. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '10, pages 253--262, New York, NY, USA, 2010. ACM.

Digital Library

[16]

Z. Weg and R. Henschel. Introducing OTF / Vampir / VampirTrace. Memory.

[17]

C. W. Wu, B.-E. Shie, V. S. Tseng, and P. S. Yu. Mining top-k high utility itemsets. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '12, pages 78--86, New York, NY, USA, 2012. ACM.

Digital Library

[18]

J. Yin, Z. Zheng, and L. Cao. Uspan: an efficient algorithm for mining high utility sequential patterns. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '12, pages 660--668, New York, NY, USA, 2012. ACM.

Digital Library

[19]

J. Zou, J. Xiao, R. Hou, and Y. Wang. Frequent Instruction Sequential Pattern Mining in Hardware Sample Data. 2010 IEEE International Conference on Data Mining, pages 1205--1210, Dec. 2010.

Digital Library

Cited By

Costa WLima Lde Lima Junior O(2021)Extracting method of packet dependence from NoC simulation traces using association rule miningAnalog Integrated Circuits and Signal Processing10.1007/s10470-020-01645-6106:1(235-247)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1007/s10470-020-01645-6
Hogenboom FFrasincar FKaymak Ude Jong FCaron E(2016)A Survey of event extraction methods from text for decision support systemsDecision Support Systems10.1016/j.dss.2016.02.00685:C(12-22)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1016/j.dss.2016.02.006

Index Terms

Efficiently rewriting large multimedia application execution traces with few event sequences
1. Information systems
  1. Information retrieval
    1. Document representation
  2. Information systems applications
    1. Data mining
2. Theory of computation
  1. Semantics and reasoning
    1. Program reasoning
      1. Abstraction

Recommendations

An iterative, multi-level, and scalable approach to comparing execution traces
ESEC-FSE '07: Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering

In this paper, we overview a new approach to comparing execution traces. Such comparison can be useful for purposes such as improving test coverage and profiling system's users. In our approach, traces are compressed into different levels of compaction ...
Visualization, transformation, and analysis of execution traces with the eclipse TRACE4CPS trace tool
Abstract
An execution trace is a model of a single system behavior. Execution traces occur everywhere in the system’s lifecycle as they can typically be produced by executable models, by prototypes of (sub)systems, and by the system itself during its ...
Visualisations of execution traces (VET): an interactive plugin-based visualisation tool
AUIC '06: Proceedings of the 7th Australasian User interface conference - Volume 50

An execution trace contains a description of everything that happened during an execution of a program. Execution traces are useful, because they can help software engineers understand code, resulting in a variety of applications such as debugging ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '13: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2013

1534 pages

ISBN:9781450321747

DOI:10.1145/2487575

Editors:
Rayid Ghani
University of Chicago
,
Ted E. Senator
SAIC
,
Paul Bradley
MethodCare, Inc.
,
Rajesh Parekh
Groupon
,
Jingrui He
Stevens Institute of Technology
,
General Chairs:
Robert L. Grossman
University of Chicago and Open Data Group
,
Ramasamy Uthurusamy
General Motors Corporation (retired)
,
Program Chairs:
Inderjit S. Dhillon
University of Texas
,
Yehuda Koren
Google

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 August 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

KDD' 13

Sponsor:

KDD' 13: The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 11 - 14, 2013

Illinois, Chicago, USA

Acceptance Rates

KDD '13 Paper Acceptance Rate 125 of 726 submissions, 17%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
270
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Costa WLima Lde Lima Junior O(2021)Extracting method of packet dependence from NoC simulation traces using association rule miningAnalog Integrated Circuits and Signal Processing10.1007/s10470-020-01645-6106:1(235-247)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1007/s10470-020-01645-6
Hogenboom FFrasincar FKaymak Ude Jong FCaron E(2016)A Survey of event extraction methods from text for decision support systemsDecision Support Systems10.1016/j.dss.2016.02.00685:C(12-22)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1016/j.dss.2016.02.006

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten