ACM通信

研究突出了

与人群一起回答枚举查询

贝丝·特鲁什考斯基，蒂姆·卡拉斯卡，迈克尔·j·富兰克林，普尔纳姆丽塔·萨卡尔
ACM通信，2016年1月，第59卷第1期，118-127页
10.1145 / 2845644
评论

混合人/计算机数据库系统承诺通过结合人群来极大地扩展查询处理的有用性。这样的系统提出了许多实现问题。也许最根本的问题是，关系查询语义基础上的封闭世界假设在这样的系统中不成立。因此，即使是简单的查询的意义也会受到质疑。此外，由于众包数据到达时的不均匀性和人们在众包系统中工作的独特性，查询进度监视变得困难。为了解决这些问题，我们开发了统计工具，使用户和系统开发人员能够推断查询完整性。这些工具还可以帮助驱动查询执行和众包策略。我们在一个流行的众包平台上通过实验来评估我们的技术。

回到顶部

1.简介

最近的一些项目已经证明，利用众包可以极大地扩展查询处理系统的有用性，例如，CrowdDB，¹¹Qurk,¹⁹和独家新闻。^20.在这些系统中，可以调用人工工作者执行查询操作，如主观比较、谓词和连接的模糊匹配、实体解析等。

当然，在向查询处理中添加人员时，由于人工工作者在延迟、成本、质量和可预测性方面的特殊性，会出现许多挑战。研究人员已经解决了其中的许多问题，但我们观察到，将人群添加到数据库查询处理器会引发更基本的语义本质问题。关系查询语言是基于封闭世界假设，其中数据库在提出查询时被认为是完整的。也就是说，它包含回答查询所需的所有数据。当可以在查询处理过程中召集人群添加新数据时，这一假设就被违背了，即使是简单查询的意义也会受到质疑。

1.1.你能全部拿到吗?枚举查询

在本文中，我们考虑关系数据库管理系统(RDBMS)中最基本的操作之一，即扫描具有过滤约束的单个数据库表谓词;该查询列举用户感兴趣的一组特定项目。例如，考虑一个SQL查询，列出所有能忍受弱光环境的室内植物:从需要光=“低”的植物中选择不同的名称。对于传统的RDBMS和给定的数据库状态，该查询只有一个正确答案，可以通过扫描表、过滤记录并返回所有匹配的记录来获得。这种方法甚至适用于实际上是无界的关系，因为封闭世界假设规定，查询执行时数据库中没有出现的任何记录都不存在。

相反，在像CrowdDB这样的众包系统中，一旦存储表中的记录用完，作业就可以被发送到请求额外记录的人群中。那么问题就变成了:查询结果集何时完成?众包查询在本质上可能是模糊的，或者有无限的结果集，元组分散在网络上，或者只存在于人类的头脑中。例如，考虑一个查询当前就业市场上即将毕业的博士生列表，或者加利福尼亚对绿色技术感兴趣的公司列表。这些类型的查询是支持群体的数据库系统的主要用例，因为对于发出查询的用户来说，每一种查询都是劳动密集型的，但执行的频率不够高，无法证明复杂机器学习解决方案的开发、调优和使用是合理的。

在本文中，我们讨论了“用户应该如何考虑在众包数据库系统的开放世界中枚举查询?”我们开发了统计工具，使用户能够对时间/成本和完整性进行权衡，并可用于驱动查询执行和众包策略。

1.2.计算物种

我们技术的关键思想是使用来自人群的新答案到达率来推断查询的完整性。考虑执行一个“选择不同的在一个众包数据库系统中，工作人员被要求提供表的单个记录。例如，人们可以使用一个微任务众包平台(如亚马逊的Mechanical Turk (AMT))来查询美国50个州的名称，方法是生成HITs(即人工智能任务)，让工作人员提供一个或多个州的名称。当工作人员返回结果时，系统收集答案，保存一个唯一答案的列表。

图1显示运行该查询的结果，纵轴显示接收到的惟一答案的数量，而在x设在。正如预期的那样，最初未见答案的到达率很高，但随着查询的进行(已经看到了更多答案)，新答案的到达率开始逐渐下降，直到确定了全部人口(即在本例中，50个州)。

