SwiftTuna: 对大规模高维数据的快速响应的增量式可视化探索 (SwiftTuna: Responsive and Incremental Visual Exploration of Large-scale Multidimensional Data )

对于大规模数据的交互式探索,经常使用预处理方案(例如,数据立方体)来概括数据并提供低延迟响应然而,这种方案由于查询涉及更多维度而遭受过大量的内存占用,并且在查询之前必须从数据构建特定数据结构的强大先决条件。在本文[1]中,我们介绍了SwiftTuna,这是一个整体系统,简化了大规模多维数据的视觉信息搜索过程。SwiftTuna利用内存计算引擎Apache Spark来实现可扩展性和性能,而无需构建预先计算的数据结构。该论文还提出了一种新颖的交互式可视化技术,即尾部图表,以促进大规模的多维数据探索。为了支持对大规模数据的响应式查询,SwiftTuna利用增量处理方法,提供即时低保真响应(即快速响应)以及延迟的高保真响应(即增量响应)。性能评估表明,SwiftTuna允许对具有40亿条记录的真实数据集进行数据探索,同时在几秒钟内保留增量响应之间的延迟。

图1. SwiftTuan可视化系统概览图

概述

尽管可视化和数据库技术取得了很大进展,但大规模多维数据的可视化分析仍然具有挑战性。最重要的问题是查询的长延迟,这是由于数据的庞大程度造成的。为了解决这个问题,InfoVis和数据库社区的研究人员试图对大规模数据进行低延迟的可视化探索。通过对相关研究和可视化系统的调查,该论文呢为大规模多维数据确定交互式可视化分析系统的以下四个要求,并为这些系统定义设计空间。

R1. 大规模数据处理

系统应该能够以可扩展的方式处理大规模数据。很难用具体的数字来定义大规模数据或大数据的含义。此外,即使有一个具体的定义,它可能会跨域变化,或随着技术的进步而变化。该论文将10亿个实体视为大规模数据的最小尺寸。该数字是用于评估信息可视化中大规模数据分析的交互系统的最大条目数。

R2. 响应式互动

众所周知,较短的交互延迟可以促进洞察力的产生。但是,查询大规模数据通常需要几分钟甚至几个小时,这太长时间不能引起用户的注意。为了支持流畅的数据探索而不会丢失用户对正在进行的任务的关注,系统应该在不到10秒的时间内响应查询。

R3. 交互式多维探索

多维度是大规模数据探索的另一个重要方面,因为大多数真实世界的大规模数据集都具有两个或多个属性。系统应该能够照亮这些数据集的各个方面,使用户能够通过可视化探索多个维度之间的关系。通过允许用户生成多维数据的感知有效的1D或2D投影,用户将能够获得涵盖数据的多个维度的有意义的见解。此要求还包括多维度的互动; 例如,用户应该能够通过应用过滤器深入研究一小组有趣的数据。

R4. 可扩展的可视化

并非所有传统的可视化技术都适用于大规模数据分析。当应用于大规模数据时,大多数传统可视化可能遭受严重的过度绘制或混乱问题。因此,可视化设计人员必须更严肃地考虑其可视化的可扩展性,以使用户能够感知和理解大规模数据的可视化。

 

根据其计算方案(即预处理或增量),系统类型(即单机或分布式)以及测试的最大数据大小,可以对以前的方法进行分类,旨在解决四个要求的子集

图2. 对于以前处理大规模高纬可视化数据方法的分类

 

 

预处理原始数据和构建特定数据结构(例如,数据立方体)以进行快速查询的预处理方案是实现大规模数据探索的主要方法(图2中的左栏)。例如,imMens 预先计算了多变量数据切片,用于在可视化中进行响应性刷洗和链接。然而,预处理方案的局限性在于:1)预处理必须在分析之前进行2)在多维数据中建立具有所有维度的预计算数据结构通常是不可行的,因为禁止内存足迹,以及3)因此,只能回答某组维度上的某组查询。

