imMens: 实时的大数据可视查询工具

发布于 作者:

最近这段时间忙于写论文，所以博客断更了2个月。近期我打算把一些这段时间看过的、个人认为特别具有参考价值的文章做个paper report，因为通过实践，发现还是这种方法做的整理，记忆最为深刻。

imMens: Real-time Visual Querying of Big Data

（此文是斯坦福可视化小组发表在欧洲可视化会议EuroVis 2013上的一篇文章。在我查询data cube、visualization相关文献时，从另一篇文章：Bandlimited OLAP cubes for interactive big data visualization的参考文献处追溯而来，发现对于我现在的研究内容而言，这篇文章更具有参考价值。）

对于处理Big Data，现有的交互式可视化方法面临着用户感知的可扩展性和交互能力的可扩展性的不足(perceptual and interactive scalability )。其中，关于Big的定义，可视化研究者通常以一百万或更多的数据作为一个阈值；用户感知的可扩展性，指的是可视化系统方便读者获得知识的能力，在这方面Big Data加剧了提高可读性与保留细节之间的矛盾；交互的可扩展性，指可视化系统支持查询、过滤、缩放、选择等交互探索方式的能力，这方面Big Data加剧了高延迟，导致了交互操作的不流畅。为了解决以上问题，斯坦福大学和清华大学的研究人员，提出了imMens系统，一个典型的浏览器/服务器的系统架构，可以对上亿条记录进行高速处理和渲染，并把浏览器中的交互操作下的图形渲染速度维持在每秒50帧。其所用的理念、技术方法非常具有前瞻性。

为了实现以上目标，该系统的研究人员遵循如下原则进行设计：用户感知的可扩展性和交互能力的可扩展性，应当由数据的分辨率所限制，而不是由记录的数量所限制。毕竟直接在电脑屏幕上呈现1亿个点，是神仙也得看晕，而且机器处理也很困难。所以，一方面需要使用过滤、抽样和聚集等方法来降低数据规模，实现多个分辨率下多个可视化等级，以强化感知扩展性；另一方面，通过实现实时的数据查询来快速响应用户的交互操作，以提高交互的可扩展性。文章详细介绍了具体方案。个人认为，其中有三个重点技术值得注意：

其一，使用分组聚合(binned aggregation)降低数据规模。

降低数据规模的方法有很多，例如过滤，抽样，模型拟合，分组（filtering, sampling,  model-fitting, binned aggregation）。其中，过滤和抽样会丢失离群值，模型拟合只针对特定的应用场合。而分组聚合同时保留了全局模式（例如，密度）和局部特征（例如，离群值），同时通过选择分组大小的方式允许多个分辨率等级。

分组聚合的具体措施是，对于顺序和（排序）类名数据，每个离散值就是一个分组；对于数值数据，则在一个连续范围内分组为相邻的区间；时序值则按时间粒度分组：年，月，周，日，时，等；对于地理数据，可以使用一维列名单位例如州和国家作为唯一的分组，如果位置是用经纬度标识的点，可以用它的投影空间坐标来分组，例如麦卡托投影，使用地图服务提供商如google map提供的map tile即可。最后，再建立多个不同颗粒等级的分组（grained bins）来支持缩放和位移等交互操作。

上图给出了不同数据类型的在1维、2维下常用可视化方案。

上图figure2是一个将分组聚合的效果具体到可视化呈现上的很好的例子。(a)表示了一个包含10万个记录的2维数值型变量使用原始的散点图呈现的效果；(b)对原始记录点使用六边形做分组聚合，并且用颜色编码了点密度；(c)使用矩形分组，可以看到它与六边形分组差距不大；(d)在(c)的基础上，采用了强化感知的配色方案。

此处的配色方案也很值得参考。其公式如下：

其中Y是图中某一区域上你要编码的颜色属性（如饱和度、不透明度或者亮度）值，介于[0,1]之间。x 是该点你要表示的数据属性（对于上图而言是密度）。通常，我们在编程中所用的函数是Y=(X-Xmax)/(Xmax - Xmin)，即X与Y呈线性关系。但是，这种简单线性配色方案有两个问题，其一是Y值（如亮度、不透明度）与人眼的实际感知并不是呈简单线性关系。对此，本文引入了非线性参数γ ，默认值是1/3, 以立方根拟合，这样反而会使人眼观测数据时感知到线性的变化，就像CIELAB色彩空间中对亮度通道的处理一样。第二是对于Big Data，最大的X值与最小的非零X值可能差距很大，为了使最小的非零X值也能被识别，有必要定义一个最小非零X值的默认色彩值，这就是参数α。按照此配色方案作出的图figure2(d)，效果确实明显优于其他。

其二，使用多元数据砖（Multivariate Data Tiles）处理数据。

虽然使用分组聚合有效地降低了数据规模，但是如果数据维度很高，那么数据总量依然会很大，对于查询和渲染依然是很大的挑战。为此，必须对数据集进行进一步的分解。

