利用众人的力量回答枚举查询.PDFVIP

研究亮点 DOI:10.1145/2845644 利用众人的力量回答枚举查询 作者：Beth Trushkowsky、Tim Kraska、Michael J. Franklin 和 Purnamrita Sarkar 摘要 据库状态时，此查询只有一个正确的答案，通过扫描 人力/ 计算机混合型数据库系统有望通过融合众人之 相关表格、筛选记录，再返回所有匹配的记录即可获 力来大大拓展查询处理的实用性。这样的系统提出了 得该答案。这种方法对即便实际上无界的关系也奏效， 许多实施问题。或许，最基本的问题是作为关系查询 因为封闭世界假定指出：在查询执行之时数据库中没 语义的基础的封闭世界假定并不能囊括此类系统。这 有的任何记录都不存在。 造成即使简单查询的意义也会产生疑问。此外，由于 相反，在 CrowdDB 等众包系统中，一旦耗尽已 众包数据到达的不均匀性，以及人力在众包系统中工 存储表格中的记录时，我们可以向众人发送作业来索 作方式的特性，使得查询进度监控变得困难。为解决 取更多记录。然后问题演变为：查询结果集何时才算 这些问题，我们开发了一些统计学工具，让用户和系 完整？众包查询天生具有模糊性或拥有无界结果集， 统开发人员能够推导出查询完整度。这些工具也能帮 其元组分散于网络或者仅存在于人脑。例如，我们可 助推动查询执行与众包策略。我们在一个流行众包平 以思考这样的查询：列出就业市场上现有的博士学位 应届毕业生，或者列出加利福尼亚州对绿色技术感兴 台上进行实验，以此评估我们的技术。 趣的企业。这种查询是利用众人力量的数据库系统的 主要用例，对发出要执行的查询的用户而言均属于劳 1. 简介 动密集型任务，但由于并不经常需要执行，所以不一 许多近期的项目显现出，利用众包可以大幅拓展查询 定值得去开发、调节和使用复杂的机器学习解决方案。 11 Qurk19 和 sCOOP 在本文中，我们将解决以下问题：“用户在众包 处理系统的有用性，如 CrowdDB 、 等。20 在这些系统中，可以调动人类工人来执行查询 数据库系统的开放世界中应当如何思索枚举查询？” 运算，如主观比较、断言和连接的模糊匹配，以及实 我们开发的统计学工具可以帮助用户推导时间/ 成本 体分解等。 与完整度的权衡，还可用于推进查询执行和众包策略。 当然，由于人类工人在延迟性、成本、质量和可 预测性上的特质，若在查询处理中加入人力会涌现许 1.2. 计算物种 多挑战。研究人员已经攻克了许多这样的问题，但我 我们技术的关键理念是利用众人提供的新答案的到达 们发现，在数据库查询处理程序中加入众人还会引起 率来推导查询的完整度。我们可以思考在众包数据库 更为基本的语义性质问题。关系查询语言的基础是封 系统中执行“SELECT DISTINCT *”查询，其要求 闭世界假定，在这种假定中，数据库在查询提出之时 工人提供表格的各条记录。例如，可以利用微任务众 被视为是完整的。也就是说，它包含回答查询所需的 包平台（如亚马逊的 Mechanical Turk (AMT) ）生成让 全部数据。如果查询处理期间可以招募众人来添加新 工人提供一个或多个州名称的 HIT （即，人类智慧任 的数据，这一假定就被违反，造成即使简单查询的意 务），以此查询美国 50 个州的名称。当工人返回结果 义也会产生疑问。 时，系统将收集答案，并且保管唯一答案的列表。 图 1 显示了运行该查询的结果，其纵轴显示收到