相比之下,增量处理方案可以作为克服这些缺点的可行解决方案。在此方案中,查询以分布式和增量方式在线处理,而不使用预构建的数据结构。

SwiftTuna系统设计

SwiftTuna采用客户端 – 服务器架构。客户端是单页Web应用程序,用户可以在其中创建查询,实时监控查询进度,并与结果交互以探索数据。

为了支持大规模数据的响应式反馈,服务器提供快速响应,并逐步处理查询。当来自客户端的查询到达时,服务器首先返回包含查询的低保真结果的提示响应,该结果是从一小部分数据构建的。为了逐步处理数据,服务器将整个数据分成ñ 块, B0 至 B– 1。反过来,服务器将传入的查询拆分为n个作业,每个作业对应于每个数据块。这些作业将插入作业队列中。服务器接受第一个工作,包括B0。从队列中运行后端工作人员的工作。此后,服务器每200ms轮询一次工作人员以检查作业是否完成。完成后,服务器从工作人员收集结果并将其发送回客户端。队列中剩余的工作(即– 1 覆盖的工作 B1 至 Bn –  以相同的方式逐个处理。

从客户端的角度来看,针对单个查询会出现一系列错开的响应。客户端累积并组合部分结果。例如,假设有一个查询计算分类维度的频率直方图,nat_cd表示国家/地区的名称。第一部分答复仅包含国家/地区的频率B0。当第二个结果到来时,它涵盖了B1,客户通过比较国家名称来累积频率。然后,客户端更新进度条和相应的可视化。

图3. SwiftTuna系统的可视化卡片

图4. 尾部图表和点图。受梯度图的启发,采用渐变来可视化置信区间。(a)尾部梯度图通过在视觉空间的一半中将它们可视化来优先考虑突出的类别(例如,最常见的五个类别),而其余类别在另一半的空间中用线条(即尾部)等)。梯度显示估计值的95%置信区间。(b)当处理所有数据时,梯度最终收敛,并且有点点图替换有尾梯度图。(c)梯度图。(d)点图。当x轴上的类别数量很小(即,等于或小于8)时,我们使用先前的梯度图和点图而不是它们的尾部版本。

图5. 可视化卡提供两个协调视图,焦点视图和上下文视图,以及可视化特定功能,例如使用对数刻度而不是线性刻度或使用双变量颜色方案。(a)扩展梯度图(从图4c扩展)。(b)扩展的尾梯度图。(c)扩展密度图。密度图不提供刷选的上下文视图,但用户可以直接刷上焦点视图。

SwiftTuna目前支持四个与可视化相关的查询,Frequency Histogram,Binned Histogram,Pivot Dot Plot和Density Plot,以及两个与数据相关的查询,Count和Load Raw Data。该论文选择的四个可视化的概念都是基于区间的概念产生,而区间的概念可以无视数据量大小很好地传达全局模式和异常值。可视化显示在可视化卡(图3)中,该可视化卡用作分析的基本单元。Frequency Histogram(图4a)和Binned Histogram(图4c)分别提供了分类或数字维度的单变量摘要。另一方面,Pivot Dot Plot(图5b)和Density Plot(图5c)适合于可视化两个维度之间的关系。透视点图使用指定的聚合函数(MIN,MEAN,MAX或SUM)聚合数字维,按行分类维对行进行分组。密度图可视化两个数值维度的关系。

由于SwiftTuna将数据分成块并逐个处理每个块,因此在该过程的中间只能获得部分结果。为了允许用户快速访问结果,该论文根据已知的统计程序估算部分结果的最终结果。例如,由于部分结果来自总体样本,该论文使用样本统计数据估算人口统计数据(例如,使用样本均值和样本标准差来估计总体均值)。在特殊情况下,决定不估计使用MIN或MAX聚合的枢轴点图的最终结果,因为这些统计数据对异常值非常敏感,因此无法进行稳健估计。

响应式查询

