SEEDB论文阅读

原文地址

SEEDB: 高效的数据驱动可视化推荐以支持可视化分析

摘要

数据分析师通常将建立可视化作为分析工作流中的第一步。但是，当处理高维数据集时，可视化显示相关或期望的数据趋势是很耗时费力的。我们提出了SEEDB，这是一个便于快速可视化分析的可视化推荐引擎：给定要研究的数据子集，SEEDB会智能地探索出可视化空间，评估期望的可视化趋势，并且推荐那些他认为最“有用”或者最“有趣”的方案。推荐有趣可视化的两个主要障碍是(a)规模：在交互时间尺度内评估大量的候选可视化方案并作出响应；(b)实用：确定用于评估可视化有趣程度的合理度量标准。对于前者，SEEDB引入了剪枝优化来快速识别高实用性的可视化，并且通过分享最优方案来最大限度地共享可视化计算。对于后者，第一步我们采用了一个基于偏差的度量标准来实现可视化，同时表明了如何将其推广到其他影响实用性的因素。我们实现了SEEDB，将它作为可以运行在任何数据库管理系统上的中间件。我们的实验表明，我们的架构能够以高准确率识别有趣的可视化。我们的优化使相关行列存储速度提高了多个数量级，并在交互时间尺度内提供了推荐方案。最终，我们通过一项用户研究论证了基于偏差的实用性度量的有效性，以及支持可视化分析的推荐的意义。

1 引言

数据可视化通常是数据分析的第一步。给出一个新的数据集或者是关于现有数据集的一个新问题时，数据分析师需要建立各种各样的可视化感受数据，来发现异常和离群值，并且找出值得进一步研究的模式。然而，当处理高维数据集时，识别显示出有趣变化和数据趋势的可视化并非易事：数据分析师必须手动指定大量的可视化，探究不同属性之间的关系（及其组合），并且检查不同的数据子集，最终才能实现有趣的或有洞察力的可视化。这种手动指定和检查每个可视化的需要妨碍了快速分析和探索。

在本篇文章中，我们解决了自动识别和推荐可视化的问题。可视化推荐的核心挑战之一是，一个可视化的有趣与否取决于很多因素。在本篇文章中，我们采用了一个简单的标准去评价可视化的有趣程度：如果一个可视化与某些参考（例如另一个数据集、历史数据或是剩余数据）有很大偏差，那么它极有可能是有趣的。虽然它简单，但我们在用户研究中（第6节）发现，偏差通常可以引导用户走向他们认为有趣的可视化。当然，其他因素也会使一个可视化变得有趣，比如美学，所呈现的数据特定属性（我们的交互工具允许分析师选择感兴趣的属性)，或者数据中的其他类型的趋势(例如在某些情况下缺乏偏差可能是有趣的)。因此，尽管我们的焦点在于大偏差的可视化，但我们开发了一个名为SEEDB的系统，并且它的技术支持很大程度上与有趣程度的特定定义是无关的。在第7节中，我们将描述如何扩展该系统以支持一个通用的实用性度量标准。

给定一个特定的趣味性标准（称为效用指标），基于这个指标推荐可视化有以下几个问题：第一，即使对于具有少量属性的中等数据集，需要考虑的可视化的数量也常常是数百或数千；对于一些数据集，单是生成它们的可视化就需要很多分钟（正如我们将在本文中看到的）。第二，评估这些可视化的效用需要对相同的底层数据进行重复计算，浪费时间和计算资源。第三，推荐需要以交互速度给出，需要以略低精度返回可视化结果的近似方法。在我们的系统SEEDB中解决这些挑战和权衡是本文的主要重点。

我们从一个解释性的示例开始，该示例解释了SEEDB用例，并激发了我们使用基于偏差的效用度量的想法。

例1.1 假设一名记者正在为一篇关于千禧一代的新闻文章进行研究。此前的分析显示，千禧一代比前几代人的结婚年龄更大，这引发了人们对这种变化会对更广泛的社会产生何种影响的疑问。

因此，记者正在研究婚姻状况如何影响社会经济指标，如教育和收入等。她利用美国人口普查数据[28]对美国未婚成年人和已婚成年人进行了分析。

