【博士论文】众包数据库关键技术研究

2020 年 12 月 12 日 专知

来自清华大学柴成亮的博士论文，入选2020年度“CCF优秀博士学位论文奖”初评名单！

https://www.ccf.org.cn/Focus/2020-12-03/717578.shtml

众包数据库关键技术研究

众包通过整合计算机和互联⽹⼤众来完成机器难以单独处理的任务，其主要包含三部分，任务发布者、众包平台和众包⼯⼈。传统众包技术中，三者的交互流程过于复杂，导致任务发布者⽆法很好地管理任务。因此，众包数据库应运⽽⽣，其从系统层⾯出发整合三者之间复杂的交互流程，使得任务发布者可以通过描述性语⾔轻松利⽤⼯⼈操作数据，降低了众包的使⽤门槛。本⽂主要的内容如下：

1. 众包数据库 CDB：为解决众包平台难使⽤、众包任务难优化、众包⼯⼈质量难控制等问题，需要通过数据库的思想来封装众包任务处理的流程。与传统数据库不同的是，众包数据库的难点不仅在于解决单⼀⽬标优化问题 (仅优化代价)，更重要的是建⽴细粒度的查询优化模型，实现代价、质量和延迟的多⽬标优化。因此，本⽂提出了⼀种新型的众包数据库系统 CDB 。不同于传统的树优化模型，CDB ⾸次提出利⽤图模型来进⾏细粒度查询优化。其次，CDB 在该模型上建⽴统⼀的框架来进⾏多⽬标优化。该系统致⼒于帮助用户高效率、高质量、低成本地利用众包来处理数据, 构建了一个中文众包平台 ChinaCrowd, 在华为公司落地应用，取得了较好的经济收益。另外，为⽀持较复杂的连接操作（基于记录或者⾃连接）与收集操作，本⽂分别提出了以下两种算法框架对它们进⼀步优化。

2. 基于众包的连接操作：为解决现实世界中脏数据的复杂连接问题，需要引⼊基于众包的连接操作。其难点在于代价较⾼，⽽寻求低代价⽅案时往往带来质量的降低。为此，本⽂提出⼀种低代价的众包实体匹配框架 Power，在保持⾼质量的同时⼤⼤降低代价。本⽂⾸先在待连接的记录对上定义了⼀种偏序关系，然后基于该关系对众包⼯⼈的回答进⾏推理，接下来循环提问直到所有记录对的答案都被推理出来。该方法致力于从理论和实践两方面优化众包成本，实验表明相比于其他方法，Power 可在节省高达 100 倍的成本下进行高质量的数据连接。

3. 基于众包的收集操作：为解决传统数据库不能处理数据库以外数据的特点，众包数据库需要引⼊收集操作，其旨在通过众包收集数据库中缺失的实体。其难点在于如何保证收集实体的正确性；如何尽可能收集相关领域的全部实体；如何减少重复实体的数量以减少代价。为此，本⽂提出了基于激励机制的众包实体收集框架 CrowdEC，其采⽤激励的⽅式⿎励⼯⼈提供不重复的实体以降低代价。该方法致力于建立收集操作的质量评价体系，从理论上给出了收集代价的竞争比保证，使得用户可实现低成本、高质量、高覆盖的收集。