  As users become confronted with a deluge of provenance data, dedicated
techniques are required to make sense of this kind of information. We present
Aggregation by Provenance Types, a provenance graph analysis that is capable of
generating provenance graph summaries. It proceeds by converting provenance
paths up to some length k to attributes, referred to as provenance types, and
by grouping nodes that have the same provenance types. The summary also
includes numeric values representing the frequency of nodes and edges in the
original graph. A quantitative evaluation and a complexity analysis show that
this technique is tractable; with small values of k, it can produce useful
summaries and can help detect outliers. We illustrate how the generated
summaries can further be used for conformance checking and visualization.

Databases;Data Structures and Algorithms