正如许多分析工作流程中常见的那样，记者首先使用她最喜欢的可视化软件来绘制数据中的各种指标。例如，她可以构建一个图表，将平均收入作为婚姻状况的函数显示出来，将婚姻状况可视化为受教育程度的函数，绘制出与种族和性别的关系，将每周工作时间可视化，等等。根据创建的可视化的类型，可能的可视化的数量会随着数据集中指示器的数量呈指数增长。因此，创建和检查所有可能的可视化很快变得难以处理。

我们已经发现，在许多分析中，显示目标数据（未婚成年人）趋势与参考数据（已婚成年人）趋势的可视化方法可能会引起分析人员的兴趣。例如，从我们的用户研究（第6节）中，我们知道对于这个特定的任务，分析人员会在图中找到可视化这很有趣，因为它描述的数据属性对于未婚成年人与已婚成年人是不同的。具体来说，图表显示，虽然未婚成年女性和未婚成年男性的资本收益大致相等，但已婚成年女性的资本收益仅为已婚成年男性的一半（图1c）。同一用户研究还显示，图1b是一个分析人员不感兴趣的可视化图。请注意，这张图表显示未婚和已婚成年人的年龄趋势没有不同（图1d）。

上面的例子表明，描述参考偏差的可视化可能会引起分析人员的兴趣；我们在本文中的目标是构建一个系统，该系统使用偏差作为一种手段，从大量潜在的可视化中识别最有趣的可视化。据我们所知，没有一个现有的系统会使用来自参考的变化来推荐可视化。正如前面所提到的，除了基于偏差的度量之外，当然还有许多其他维度可以影响可视化的感知效用，其中一些我们将在第7节中讨论，并将对这些度量的详细研究留给未来的工作。

我们对SEEDB的实现整合了端到端数据查询和可视化环境，允许分析师手动生成他们自己的可视化（如Tableau或Spotfire），或者根据需要获得数据驱动的建议，可以使用手动界面进一步细化。我们选择在SEEDB中同时支持自动化和手动交互，因为我们相信混合活动接口[12]对于保持分析人员处于决策圈中并允许他们驱动分析过程是必不可少的。

在将SEEDB开发为可以在任何数据库系统上运行的中间件层时，我们开发并验证了两种正交技术的使用，以使基于偏差的可视化推荐问题变得易于处理:

• 共享计算。我们开发了一套多查询优化技术，以便在候选可视化中共享计算，从而减少了最多40倍的时间。
• 剪枝计算。我们开发了剪枝技术，以避免在明显低效用的可视化上浪费计算，并采用了传统基于置信区间的top-k排序[11]和多臂老虎机[38]的技术，进一步减少了5倍的时间。

最后，我们开发了一个通用的基于阶段的执行框架，该框架允许我们同时利用这两种技术的优点，将执行时间减少了100倍以上，并使许多推荐实时可行。综上所述，本文的贡献有:

• 我们构建了一个系统，该系统将参考偏差作为为分析任务找到最有趣的可视化结果的标准（第2节）
• 我们将SEEDB设计为一个中间件层，它可以在任何符合sql的DBMS上运行（第3节）
• 我们将描述SEEDB的执行引擎（第4节），它使用共享技术在可视化中共享计算（章节4.1）和剪枝技术，以避免低效用的可视化计算（章节4.2）
• 我们评估了SEEDB的性能并证明了SEEDB可以在交互的时间尺度上以高精度识别高实用性的可视化（第5节）
• 我们展示了一个受控用户研究的结果，该研究验证了我们基于偏差的效用度量，并根据手工图表构建工具评估了SEEDB，表明SEEDB可以加速有趣的可视化标识（第6节）

我们注意到，这项工作建立在我们的短期愿景论文[24]和演示论文[36]中所描述的SEEDB的高层思想之上。

2 问题描述

在OLAP的标准中，以及在可视化分析工具如Tableau和Polaris[1,35]中，我们关注雪花模式数据库$D$。在可视化中，我们将想要进行group-by的属性表示为维度属性$A$，将想要进行聚类的属性表示为度量属性$M$。进一步地，我们用$F$表示度量属性上的潜在聚合函数集(如COUNT, SUM, AVG)。出于可视化的目的，假设我们可以依据任何维度属性$A$对$D$进行分组，并且可以聚合任何度量属性$M$。这就产生了一个两列的表格，可以通过标准的可视化机制（如条形图或趋势线）轻松地进行可视化。(最近的研究表明，柱状图是使用可视化分析工具[22]创建的绝大多数可视化效果。)我们的技术还应用于一般的Polaris表代数[35]，在这里，我们可以一次跨多个属性进行聚合，并group-by多个属性，可能会产生两个以上的列。为了便于阐述，我们在本文中将重点介绍两列结果可视化，可以使用条形图或趋势线方便地进行可视化。