这种行为在诸如生物统计学等领域中是众所周知的，在这些领域中这种类型的数字被称为物种累积曲线(囊)。⁹想象一下，你试图通过连夜布设陷阱来数出岛上独特物种的数量，第二天早上确定陷阱中发现的独特物种，释放动物，每天重复这个过程。通过观察新物种被识别的速度，你可以推断出真实的物种数量，尽管是隐藏的。我们可以将此推理应用于众包查询处理器中的枚举查询。

1.3.论文概述

在本文中，我们应用统计学和生物学文献中的物种估计技术来理解和管理众包数据库系统中枚举查询的执行。我们发现，虽然经典理论为理解此类查询的意义提供了关键，但在微任务众包工作者的行为中存在某些特殊性，这要求我们开发新的方法来提高这种环境下结果集大小估计的准确性。

我们还描述了利用这些技术的方法，以帮助用户在时间/成本和完整性之间做出明智的权衡。这些技术的有用性超出了众包数据库的范围，例如，估计深度网络查询的完整性。

综上所述，我们作出了以下贡献:

• 我们将众包枚举过程形式化，并描述了它如何违反现有物种估计技术的基本统计假设。
• 我们开发了一种估计结果集大小的技术基数，以及在存在群体特定行为时查询进度。
• 我们设计了一种技术来确定是否可以应用数据抓取，并描述了一种现收现付的方法，以允许对成本/完整性的权衡做出明智的决定。
• 我们通过使用AMT的实验来检验我们的技术的有效性。

回到顶部

2.背景:CrowdDB

CrowdDB是一个混合的人机数据库系统，它使用人工输入来处理查询。CrowdDB支持不同的众包平台;本文主要关注AMT，即所谓微任务的领先平台。微任务通常不需要任何特殊训练，也不需要超过几分钟就能完成。AMT为请求者提供了一个市场，让他们发布微信号，让工作人员搜索并完成这些任务，获得少量奖励，通常是几美分。

CrowdDB集成了传统的查询编译、优化和执行组件，这些组件经过扩展以处理人工生成的输入。该系统扩展了特定于人群的组件，如用户界面(UI)管理器和质量控制/进度监视器。用户使用标准SQL的扩展CrowdSQL发出查询。UI Manager负责为人群工作者与之交互的微任务生成任务界面。CrowdDB自动生成作为HTML表单的ui人群注释。注意，与允许最终用户构造和提交查询请求的传统数据库系统前端ui不同，这些ui是数据库系统后端的一部分，呈现给帮助实际查询执行的人群工作人员。图2展示了一个HTML UI示例，它将被呈现给一个工作者，用于以下人群表定义:

在查询处理过程中，系统使用AMT web服务API自动发布一个或多个hit，并在它们到达时收集答案。在接收到答案之后，CrowdDB在将答案传递给查询执行引擎之前，会在人群工作人员之间使用多数票进行简单的质量控制。最后，系统不断更新查询结果，并根据新的答案对当前结果的质量进行评估。因此，一旦质量足够，用户就可以停止查询，或者在检测到问题时进行干预。富兰克林等人给出了关于CrowdDB组件和查询执行的更多细节。¹¹本文主要关注进度组件，该组件允许用户持续推断查询的完整性和成本。

回到顶部

3.进展的评估

为了在答案到达时评估进度，系统需要估计结果集的大小，也称为基数，以计算完成百分比。物种估计算法解决了一个类似的目标:通过对感兴趣地区物种的观察来确定不同物种数量的估计。在本节中，我们将描述对人群如何回答枚举查询的观察，以及对众包查询的估计挑战。我们提出了一个众包枚举模型，并列出了对人类容忍估计器的要求。

回到顶部

3.1.现有估计器的问题

人们发明了各种各样的技术来估计物种的数量^3.，6以及估计数据库表中不同值的数量。¹⁴它们都有相似的操作:从总体(例如，整个表)中随机抽取一个样本，并基于观察项目(不同值)的频率，估计不同值的真实和未知数量。这些技术最显著的不同在于它们的假设，特别是不同的值估计技术假设总体(即表)大小是已知的。不幸的是，只有在封闭的世界里才有可能了解人口规模;在允许众包枚举的系统中，记录可以按需获取，因此表的大小可能是无限的。我们专注于适合于开放世界的估计，因为它们允许无限的总体。