该论文采用增量查询方法来实现对每种可视化的可视化相关查询的响应式查询。

查询流程

当需要更新可视化卡时(例如,用户激活过滤器或添加新卡),客户端请求对应于每个卡的每个查询的查询。例如,如果用户对数据应用过滤器,则应更新所有可见的可视化卡; 因此,客户端请求与可见卡一样多的查询。

要了解SwiftTuna的查询流程,假设分析师发出了两个查询, 查询1 对于分类维度的频率直方图和查询2对于数字维年龄的分箱直方图。当查询到达服务器时,每个查询都被分成n个工作,n是一个可调数量的块。为了减轻原始数据中可能的偏差,处理索引(从0到– 1)随机分配给每个块而不重复,并以此随机顺序处理块。对于查询Qi和块Bj,我们把该查询工作表示为 J(QiBj)

然后,创建的作业按特定顺序插入作业队列。SwiftTuna支持两种调度模式:块顺序和列表顺序。默认的块顺序优先于块查询。按此顺序,服务器首先执行具有较小处理索引的作业。例如,完成第一份工作j(Q1B0) 后,服务器运行j(Q2, B0),而不是J(Q1, B1)。在获取所有查询的早期结果时,块顺序很有用。相反,列表顺序优先考虑块上的查询,这意味着服务器完成与第一个查询相关的所有作业并移动到下一个查询。例如,在列表顺序中,J(Q1, B0) 之后执行J(Q1, B1)。用户可以切换调度模式并在卡列表面板中重新排序查询的优先级(图6c)。

图6. 卡片列表面板。(a)卡片列表显示可视化卡列表。最初,提供每个维度的卡片。(b)进度列表说明了每张带有进度条的卡的进度。用户可以分别通过单击停止和播放图标来停止或继续处理卡的查询。(c)用户可以使用两个选项确定查询的优先级:块顺序和列表顺序。(d)每次用户刷上可视化时,表示刷洗区域的过滤器将添加到过滤器列表中。用户可以单击漏斗图标以激活过滤器。(e)用户可以通过单击卡片列表底部的加号图标为二维创建一张新卡片(例如,两个数字维度之间的密度图)。

当用户应用过滤器时,会发生另外两个过程。首先,服务器使用SQL语法表示过滤器,并将其作为参数附加到所有作业。这允许工作人员过滤掉数据。其次,计算作业(计算满足过滤器的行数)将作为作业队列的前缀。计数作业的结果将发送到客户端并用于显示已过滤行的数量。

基本上,服务器需要一份工作,J(Qi, Bj),从作业队列中并在群集上运行它。在这里,由于我们只有一个作业和多个工作人员,我们需要将作业再次拆分为任务以利用Apache Spark的并行处理。服务器分隔块Bj到指定数量的子块(例如,集群中的工作者的数量),并创建与每个子块对应的每个任务的任务。然后,工作人员并行运行任务。服务器从工作程序收集结果,并将它们作为查询的增量响应发送回客户端Qi。请注意,此时客户端具有查询的增量响应Qi在块上B0至Bj。如果查询未完成(即,J – 1),客户端使用错误指示符(例如,梯度图)可视化响应并显示不完整的进度条。

即时响应

由于在之前的研究中提倡快速响应的重要性,SwiftTuna提供了快速响应,使用户能够在分析的早期阶段直观地确认查询。查询的提示响应是根据存储在服务器上的整个数据的一小部分样本构建的,而不会将查询传递给工作人员。此功能允许服务器几乎立即对查询做出反应,帮助用户将注意力集中在分析上。当请求两个或多个查询时,服务器会打包查询的所有提示响应,并立即将打包结果传回,从而减少网络开销。

当客户端收到查询的快速响应时,它会根据提示响应显示初始可视化。几秒钟后,当查询的第一个增量响应到达客户端时,客户端会丢弃提示响应并将其替换为第一个增量响应。这是因为当查询使用分箱(例如,分箱直方图)时,由于箱的不同尺寸和范围,不可能合并两个响应(即,快速响应和第一增量响应)。