除了数据库$D$之外，我们假设分析人员表示希望研究由查询$Q$指定的数据子集。SEEDB的目标是推荐具有高效用的$Q$的可视化(我们使用偏差来测量，正如本节中所解释的那样)。我们支持的在$D$上提出的查询Q包含了选择事实表的水平部分和一个或多个维度表的常规查询。从概念上说，我们可以将此视为一个简单的选择查询，连接雪花模式中涉及的所有表的结果。即便如此，我们还可以支持投影和连接，它们的作用是在可视化中分别删除某些列或表。因此，我们在雪花模式上支持一般类型的选择-项目-连接(SPJ)查询。出于本讨论的目的，我们将重点关注连接雪花模式中所有表的结果的简单选择查询。我们注意到这类查询可以满足大多数可视化任务。例如在我们的示例中，$Q$可以从人口普查表中选择记录的任何子集。我们将$Q$的结果表示为$D_Q$。

每个SEEDB可视化都可以转换为对底层数据进行group-by查询的聚合。我们将一个可视化$V_i$视为一个函数，由一个三元组$(a,m,f)$表示，其中$m\in M, a\in A, f\in F$。我们称它为聚合视图，或者简称为视图。聚合视图对$a$执行group-by，并应用聚合函数$f$来度量属性$m$​。举个例子，$V_i(D)$表示将$D$中的数据按$a$分组，再用$f$对$m$值进行聚合的结果；$V_i(D_Q)$表示应用于$D_Q$中数据的类似的可视化。

SEEDB通过偏差确定可视化的效用；显示出查询数据集(即$D_Q$)与参考数据集(称为$D_R$)中不同趋势的可视化被认为具有很高的实用性。参考数据集$D_R$可以定义为整个基础数据集$(D)$、$D_Q$的补集$(D-D_Q)$或任意查询$Q’$ 选择的数据$(D_{Q’})$。分析师可以选择指定$D_R$；如果分析师没有指定，我们使用$D_R=D$作为默认值。给定一个视图$V_i$，基于偏差的效用计算结果为应用$V_i$于查询数据$D_Q$和应用$V_i$于参考数据$D_R$的结果偏差。应用$V_i$于查询数据的视图可以表示为下面的查询$Q_T$。我们称之为目标视图。

$$Q_T=SELECT \ a,f(m)\ FROM\ D_Q \ GROUP\ BY \ a$$

类似地，应用$V_i$于参考数据的视图可以表示为$Q_R$。我们称之为参考视图。

$$Q_R=SELECT\ a,f(m)\ FROM\ D_R\ GROUP\ BY\ a$$

对应于每个视图的（两个）SQL查询称为视图查询。上面的视图查询的结果是包含两列的汇总，即$a$和$f(m)$。为了确保所有聚合汇总具有相同的规模，我们将每个汇总归一化为概率分布（即$f(m)$值和为1）。在我们的例子中，平均资本收益与性别的可视化（图1），$V_i(D_Q)$（未婚成年人，数据见表1c）目标视图的概率分布表示为$P[V_i(D_Q)]:(F:0.52,M:0.48)$，而$V_i(D_R)$（已婚成年人，表1c）参考视图的概率分布表示为$P[V_i(D_R)]:(F:0.31,M:0.69)$。相比之下，平均年龄与性别的可视化分布（数据见表1d）为目标视图$(F:0.5,M:0.5)$，参考视图$(F:0.51,M:0.49)$。定性地说，我们看到前者的分布有很大的偏差，而后者几乎没有任何偏差。

给定聚合视图$V_i$以及目标视图的概率分布$(P[V_i(D_Q)])$和参考视图的概率分布$(P[Vi(DR)])$，我们将$V_i$的效用定义为这两个概率分布之间的距离。两个分布之间的距离越远，可视化就越可能有趣，因此效用也就越高。形式化讲，如果$S$是距离函数，

$$U(V_i)=S(P[V_i(D_Q)],P[V_i(D_R)])$$