为了了解人群回答枚举查询的能力以及人群行为对现有估计技术的影响，我们将真实基数已知的集合元素众包。我们使用开放世界安全估计器“Chao92”⁷由于它在物种估计文献中被广泛应用。⁴图3在一个AMT实验中，我们将192个联合国(UN)成员国的名称众包，并将其与使用模拟的预期行为与来自联合国所有试验的经验数据分布(DD)进行比较。我们专注于单个具有代表性的实验，而不是多次运行的平均值，以调查用户将观察到的行为;平均也可以掩盖我们接下来描述的影响。

注意在图3这个估计值开始接近192的真实值，然而它随后显著增加高估了实验剩余时间的真实值。这是令人惊讶的，因为我们的模拟显示，当它接收到更多的数据(“预期的”)时，估计应该变得更加准确和稳定图3)．事实证明，群体工作者提供答案的方式深深地影响了估计算法的行为。例如，一些工作人员通过按字母顺序列出联合国成员国。然而，一些工作人员从他们知道的几个国家(如美国、印度、巴基斯坦、中国等)开始他们的回答序列，或者提供一个完全非字母顺序的序列。一般来说，人们可能会使用不同的内部偏差或技术来查找集合中的项(我们在Trushkowsky等人中讨论了完整的列表遍历。²²)．此外，每个工人完成不同数量的工作，在不同的时间点到达/离开实验。

3.2.人类枚举的模型

物种估计算法假设一个有替换的样本来自某个未知的分布，描述项目的可能性图4一)．在这个上下文中，示例元素到达的顺序是无关的。

在分析了众包枚举(例如，在前面提到的联合国实验中)后，我们发现这个假设并不成立。与有替换的样本相比，个体工作者通常从底层分布中提供答案没有更换。此外，工作人员可能从不同的底层分布中取样(例如，一个可能按字母顺序提供答案，而另一个可能按不同的顺序提供答案)。

这个抽样过程与传统估计的假设有很大的不同，它可以表示为一个两层抽样过程，如图4 b．底层由许多抽样过程组成，每个抽样过程对应于某个DD中的单个工作者没有更换。顶层处理样品与从底层流程(即工作人员)的集合中进行替换。因此，从人群中得到的有序的答案流表示在工人中进行有替换抽样，每个工人抽样一个没有替换的DD。

接下来我们讨论两层抽样过程的参数化(例如工作过程的数量、不同的底层分布等)对估计的影响。

3.3.取样不更换和工人倾斜

个体从描述选择每个项目可能性的底层分布中进行抽样而不进行替换。这种行为对于获取集合中所有物品的目标是有益的，因为在高概率物品已经由该工人提供之后，低概率物品更有可能出现(我们不会为单个工人的重复工作付费)。然而，一个负面的副作用是，估计器接收到的关于项目的相对频率的信息较少，从而导致潜在DD的倾斜。这可能导致估计器过度预测，因为与有替换的样本相比，看不见的项目更快地到达。

当一些工人比其他人完成更多的命中时，过度预测也会产生;工作量明显增加的工人被称为“裸奔者”。¹⁵在双层抽样过程中，工人倾斜(WS)决定了哪个工人提供下一个答案过程;裸奔者被选中的频率更高。高WS会导致唯一答案的到达率比不进行替换的抽样导致的到达率更快，导致估计器过度预测。

在一个工人提供所有答案的极端情况下，两层流程减少到一个底层分布的一个流程抽样，没有替换。在这种情况下，完整性估计变得不可能，因为无法对底层分布进行推断。另一种极端情况是，如果有无限数量的工作者使用相同的底层分布提供一个答案，所得样本将对应于有替换情况的抽样(图4一)．后者就是为什么尽管有人工生成的枚举，仍然可以进行估计的原因。

为了说明参与基于人群的枚举的工人数量对Chao92估计量的影响，我们模拟了从超过200个项目的均匀分布中抽样的不同数量的工人，平均超过100次。图5一个描述了在三种情况下，随着样本数量的增加而计算的Chao92估计量的值:一个有替换的样本(相当于无限数量的工人)，以及三个或五个工人，每个抽样不从项目分布中替换。正如预期的那样，由于统一的DD，带有替换的样本稍微高估了一些，但很快就接近了200的真实值。没有替代的样本，只有更少的工人，会高估更多，并在更长时间内保持这种状态。

3.4.不同且扭曲的数据分布

