论文：《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 的标准：
- 至少包含两个节点
- 同时是拓扑和语义敏感的
- 每对节点间不一定有连接
- 每个节点到输入和输出节点间必须有通路
- 输入节点的类型必须一样，输出节点亦然
- 输入输出节点可以连接任意多的边
- 可以从多个节点获得输入也可以向多个节点输出
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 相比效率更高，准确率也更高。
从用户需求的角度，作者人问本文的方法满足了专家的需求。
总的来说，本文的方法高效、准确的完成了工作流图的压缩任务。
✉️ zjuvis@cad.zju.edu.cn