计算概率分布之间的距离已经在文献中得到了很好的研究，并且SEEDB支持各种距离函数去计算效用，包括Earth Mover’s Distance, Euclidean Distance, Kullback-Leibler Divergence (K-L divergence), and Jenson-Shannon Distance. SEEDB使用Earth Mover ‘s Distance作为默认的距离函数，我们发现使用其他距离函数可以得到类似的结果[37]。

我们可以将SEEDB问题正式表述如下：

问题2.1 给定数据库$D$上一个用户指定的查询$Q$，一个参考数据集$D_R$，一个效用函数$U$，和一个正数$k$，需要找到$k$个分类的视图$V\equiv (a,m,f)$，它是所有视图中$U(V)$最大的，同时最小化总计算时间。

在第7节中，我们将描述如何将我们的度量标准一般化以捕获除偏差之外的与可视化有趣程度有关的因素。

3 SEEDB前端及架构

我们现在描述SEEDB的前端用户体验，然后更详细地描述体系结构和执行引擎。

前端体验。SEEDB的可视化推荐功能被打包成端到端的可视化分析环境，带有基本的可视化功能，比如由Tableau提供的功能。SEEDB前端允许分析人员手动生成可视化，或者根据需要获得数据驱动的建议，这些建议可以使用手动界面进一步细化。我们将前端设计成一个混合式驱动界面，以保持人在决策圈内，并允许用户控制分析。图2显示了SEEDB的web前端所包含的四个部分：(A)用于连接数据库的数据集选择器和用于规定查询的查询创建器；(B)用于手动指定可视化的可视化生成器；(C)可视化显示面板；(D)显示推荐的可视化效果的推荐插件。由SEEDB提供的推荐会变化，以响应数据库发出的查询(A)中的变化。

架构概述。SEEDB作为一个中间件层被实现，它可以运行在任何符合sql标准的数据库系统之上。图3描述了系统的总体架构。SEEDB客户端是一个基于web的前端，它捕获用户的输入并渲染呈现由SEEDB服务器产生的可视化结果。SEEDB服务器由两个主要组件组成：视图生成器负责解析输入查询、查询系统元数据和生成必须被评估的可视化查询列表；执行引擎的目标是使用我们在底层DBMS上的优化来评估查询集合。所选中的聚合视图（例如，那些有很大偏差的视图）被发送到SEEDB客户端，并作为可视化建议显示给用户，然后用户可以与这些可视化进行交互。

基础执行引擎。为了激发对优化的需求，我们首先描述执行引擎在没有优化的情况下是如何工作的。为了确定$k$个最佳聚合视图，SEEDB需要做以下工作：对于每个聚合视图，它生成一个对应于目标视图和引用视图的SQL查询，并向底层DBMS发出这两个查询。它对每个聚合视图重复这个过程。当接收到结果时，它计算目标和参考视图分布之间的距离，并识别具有最高效用的$k$可视化结果。这个基础实现有许多低效之处。在一张具有$a$个维度属性、$m$个度量属性和$f$个聚合函数的表上，$2\times f\times a\times m$个查询需要被执行。正如我们在第五节中说明的，对于大的数据集，这需要耗费$>100s$的时间。这种延迟对于交互使用是不可接受的。

优化执行引擎。为了减少评估聚合视图集的延迟，SEEDB引擎应用了两种优化：共享，聚合视图查询被组合在一起，以尽可能地共享计算；以及剪枝，在不扫描整个数据集的情况下，将与低效用可视化相对应的聚合视图查询删除。这些优化在很大程度上是相互正交的。为了从这两种优化中获益，我们开发了一个分阶段执行框架。每个阶段对数据集的一个子集进行操作。阶段$n$的第$i$个对数据集的$n$个大小相等的分区中的第$i$个进行操作。例如，假设我们有$100,000$条记录和$10$个阶段，那么阶段$i=4th$就会处理记录$30,001$~$40,000$。执行引擎从在考虑范围内的整个聚合视图集开始。在阶段$i$期间，SEEDB使用数据集的第$i$个部分更新仍在考虑中的视图的部分结果。执行引擎应用基于共享的优化来最小化数据集的第$i$个部分上的扫描代价。在阶段$i$的末尾，执行引擎使用基于剪枝的优化来确定要丢弃哪些聚合视图。从部分1到$i$的每个聚合视图的结果都被用来估计每个视图的质量，而那些效用较低的视图则被丢弃。然后在第$i+1$轮处理保留的聚合视图，并继续这个过程。通过这种方式，在这些阶段中考虑的视图集减小，在第$1$阶段开始时所有的聚合视图，在第$n$阶段结束时只剩下$k$个视图。

