工作流可视化的可视压缩新方法

论文：《Visual Compression of Workflow Visualizations with Automated Detection of Macro Motifs》

作者：Eamonn Maguire, Student Member, IEEE, Philippe Rocca-Serra, Susanna-Assunta Sansone, Jim Davies, and Min Chen, Member, IEEE

会议：Infovis2013

本文介绍了一种基于自动检测motif，并结合用户打分进行选择并生成macro，最终实现对工作流图的可视压缩。

本文工作的流程如下：

A：输入数据存入数据仓库

B：Motif提取算法，从数据中提取motif

C：生成motifs

D：对motifs进行打分，根据分数进行排序

E：通过交互选择motif生成macro

F：选出macro

G：为macro生成图形

H：用户为macro标注

I：将生成生成的macro插入到工作流图中。

本文的关键在于motif生成算法，作者首先给出了motif的标准：

1.至少包含两个节点

2.同时是拓扑和语义敏感的

3.每对节点间不一定有连接

4.每个节点到输入和输出节点间必须有通路

5.输入节点的类型必须一样，输出节点亦然

6.输入输出节点可以连接任意多的边

7.可以从多个节点获得输入也可以向多个节点输出

motif生成算法可以用一个有限状态机说明：

状态S0代表单节点起始状态，S2代表多节点起始状态，S1代表单节点状态，S3代表相同属性的多节点状态，S4代表不同属性的多节点状态。图中实边表示状态转移后能够生成motif，虚边表示状态转移后不能生成motif。

文中将motif分成了三类，分别是单支、同类多支、异类多支，分别对应下图的a，b，c图：

上图同时也给出了三类motif所对应的状态转移情况。

生成motif后使用评分函数对motif打分，这个打分综合了motif所在工作流的出现次数，motif在工作流中的出现次数，以及motif实现的压缩量，得出的结果如下：

通过交互用户选出motif生成macro，macro的设计使用了层次细节的模式，如下图所示：

从图中可以看到，macro的层次设计分为三层，第一层细节只提供所有节点组成的拓扑轮廓，并以一个color bar表示macro中的节点类型；第二层细节给出了节点的分布情况；最后一层细节则给出了所有节点以及他们直接的连接情况。

文章最后从两个方面给出了评估。

与现有算法相比，作者认为本文的方法于FANMOD相比效率更高，准确率也更高。

从用户需求的角度，作者人问本文的方法满足了专家的需求。

总的来说，本文的方法高效、准确的完成了工作流图的压缩任务。