个体工人可能从不同的dd中得出他们的答案:一个工人最可能得到的东西可能是另一个工人最不可能得到的东西。这些差异可能来自不同的文化或地区偏见，或在网上寻找数据的替代技术。将同一数据上的多个分布混合在一起，会产生一个比其组成部分更“平坦”的组合分布，变得不那么倾斜。相反，当底层DD严重倾斜并在工作人员之间共享时，估计器将低估，因为没有足够数量的项表示分布的尾部。

图5 b表示不同的dd结合不同的WS对Chao92估计的影响。它显示了四种组合:WS的缺失/存在和工作者的共享/不同dd。对于所有情况，我们使用幂律DD，其中最可能的项目具有概率p，第二种可能性有概率p（1p),k最有可能的项目有概率p（1p）^k1等;我们设置p= 0.03。为了模拟不同的dd，我们对每个worker的原始分布进行随机排列。

模拟结果表明，最坏情况的特征是高WS和单一共享DD (WS = T和DD = F)。在共享倾斜分布下，Chao92将开始低估，因为所有工人都回答了相同的高概率项目。在高WS的情况下，裸线者会快速提供许多唯一答案，导致比有替换的抽样遇到的更多的唯一项。

另一方面，最好的情况是没有WS但有不同的DD (WS = F和DD = T)。通过使用不同的DD而不过度强调少数工人，整个样本看起来更统一，类似于图5一个，由于DD对倾斜数据的扁平化效应。

3.5.工人的到来

最后，在实验过程中，工人的到达和离开会影响估计。并不是所有的工作程序都在查询的生命周期内提供答案。然而，当裸奔者出现时，估计器可能会受到强烈的影响，他们突然主导了总答案的数量。

图5 c展示了一个工人所能产生的影响。它使用与前面相同的模拟设置图5 b，但也包括一个额外的单裸奔者，从200点击开始，在其他人有机会提交另一个答案之前，持续提供所有200个答案。如图所示，它导致Chao92在所有四种情况下都过度预测。然而，如果员工使用不同的dd，影响就不会那么严重。同样，这是因为DD使样本看起来分布更加均匀。

3.6.讨论

工作人员在响应枚举查询时所表现出的一些行为在诸如AMT这样的市场中是固有的，例如单个工作人员选择完成多少任务。每个员工给出答案的顺序和给出的数量取决于个人的偏见和偏好。我们上面概述的人群行为的四个因素(无替换抽样、WS、不同分布和工人到达)都可能导致Chao92表现不佳。这些行为中最不稳定的是WS，特别是当DD本身是倾斜的;一个过分热心的工作人员可能会造成估算的巨大波动。过高估计尤其有问题，因为它可能导致不必要的众包成本，试图列举更多实际上不存在的集合项目。但是，我们不希望禁止单个工作者，特别是高生产率的工作者提交响应，因为这样做会减慢或限制查询的进度。因此，我们想让Chao92对这样的裸奔者的影响更宽容，同时仍然允许裸奔者提交答案;接下来我们将讨论容条纹的基数估计技术。

回到顶部

4.Streaker-Tolerant估计量

我们的目标是根据目前收集到的答案为一个开放世界查询提供一个进度估计。在本节中，我们扩展了Chao92估计，使其对单个工人的影响更加稳健，并将精力集中在减少裸奔者和工人到达的影响上。在我们介绍处理裸奔者的扩展之前，我们首先更正式地介绍基本估计器模型和Chao92。我们首先提出了一个新的度量，该度量包含了估计稳定性和快速收敛到真实基数的概念，然后应用该度量来衡量我们的技术的有效性。

4.1.基本估计器模型和f统计

从工作人员那里得到答案，就好比从一些未知大小的潜在分布中抽取样本N;每个答案对应项目分布中的一个样本。我们可以将该问题重新表述为一个物种估计问题，如下所示:从AMT接收到的HITs集合是一个大小的样本n从一个元素可以来自N不同的类别，编号1N（N，未知，是我们所追求的);c是在样本中看到的唯一类(种)的数量。让n_我是样本中属于类的元素的数量我, 1我N。当然一些n_我= 0，因为在样品中没有观察到。让p_我是一个元素从类的概率我是由工人选择的，．

伯纳姆和欧⁵显示聚合的“频率的频率”-统计(这里f-statistic)足以估计非参数算法中未观察物种的数量。的f-statistic捕获样本中观察到的类的相对频率。让f_j是类的数量j样本中的成员。目标是通过预测来估计基数f₀，不可见类的数量。

4.2.Chao92的估计量