4 SEEDB执行引擎

在本节中，我们将描述用于有效生成可视化推荐的共享和修剪优化。我们的扩展技术报告[37]描述了额外的离线预计算和剪枝技术。

4.1 基于共享的优化

在执行引擎的基本实现中，每个可视化被转换为在DBMS上独立执行的两个视图查询。然而，对于特定的用户输入，由SEEDB评估的查询非常相似：它们扫描相同的底层数据，不同的只是用于分组和聚合的属性。这为智能地合并和批处理查询提供了机会，从而减少了向数据库发出查询的数量，进而减少了底层数据的扫描次数。我们设置中的共享计算是一般多查询优化问题[33]的一个特例；我们将在第8节更详细地讨论这种关系。具体来说，我们应用了以下优化：

合并多个聚合：具有相同group-by属性的聚合视图查询可以被重写为具有多个聚合的单个查询。因此，对于视图$(a_1,m_1,f_1),(a_1,m_2,f_2)…(a_1,m_k,f_k)$，每个都需要执行两次查询，我们可以将这些视图合并为一个视图$(a,\{m_1,m_2…m_k\},\{f_1,f_2…f_k\})$来代替，总共只需要两次查询。我们发现，合并行和列存储中的聚合对延迟的影响很小，甚至没有影响。

合并多个group-by：在应用了我们的多个聚合优化之后，SEEDB剩下了许多具有多个聚合的查询，但只有单属性分组。这些查询可以进一步组合，以利用多属性分组的优势。但是，与合并多个聚合不同，添加分组属性会显著增加必须维护的组的数量，并且(可能)导致大量组的整体性能下降。

我们声明（并在第5节中验证），只要保持分组的内存利用率在一个阈值以下，分组就可以提高性能。而内存利用率又与查询中出现的不同组的数量成比例。如果一组属性$a_1…a_m$被用于分组，那么不同组的数量上界由$\prod_{i=1}^m|a_i|$决定。给定一个内存预算$S$，现在的挑战是确定最优的属性分组，使每个组都尊重内存预算。

问题4.1（最优分组） 给定内存预算$S$和一组维度属性$A={a_1…a_n}$，将维度属性A分组为$A_1,…,A_l$(其中$A_i\subseteq A,\bigcup A_i=A$ )，使得查询$Q$根据任意$A_i$对表进行分组，$Q$的内存利用率都不超过$S$。

注意到上述问题与NP-Hard装箱问题[18]同构，如果我们让每个维度属性$a_i$对应于装箱问题中带有重量$\log|a_i|$的一个物品，并且将箱子的大小设置为$\log S$，然后将这些物品装入箱子中，这与寻找组$A_1,…,A_l$是相同的，这样任何组的估计内存利用率都低于$S$。我们使用标准的首次适应算法[14]来寻找维度属性的最优分组。

合并目标视图和引用视图查询：因为目标视图和引用视图仅在执行查询的数据子集上不同，所以SEEDB将这两个视图查询重写为一个。例如，假设目标视图为$Q1$，参考视图为$Q2$，它们可以被合并为一个视图$Q3$。

$$\begin{aligned} Q1&=SELECT \ a,f(m) \ FROM\ D\ WHERE\ x<10\ GROUP\ BY\ a\\ Q2&=SELECT \ a,f(m) \ FROM\ D\ GROUP\ BY\ a\\ Q3&=SELECT \ a,f(m),CASE\ IF\ x<10\ THEN\ 1\ ELSE\ 0\ END\\ &as\ g1,1\ as\ g2\ FROM\ D\ GROUP\ BY\ a,g1,g2 \end{aligned}$$

并行查询执行：SEEDB并行执行多个视图查询，因为这些查询通常可以共享缓冲池页面，从而减少磁盘访问时间。然而，精确的并行查询数目需要考虑缓冲池争用、锁定和缓存线争用等因素进行调优。

4.2 基于剪枝的优化

