LinSet.zip:压缩线性集合图(LinSet.zip: Compressing Linear Set Diagram)

本工作在已有的Linear Diagram的基础上,通过将多个不相交的集合采用一定的策略压缩到一行,以使得布局更加紧凑,进而提高视图的空间效率以及提高集合间比较的效率。

背景

Linear Diagram[2]是一个经典的集合可视化方法。在Linear Diagram中,每一行表示一个集合,每一个overlap(如下图,下面叙述中都称作列)表示一类元素的聚合,列的宽度编码聚合中元素的数量。列与行的线段(segment)相交则表示相应的聚合中的元素属于线段表示的集合。

图1 Linear Diagram。图中红色虚线框以及旁边的文字是后面增加的注释,并不是原视图上的元素。

Linear Diagram的表示方法十分直观,可拓展性也很强,但也存在一些问题:

  • 在行空间上,当集合间的交集较为稀疏时,会出现大量空白,行空间的利用率会很低;
  • 在列空间上,比较距离较远的两个集合会比较困难。

算法

LinSet.zip便是通过对Linear Diagram进行改进以解决这些问题。 通过将多个不相交的集合采用一定的策略压缩到一行,以使得布局更加紧凑,进而提高视图的空间效率以及提高集合间比较的效率。整体算法流程如下:

图2 算法流程示意图

(1)列排序算法(a)→(b)。通过对列进行排序减少每个集合中segment的数量。

实际上在Linear Diagram中也有这部分算法,Linear Diagram使用的是贪心法,首先取包含集合最多的列,然后依次从剩下的列中选出和当前最左(右)侧的列距离最短的列加入最左(右)侧。距离计算方法如下图所示:首先将列转换成0-1向量,然后计算两个向量的曼哈顿距离即可。

图3 列距离计算演示

实际上,这个问题可以抽象成一个货郎周游问题(TSP),通过构建一个全1的辅助节点作为起始和终止位置,求解如何经过所有列对应的节点使得距离之和最短。TSP作为一个经典问题,不乏有很多精确算法和启发式算法,两种算法应用在这里的效果差异后面评估部分会提及。

(2)行压缩算法(b)→(c)。通过采取适当的策略将不相交的集合放到一行,以使得布局更加紧凑。

这里主要运用了3种策略:

  • Γ1: 同一行的集合之间不相交即可;
  • Γ2:在Γ1的基础上,任意两个集合内的segments都不能交替出现;
  • Γ3:在Γ1的基础上,允许两个集合的segments交替出现,但不能出现3个及以上的互相交替。

示意图如下:

图4 不同压缩策略的示意图

要想求解Γ1,可以将问题转化为图着色问题(同一种颜色的节点不能相连),将集合抽象成图中的节点,将集合交集抽象成图中的边,这样如何将集合分配到不同的行成为了如何为节点分配不同颜色的问题。通过图着色的相关精确算法和启发式算法即可实现求解。

图5 将Γ1转化成图着色问题示意图

求解Γ2和Γ3也十分类似。对于Γ2,只需要检查所有的交替情况并在出现交替的两个集合之间增加边(表示这两个集合对应的节点不能分配成同一个颜色,进而两个集合不能分配到同一行);对于Γ3,则需要检查所有的集合三元组以确定是否需要增加新的边。

(3)颜色分配。为每个集合分配一种颜色。

分配颜色并不是一个简单的问题。这里需要 (a) 同一行的各个集合的颜色不能相同;(b) 不同行的集合之间可以用相同的颜色(如果颜色不够用的话)。如果想要最小化使用颜色的数量,实际上是一个NP-hard的问题,需要花费很多来求解。作者最终采用了循环分配颜色的方法,这相比于上述问题的启发式算法的效果差别不大。

(4)渲染视图。

对于Γ2和Γ3,在segments之间增加连线以表明这些segments属于同一个集合(见图4(c)和(d))。

效果评估

对于LinSet.zip的评估主要在以下几个方面:

  1. 精确算法的时间效率
  2. 从最终segments的数量和压缩比例两个方面比较启发式算法和精确算法
  3. 对真实数据集的压缩效果探究

(1)精确算法的时间效率

在列排序算法中:
(1)时间并没有随着数据规模的扩大呈现指数级的提升;
(2)只有两个超过300s的。

在行压缩算法中:
(1)Γ1(B=+∞)时间最短;
(2)函数曲线都很类似;
(3)100个sets以下的情况都可以控制在5秒以内。

图6 精确算法的时间效率

(2)从最终segments的数量和压缩比例两个方面比较启发式算法和精确算法

启发式算法相比较与精确算法的效果差别有限。

图7 启发式算法和精确算法的比较

(3)对真实数据集的压缩效果探究

Γ1 < Γ3 < Γ2 < 0.4

图8 真实数据集的表现

用户实验

设计了2个元素相关的问题和3个集合相关的问题,比较了Linear Diagram和LinSet.zip分别在Γ1-Γ3下的效果。实验相关假设和最终结果如下:

图9 用户实验假设与结论

评价

  • 作者提到的不足:
    • 集合标签目前是简单放在集合最大的segment上,无法避免重叠的问题;
    • 缺少交互支持。例如对列进行重排以减小选中集合的segment数量;
    • 可以尝试扩展到径向布局。
  • 实际上,LinSet.zip也是一个trade-off
    • 增强了搜索元素和集合交集的能力(本文的目标)
    • 降低了对集合数量和集合大小的可读性(本文的用户实验支持这一观点,如下图,Γ0也就是Linear Diagram在Task 3上的表现最好)

参考文献:

[1] M. Wallinger, A. Dobler, and M. Nöllenburg, “LinSets.zip: Compressing Linear Set Diagrams.” arXiv, Feb. 16, 2023. Accessed: Apr. 12, 2023.
[2] P. Rodgers, G. Stapleton, and P. Chapman, “Visualizing Sets with Linear Diagrams,” ACM Trans. Comput.-Hum. Interact., vol. 22, no. 6, pp. 1–39, Dec. 2015.

评论关闭。