例如，本文使用了黑莓手机的统计数据集，制作了如上图所示的探索界面，包含month, day, hour, X, Y这5个维度，可以分析不同时间点下用户的分布情况。

为了支持交互，可以使用在OLAP领域通用的方法，建立了一个五维数据立方。但是，像这样完整的数据立方通常过于庞大以至于不能完全存入缓存以及做实时查询。数据立方的大小等于∏i bi，其中bi是数据维度i下分组（bins）的个数。如果维度数量或者某维度上分组个数增加，那么整个数据立方的大小将变得难以控制。所以，必须将完整的数据立方分解为子立方。例如，针对这一可视化系统，作者将5维数据立方分解为4个三维子立方，月-日-时，月-经度-纬度，日-经度-纬度，时-经度-纬度，如上图figure5(b)所示。假设每个维度上分组的数量为b,那么整个数据存储大小就从b5变为4b3。形象地说，若b=50，那么数据立方的存储空间就从312.5M降低到了0.5M。这大大降低了数据存储规模。

但论文作者并不以此为满足，因为单一的子立方也可能因为分组数量过大而过于庞大。为了解决这个问题，作者借用地图服务中常用的数据砖（data tiles）概念，将子立方再切分为数个数据数据砖（data tiles）。

这里先讲解一下数据砖（data tiles）：我们看到的google map， 高德地图等地理信息服务系统的前端模块，都使用了data tiles，将庞大的地图图像数据，分解为若干个小图来处理——这就是为什么我们使用这些地图服务时经常看到地图图像是一小块一小块加载的。不过，本文中所提出的data tiles与地图服务中的data tiles有两处不同：其一是本文所用的data tiles视为了了进行动态的可视化而准备的，并不是已经预处理好的图像；其二是本文所用的data tiles包含多维数据，不仅是为了帮助查询，也是为了辅助渲染。此外，在索引方式上，这两者是类似的。每个data tiles都以Dbs-be-z的方式索引。其中D是数据维度，bs表示的是该维度上起点分组(bin)编号，be是终点分组的编号，z是缩放的分辨率等级。

之后，文章展示了将数据立方(data cube)最终切分为数据砖(data tiles)的好处：当进行一个范围查询时，只需要用划分的小块对这个范围进行拼接就可以了，不需要对整个数据空间进行搜索。例如，在上面那个黑莓手机分布的可视化系统中，如果用户要选择地图上的点并将之在日期直方图(day histogram)中高亮（即所谓的brushing & linking 操作），那么只需要回滚计算包含X*Y*day的数据砖并计算器总和。下图figure6表明了计算过程：只需要把相关的四个数据砖沿着X，Y维度做累加计算即可。而这种累加计算，只针对每个数据砖data tile,不存在顺序关系，为map reduce式的并行计算提供了可能。对于缩放和位移这一类的交互操作，则取出取出其他分辨率等级的分组的数据砖，就像google map的地图服务器那样。

其三，使用webGL在浏览器端实现基于GPU的并行数据计算

在最终实现上，imMens是一个服务器-浏览器的B/S架构的Big Data可视化探索系统。只要给出一个可视化定义（这一步需要手工写代码完成），那么imMens就会在后端计算好数据砖，然后根据需要把数据发给前端的现代浏览器上。

如前文所述，发来的数据砖不是渲染好的图形，而是分组数据，因此并不能直接在浏览器端显示，需要依赖现代浏览器来进行计算和渲染后才能显示和交互。一般情况下，基于安全的原因，对于浏览器端的渲染和计算，我们只能用诸如javascript语言控制大致逻辑，不能做到内存编辑和处理并行单元，因此很难做到并行计算提高渲染效率。但是此文提出了一个非常值得参考的意见：在服务器端将数据砖映射为png格式图片后发给前端浏览器，前端使用webGL计算数据和渲染图形，最终结果会放在一个HTML5 canvas元素上。以上具体步骤如图figure 8所示。毕竟webGL是目前唯一一个可以调用GPU功能的标准类库，使用GPU做数值计算也是经典的做法。以上方案从而充分利用前端存储空间和GPU的并行计算能力。

除此以外，imMens系统还用了leaflet渲染地图、D3渲染坐标轴和文本框。他们代码是开源的，可以到这里下载：https://github.com/StanfordHCI/imMens

 总结

本文提出了一种针对大规模数据的快速可视化查询系统imMens，并通过实验证明其方法的高效性。imMens所用的理念，使用分组聚合(binned aggregation)降低数据规模，使用多元数据砖（Multivariate Data Tiles）处理数据，和使用webGL在浏览器端实现基于GPU的并行数据计算。文中提到他们未来的工作是1）根据可用资源自动优化客户端的可视化规格（包括要求的维度和分组数）；2）提供一个类似tableau的可视化创建界面。以上内容对我目前的工作都具有极大的参考价值。