增量响应

虽然第一个增量响应取代了快速响应,但客户端会累积剩余的增量响应并估计最终结果。具体过程因查询类型而异。在本节中,我们将解释每种查询类型的累积估计。

对于诸如频率直方图之类的计数查询,累积过程很简单。给定两个增量响应,我们比较每个类别的频率,如果两个响应中存在相同的类别,则将两个频率相加。对于估计,由于我们已经知道数据中所有行的数量,我们估计最终结果及其95%置信区间。

分箱直方图和密度图类似于频率直方图,因为它们计算行数。但是,为了累积这些查询的增量响应,必须在处理之前选择响应中使用的bin的大小和范围。我们可以为每个数字维度使用固定范围,但我们发现使用固定范围通常会产生不令人满意的分级结果,尤其是当数据中的多行被过滤掉时。作为一种补救措施,SwiftTuna增加了一项额外的工作,一项范围工作,在处理这些查询之前,这些查询仅在过滤后的剩余行中计算数字维度的最小值和最大值。然后,通过均匀地划分尺寸的最小值和最大值之间的间隔来确定箱的尺寸和范围。估计步骤与频率直方图查询的步骤相同,因为它们都是计数估计。然而,在测试中,对全部数据计算最小值与最大值会消耗数分钟,对于即时的查询极为不利,因此改为只计算第一块的数字维度的最小值和最大值,这样耗时大约为2秒,在实际的测试中这种处理也不会因为漏掉其他块的统计对分箱产生影响。

对枢轴点图的累积响应有点不同。枢轴点图在分类维上聚合数值维。目前,支持四种聚合函数:MIN,MAX,MEAN和SUM。合并MIN和MAX函数的两个增量响应非常简单。对于两个响应中的类别,我们比较响应中的两个MIN(或MAX)值,并根据聚合函数选择较小(或较大)的值。如前所述,我们决定不估算最终的MIN和MAX值,因为它们对异常值非常敏感。

对于MEAN和SUM函数,服务器为增量响应中的每个类别提供三个值:类别的频率,特定数字维度的总和以及维度的平方和。选择SUM函数时,可直接显示第二个值(即sum)。否则,对于MEAN函数,我们通过将第二值(即,和)除以第一值(即,类别的频率)来计算平均值。平方和用于计算平均值和总和估计值的方差和95%置信区间。

测试结果

经过测试,平均而言,无论查询维度的范围和查询的类型如何,用户都能够在0.5秒内收到快速响应。当数据被分成2,400个区块时(即N 400 ,一块大约覆盖175万行。需要大约两秒来计算第一个块上的维度范围(以确定箱的范围)或为一个块构建分箱直方图。这意味着用户可以在收到快速响应后的四秒钟内掌握175万行的第一个增量响应,并且每两秒进行一次下一个增量响应。

关于块的粒度,较小的块 (N 400 产生了更快的反应。然而,就吞吐量而言,较大尺寸的块是优选的。例如,当N是2,400,需要1.78秒来扫描一个块中的175万行并创建一个分箱直方图,但是,当N是240,处理十倍的行(1750万行)只需要两倍的时间(3.52秒)。这意味着存在无法有效并行化的开销,例如网络延迟或节点之间通信所花费的时间。

结论

总而言之,本文讨论了SwiftTuna这一使用低保真度即时响应和高保真度增量式响应的针对大规模高纬度数据的可视化系统,在使用数据立方体的预先处理方式的系统之外,又提供了一个另外的角度,十分有趣。

参考文献:

[1] Jaemin Jo, Wonjae Kim, Seunghoon Yoo, Bohyoung Kim and Jinwook Seo, “SwiftTuna: Responsive and incremental visual exploration of large-scale multidimensional data”, IEEE Pacific Visualization Symposium (PacificVis)131 – 140, 2017

评论关闭。