实际上，大多数可视化都是低效用的，这意味着计算它们会浪费计算资源。因此，如前所述，在每个阶段的末尾，执行引擎使用剪枝优化来确定要丢弃哪些聚合视图。具体来说，基于到目前为止处理的数据，每个视图的部分结果被用于估计效用，而低效用的视图被删除。SEEDB执行引擎支持两种剪枝方案：第一种使用置信区间技术来绑定视图的效用；第二种使用多臂老虎机分配策略来找到顶级效用视图。

基于置信区间的剪枝。我们的第一个剪枝方案使用最坏情况统计置信区间来约束视图效用。这种技术（称为CI）类似于在其他背景中开发的基于top-k的剪枝算法[13,27]。我们的方案如下：在每个阶段，我们对每个聚合视图$V_i$保留一个平均效用的估计值，并在该均值附近设置一个置信区间。在一个阶段结束时，我们使用以下规则来剪枝低效用视图：如果视图$V_i$的效用上界低于$k$个或更多视图的效用下界，则$V_i$被丢弃。举例来说，假设一个数据集有4个视图$V_1…V_4$，我们想要找出排行前二的视图。进一步假设在阶段$i$结束时，$V_1$-$V_4$具有如图4所示的置信区间。到此为止，视图$V_1$和$V_2$的效用估计最高，可能在前二视图中。视图$V_3$目前不在前二中，但它的置信区间与前二重叠，这使得$V_3$有可能取代$V_1$或$V_2$。另一方面，$V_4$的置信区间完全低于$V_1$和$V_2$的置信区间。因为我们很大程度上可以断言$V_4$的效用在它的置信区间内，也就是说，$V_4$的效用很有可能比$V_1$和$V_2$的效用都低，它也不会出现在前二视图中。我们的修剪方案的伪代码可以在我们的技术报告[37]中找到。

我们使用从Hoeffding-Serfling不等式[34]得到的最坏情况下的置信区间。这个不等式声明了假设给定$[0,1]$上均值为$\mu$的$N$个值$y_1,…,y_N$，而且有$m$个不需要替代的值$Y_1,…,Y_m$，然后我们可以计算这$m$个值的当前均值附近的运行置信区间，使得$N$的实际均值总是以$1-\delta$的概率在这个置信区间内：

定理4.1 $\forall \delta>0$，对于$1\le m\le N-1$，定义

$$\varepsilon_m=\sqrt{\frac{(1-\frac{m-1}{N})(2\log\log(m)+\log(\pi^2/3\delta))}{2m}}\\ then: Pr[\exists m,1\le m\le N: |\frac{\sum_{i=1}^mY_i}{m}-\mu|>\varepsilon_m]\le \delta$$

在我们的设置中，每个$Y_i$对应的是根据迄今为止看到的记录计算出的效用估计值。

基于多臂老虎机的剪枝。我们的第二个剪枝方案采用了一个多臂老虎机策略[38]。在MAB中，一种在线算法通过一系列的试验从一组可选臂中重复地进行选择来最大化回报。我们注意到，这是老虎机策略第一次被应用于识别有趣的可视化效果的问题。

最近研究的MAB变体集中于寻找具有最高平均奖励的臂[5,4]。这种变化与SEEDB处理的问题相同：我们的目标是找到可视化（臂）和最高的效用（奖励）。具体来说，我们采用[5]的连续接受和拒绝算法来寻找具有最高平均奖励的臂。在每个阶段结束时，仍在考虑中的视图按其效用平均值排序。然后我们计算出效用平均值之间的两个差异：$\Delta_1$是最高均值和第$k+1$高均值的差值，$\Delta_n$是最低均值和第$k$高均值的差。如果$\Delta_1$比$\Delta_n$大，那么均值最高的视图被”接受”为top-k的一部分（它不再参与剪枝计算）。另一方面，如果$\Delta_n$更大，那么在运行过程中均值最低的视图将从视图集合中被丢弃。伪代码可以在技术报告[37]中找到。[5]证明了在一定的奖励分配假设下，上述技术识别出了高概率的top-k臂。

一致的距离函数。注意到上面描述的两个修剪方案在其他设置中都有前提条件，这些条件不会直接转移到我们的设置中。比如，MAB设置假设每个试验的样本来自一个固定的底层分布，而实际上我们的试验对应于$m$个分布（组）中的随机值，它们聚合在一起形成给定视图的效用估计。在我们的评估中，我们发现尽管有这个限制，修剪方案在实践中工作得相当好。