的Chao92⁷估计使用样本覆盖预测N。样例报道C是概率的和吗p_我观察到的类别。因为基础分布p₁.．.p_N是未知的，古德-图灵估计量¹²使用f使用统计:

Chao92估计器试图显式地描述和合并底层分布的倾斜方差系数(CV)，一个用来描述概率分布方差的度量⁷；我们可以用CV来比较不同阶层分布的倾斜程度。CV定义为标准差除以均值。考虑到p_我(p₁.．.p_N的概率我被选中的班级，带着平均值， CV表示为．⁷更高的CV意味着更高的方差p_我的年代;CV为0意味着每一项都是等可能的。

真正的CV是不可能计算出来的p_我，所以Chao92估计基于f统计:

最后的估计量定义为:

4.3.用于众包枚举的估计器

Chao92估计量受样本中稀有元素的影响很大;报道估计完全基于单例答案的百分比(f₁回想第3节中对不同人群行为的讨论，其中许多行为会导致之前未见的答案迅速出现。当这些新f₁项目出现得“太快了”，估计者将其解释为一个信号，表明整个集合的大小比它的实际大小要大。我们开发了一个基于Chao92的估计器，它改善了一些由过量的f₁的答案。

大多数戏剧性的高估都是由裸奔者造成的，也就是说，每个工作者提供的答案数量有明显的偏差。值得注意的是，当一个或几个工人贡献的答案比其他人多得多时，问题就发生了，可能也从不同的DD中获得了答案。因为其他工人没有机会提供答案，而这些答案会增加f₂年代,f_3.s等，Chao92预测的总集合基数过大。因此，我们的估计器被设计用来识别与他们在样本中对唯一答案的贡献相关的任何异常值工作者(他们的f₁答案)。

使Chao92估计器对裸奔者更有弹性的背后的想法是改变f统计。第一步是确定那些“f₁离群值。”我们传统上定义离群值，即所有劳动者均值之外的两个标准差W。为了避免由于真实离群值对平均值和标准差的影响而造成的假阴性，计算这两个统计值时不包括潜在离群值f₁计数。的f₁统计的工作我与平均值相比还有样本标准差：

我们创建从原来的f₁通过减少每个工人我的f₁-贡献落在：

最终估计量与式(3)相似，不同之处在于它使用了统计。例如，简历，则简化为:

虽然调整很小，在对抗裸奔者的影响上比原始的Chao92更强大，如下所示。

4.4.实验结果

我们在AMT上为枚举任务运行了30000多个点击。的人群我们实验的桌子包括大大小小的有明确定义的场景，如NBA球队、美国各州、联合国成员国，以及真正能利用人类感知和体验的场景，如有弱光需求的室内植物、旧金山供应扇贝、苗条无尾礼服和冰淇淋口味的餐厅。工作人员的报酬是0.01美元和0.05美元，他们使用类似于的UI在结果集中提供一个项目图2；如果他们想提交多个答案，他们可以完成多个任务。在本文的其余部分中，我们将重点关注实验的一个子集，两个具有已知基数和固定成员的实验，美国州(9次实验运行)和联合国成员国(5次实验运行)，以及更多的开放式查询(各一次运行)。

误差度量。由于缺乏一个很好的度量来评估估计器的稳定性和收敛速度，我们开发了一个误差度量来捕获偏差(与真值的绝对距离)，以及估计器的收敛和稳定时间。其思想是随着样本大小的增加，对估计量偏差的幅度进行更多的加权。让N表示已知的真值，和表示估算我样本。后n样本,定义:

较低意味着较小的平均偏差，因此更好的估计。除了对需要较长时间才能达到真实值的估计器进行惩罚之外，加权对以后的错误给予比开始时更严厉的惩罚，以满足收敛速度标准。该指标还会奖励接近真实值的评估人员。

结果:联合国和各国。我们首先说明如何作为联合国成员国和美国国家的一组代表性实验;由于空间的原因，我们省略了整个集合。正如第3节中所讨论的，我们不平均实验运行的结果，因为每次运行可能有不同的数据和WSs;平均可以掩盖工人行为对估计量的影响。

图6 ag)显示这些实验的基数估计以及度量。每个图显示了Chao92算法的估计(标记为“原始”)和为这些估计计算的误差度量值(_源自)，以及估计和误差(_新)用于容忍裸奔估计器(标记为“人群估计器”)。我们观察到，对于大多数联合国实验，我们的估计比Chao92有改进。

在标记为un1的实验运行中，我们的估计避免了实验中出现的对Chao92的过高估计。在UN 2实验中，一名裸奔者在开始时占据了全部答案集——这是一个实质性的异常值。一旦他/她的贡献大幅减少，剩下的工作人员的答案就会有明显的重叠，因为大多数人都是按字母顺序列出国家列表，这导致基数较低，因为这种情况产生了严重倾斜的DD。回顾前一节，在这种情况下，估计器的预期行为是tounder-predict。相比之下，联合国的第三次试验一开始就有几个裸奔者，每个人的dd都非常不同(也就是说，从不同的字母起点列举国家的名单)。而启发式有助于平衡f₁由于这些工作者的贡献，由于他们给出的单例答案的总和，仍然会出现高估的情况。在少数情况下，我们的估计器的性能比Chao92差，例如，实验运行un4。当工人共享高度倾斜的分布时，低估是可能的;裸奔者导致的估计值高于它应该产生的值，偶然间产生一个更接近真实值的值。

与Chao92相比，我们估计的效果在WS较少的States实验中不太显著。图6 e而且f展示了美国两个州的实验，有中度裸奔问题，帮助．在第三个状态实验中(图6克)，我们的估计减少了裸奔者的影响，但由于类似于联合国实验第4步的原因，需要更长的时间才能收敛。

结果:开放式用例。联合国国家和美国州用例都是集合，其真实基数以及集合的内容都是已知的;已知基数的用例允许我们评估估计算法的准确性。这里我们研究“开放式”的用例，也就是说，集合内容和基数是未知的。对于这些结果，我们只能比较估计算法。开放式用例展示了我们在联合国实验中观察到的几种工人行为;特别是裸奔者。图7的广告show Chao92和我们的用于植物，餐厅，礼服和冰淇淋口味的实验。

在所有情况下，我们的估计器成功地减少了这些裸奔对完备集基数预测的影响。注意，我们不能对这些实验的误差进行评估，因为真正的基数是未知的。在植物实验期间(图7)，其中一个工人从一开始就比其他工人贡献更多的独特答案，例如，一个不太知名的植物“兔蹄”;许多工人坚持众所周知的答案(例如，蛇草，和平百合)。相比之下，在餐厅实验中(图7 b)一个裸奔者贡献了很多f₁但其他工作人员最终提供了许多相同的答案。燕尾服实验(图7 c)显示了一个裸奔者在实验后期到达的影响，导致Chao92估计的急剧增加，这得益于．

4.5.讨论

我们表明，我们的估计器成功地提供了更准确的预测，以人群为基础的枚举存在过度热心的工人。我们的技术专门处理基数过高估计，这可能导致发出查询的用户认为结果集没有实际完整。然而，任何估计器都只能处理一定范围的工作者行为。在只有一个工作者提供答案的极端情况下，或者如果工作者共享一个严重倾斜的分布，将证明对估计者是困难的。我们运行的大多数实验没有这些问题，启发式能够改善工人行为对估计的影响。

回到顶部

5.表走

当工作者共享相同或多个严重倾斜的DD时，估计器可能会低估总集大小。如果工作人员遍历同一个列表寻找答案，就会出现这种严重倾斜的分布;我们把这种效应称为列表中行走。检测列表遍历使得改变众包策略以节省资金成为可能。如果存在一个或两个包含完整集合的列表，例如联合国国家，这种切换可能有助于获取所有列表。然而，没有单一列表存在的转换策略是没有意义的。

检测列表游走的目标是区分从倾斜项目分布中提取的样本和列表的存在，这将导致确定的答案序列。在本节中，我们开发了一个启发式方法来确定给定数量的工人w将会回复年代答案的顺序完全一样。如果这个概率低于一个阈值(我们使用0.01)，我们得出结论，列表遍历很可能存在。

5.1.初步设置:二项分布

让W是提供长度的答案序列的工人总数年代或者更多。在这其中,让w是有相同长度的答案序列的工人的数量年代从相同的偏移量开始o共同之处。我们把这个序列称为目标序列的长度年代，它本身是由单个的答案组成的_我在每一个位置我从偏移量o（= (_o＋1、……_o+年代))。如果p观察到某个工蚁序列的概率，我们感兴趣的是这个概率w的W所有工人都有这样的顺序。此外，在我们的情形中，我们不一定关心的概率w工人提供相同的顺序，而是概率w或更多这个概率可以用二项分布表示:W对应于试验和的次数w表示成功的次数:

式(8)中的概率决定了目标序列是否共享于w的W工人很可能是由于走单造成的。我们现在讨论p，表示观察到特定目标序列的概率的长度年代。

5.2.目标序列的概率

并不是所有的工作人员都使用相同的列表或使用相同的顺序来遍历列表，所以我们希望p以反映工人观察到的答案序列。我们通过估计概率来做到这一点p（我)遇到答案_我在我目标序列的位置乘以这个答案出现在我在所有人中的位置W的答案。让r（我)是回答的次数_我出现在我在所有序列中的位置W相比较,p（我)定义为r_我/W．例如，如果目标序列从偏移量o是“A, B, C”，四个工人的第一个答案分别是“A”，“A”，“A”和“B”，r_o＋1/W将3/4。现在是看到的概率是观察概率的乘积吗_o＋1,然后_{o+ 2}等。

仅以这种方式依赖数据在极端情况下可能会导致假阴性w＝W，即所有工作人员使用相同的目标序列。注意，在本例中p获得可能的最大值1。我们需要把这两个真实的数据r_我/W以及对潜在倾斜的悲观信念。作为悲观先验，我们选择高度倾斜的格雷自相似分布，¹³通常用于80/20规则。只有当我们发现一个无法用80/20分布解释(概率超过1%)的序列时，我们才相信我们遇到了列表遍历。假设一个高偏度分布是保守的，因为如果他们真的在抽样，工人们更有可能以相同的顺序回答，而不是在均匀分布。我们假设目标序列完全遵循自相似分布，总是选择最可能的序列。在这种情况下就是一个最可能的答案的串联，然后是第二个最可能的答案，以此类推。在我们的先验信念下选择这个序列的可能性是(1h）^年代而一组的可能性w工人选择此顺序为:

为了结合从数据得到的分布和我们先前对最大倾斜的信念，我们使用平滑因子将重点从数据转移到分布;更高的值把重点放在数据上。使用将式(9)和式(10)结合，得到有目标序列的概率(长度年代)共同之处:

5.3.实验结果

我们将我们的启发式应用到AMT实验中，观察目标序列至少长度年代= 5。也就是说，对于至少大小的答案序列年代我们用式(8)计算该序列出现的概率。如果概率低于阈值0.01，则认为该序列是一个列表。我们检查列表在一段时间内的使用情况(点击数)，并量化观察到的点击数中有多少是列表的一部分;这让我们了解了在实验中使用列表的影响。由于空间原因，我们描述了联合国一次试验的结果。

图8显示了在联合国的一个实验中受影响的HITs的数量。直线对应于用式(11取值为0.2、0.5、0.8。较低的值检测较少的列表(或者需要更多的HITs来检测列表)。

我们的结果表明，我们的启发式能够检测到当多个工作者正在查询同一个列表时，以及列表遍历的严重程度。例如，据报告，在UN 2的实验中，约2025%的点击量受到列表移动的影响。在美国的实验中，很少或根本没有清单行走。尽管网站上显示了美国各州的名单，但我们认为，工人们并不觉得想州的名字太难，就不能上网查询。

开放式用例也包含很少或不包含列表遍历。未来，我们计划检测列表遍历，并切换到从web上抓取信息。

回到顶部

6.成本与收益:现收现付

对于有限成员的集合，估计集合大小并利用人群来提供完整的集合是有意义的。然而，某些查询的结果集可能具有无界大小、高度倾斜的分布和/或极端的工作者行为，这使得预测其大小变得毫无意义，如第3节所述。对于这些情况，更有意义的是尝试估计花更多钱的收益，也就是说，预测SAC的形状(例如，图1)在不久的将来。

再一次，我们利用物种估计算法来创建现收现付制预测这种成本与通过付出额外努力获得更多答案的收益权衡的技术。我们评估了Shen等人开发的估计器的有效性。²¹确定有多少未见物品会到达米来自工人的额外回答;这种分析将在收到之后进行n答案(点击)。总的来说，我们发现预测为小米更准确，因为只考虑不久的将来。越大米，预测的距离越远，结果就越容易出错，特别是如果米超过当前的HITs大小n。²¹Trushkowsky等人对现收现付的方法和实验结果进行了完整的描述。²²

回到顶部

7.相关工作

在本文中，我们关注于估计查询结果集的完成进度，这是查询质量的一个方面。已经提出了质量控制技术，可用于验证单个集合元素。^10，16这项工作是CrowdDB的一部分，¹¹但它可以应用于其他混合数据库系统，使用人群来枚举集合。

我们的估计技术建立在现有物种估计工作的基础上。^3.，6，9这些技术在数据库文献中也得到了扩展，用于不同的价值估计，^8，14但这项工作没有考虑人类行为如何影响众包查询的抽样过程。

物种估计技术已经被用于搜索和元搜索引擎。在Broder等人。²作者根据以前的查询开发了一种算法来估计由特定条件定义的任何文档集的大小。刘等人。¹⁷描述一种估计元搜索引擎语料库大小的算法，以更好地将查询导向搜索引擎。类似的技术也被用来衡量搜索引擎的质量。¹最近的工作探索了深度网络的物种估计技术，¹⁸然而，它没有考虑具体的工人行为，并假设有替换的抽样。

回到顶部

8.结论

人们特别适合收集新信息，因为他们可以获得现实生活经验和在线信息来源。然而，将众包信息合并到数据库中，就会产生关于查询结果的意义的问题，如果没有封闭世界的假设，一个人如何推理一个简单的选择*查询?我们认为，进度估计允许用户在开放世界中理解查询结果。通过计算枚举查询的预期结果集大小或基数的估计值，可以形成该集的完整程度的估计值。

物种估计文献为解决基数估计问题提供了一个起点。然而，将现有的估计量应用于来自人群的响应序列会产生不准确的结果。

众包枚举不是来自单个项目分布的有替换样本，而是来自可能不同分布上的许多无替换抽样过程的有替换抽样过程。

一个特别麻烦的问题是“裸跑者”的存在，这些工人完成的点击量比其他工人多很多，导致估计器严重高估基数。为了改善这些过分热心的工人所造成的问题，我们开发了一种streaker-tolerant估计量。通过在AMT上运行的枚举实验，我们表明该估计器成功地减少了裸跑者的影响，并产生了更准确的估计。

在本文中，我们研究了RDBMS中使用的一种常见操作:从众包关系中枚举项目。当然，现代数据库系统支持许多其他的操作，称为关系操作符，这些操作符可以组合起来形成表达性更强的查询。

我们相信，我们描述的结果集大小估计技术可以用于这些表达性更强的查询。有些操作符很容易应用于众包枚举结果的后续处理步骤。如果处理人群提供的每个项目以生成单个项目，则可以直接应用基数估计技术来推断最终查询结果的完整性。一个例子是项目操作符，该操作符只向用户返回关于每个项目的部分信息，例如只返回植物查询中每个植物的学名。相比之下，考虑一下加入运算符，它组合来自多个关系的数据，这个过程通常根据某个谓词匹配来自两个关系的项对。在这种情况下，对结果集大小的估计可能需要包含关于项目匹配可能性的统计信息。rdbms中的另一个常见操作是聚合，例如，确定能忍受弱光的植物的平均高度。平均数可以用目前从人群工作者那里收到的一组回复来计算;基数估计技术可能有助于估计该平均值的置信度，或当前计算与真实值的接近程度。此外，最近的工作还探索了如何使用人群输入来减少此类操作在脏的和不完整的数据集上查询答案的不确定性。²³

将人群纳入查询处理系统提供了扩展这些系统的有用性的机会，但也提出了关于查询结果意义的基本问题。我们在本文中开发和描述的基数估计方法支持查询进度估计，从而允许用户理解来自混合人/机数据库系统的查询结果。通过采用统计技术，我们允许用户推理开放世界中的查询完整性。

回到顶部

致谢

这项工作的灵感来自于CrowdDB项目，我们要感谢我们的CrowdDB合作者Donald Kossmann, Sukriti Ramesh和Reynold Xin。

本研究部分由NSF研究生奖学金支持，部分由NSF CISE探险奖CCF-1139158支持，以及来自亚马逊、谷歌、SAP、Blue Goji、思科、Cloudera、爱立信、通用电气、惠普、华为、英特尔、微软、NetApp、Oracle、广达、Splunk、VMware和DARPA(合同#FA8650-11-C-7136)的捐赠。

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2016 ACM, Inc.

---

没有发现记录