然而，我们可以得到一个较弱的前提：我们可以证明，当我们采样越来越多时，估计的效用$\hat{U}$可以任意接近于所有聚合视图的$U$。本质上，这意味着使用足够大样本的修剪算法（如CI和MAB）将以高概率删除低效用视图。我们可以这样形式化地表示这个性质。

性质4.1（一致性） 使目标和参考可视化都有$m$个组。$\hat{U}$表示基于$m$组均匀随机样本所估计的效用值$U$。那么随着样本个数趋于$\infty$，$\hat{U}$以$1-\delta$的概率趋于$U$，$\delta$越小越好。

我们称具有这个性质的距离函数为一致距离函数。一致的距离函数允许剪枝方案随着时间的推移收集越来越好的效用值估计（只要样本足够大）。在扩展的技术报告[37]中，我们用Hoeffding不等式证明了这个性质对于欧几里德距离是成立的。我们在5.4节和[37]的结果以经验为主地表明，基于CI和MAB的修剪方案适合各种指标，包括基于EMD的偏差、基于欧氏距离的偏差，以及根据目标分布和参考分布中各自组之间的差异对可视化进行排序的MAX_DIFF指标。

5 性能评估

在接下来的两个部分中，我们将从返回可视化时的性能和用户研究两方面对SEEDB进行评估。在这两部分中，我们报告了在表1中列出的各种真实和合成数据集上的SEEDB结果。

在本节中，我们将重点放在性能研究上，我们的目标是评估我们的共享和剪枝优化如何改善延迟，以及我们的剪枝优化如何影响准确性。在每个实验中，我们主要的评估指标是延迟，也就是说，SEEDB返回top-k可视化需要多长时间。对于涉及我们的剪枝策略的实验，我们通过两个额外的度量来衡量结果的质量，即准确性和效用距离（在第5.4节中进一步讨论）。因为我们期望数据布局会影响我们的优化效果，所以我们在面向行数据库（记作ROW）和面向列数据库（记作COL）上评估了我们的技术。

下面的实验使用EMD距离作为我们计算偏差的距离函数。所有的实验都是在一台8 GB RAM、16核Intel Xeon E5530处理器的机器上运行的。除非另有说明，否则我们报告三次运行的平均测量结果。我们首先总结了实验结果，然后深入研究各个优化的性能结果。

5.1 结果总结

图5.a和5.b通过表1中四个真实数据集(BANK、DIAB、AIR和AIR10)显示了SEEDB的表现概况。对于每个数据集，我们将显示在ROW和COL通过基本的SEEDB框架(NO OPT)存储并应用共享优化(SHARING)与剪枝优化(COMB)后的延迟。我们还展示了使用COMB (COMB_EARLY)产生早期结果的延迟，在这里，我们会在确定了top-k的可视化后返回近似结果。图5中的结果使用了置信区间(CI)修剪方案，k=10。

• 【>100X的总体提速】 我们的共享和修剪优化的结合提供了50X的提速(COMB)

  - 300X用于于ROW (COMB EARLY)(图5a)和10X (COMB)

  - 30X用于COL(COMB EARLY)(图5b)。这将小型数据集(如DIAB)的延迟从12秒缩短到200ms，大型数据集(如AIR10)的延迟从2小时缩短到数十秒。

• 【6-40X的共享提速】 共享优化(章节4.1)单独产生用于ROW的高达40X的性能增益和用于COL的6X提速

• 【5X的不损失精度的剪枝提速】 修剪优化(章节4.2)提供高达5X的额外增益。特别是，早期的结果返回能够实现对大型数据集的实时响应，例如，对于AIR, COMB_EARLY策略能使在处理完整数据集需要数十秒时，SEEDB在不到4s的时间内返回结果。我们还发现，修剪对结果的质量没有负面影响：我们的剪枝策略的效用距离(稍后定义)接近于0。

• 【乘数增益】 用于ROW存储的共享优化带来的40X增益与剪枝优化带来的5X增益相结合可以产生超过200X的总体增益(图5a)。

• 【在更大的数据集上的增益提高】AIR10 (300X)的总体增益要比BANK (10X)大得多。我们发现我们的共享优化最适合于像BANK和DIAB这样的小数据集，而COMB和COMB_EARLY对于像AIR和AIR10这样的大数据集是必不可少的。

6 用户研究

7 效用指标: 讨论

8 相关工作

9 结论

10 参考文献