时空众包数据管理技术研究综述-童咏昕 , 袁野 , 成雨蓉 , 陈雷 , 王国仁.pdf

上善若水

562

24页

0次

2022-05-20

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2017,28(1):35−58 [doi: 10.13328/j.cnki.jos.005140] http://www.jos.org.cn

时空众包数据管理技术研究综述

∗

童咏昕

1,2

袁

野

成雨蓉

陈

雷

王国仁

(软件开发环境国家重点实验室(北京航空航天大学),北京 100191)

(北京航空航天大学计算机学院,北京 100191)

(东北大学计算机科学与工程学院,辽宁沈阳 110004)

(香港科技大学计算机科学与工程学系,香港)

通讯作者: 童咏昕, E-mail: yxtong@buaa.edu.cn

摘要: 近年来,众包为传统数据管理提供了一种通过汇聚群体智慧求解问题的新模式,并成为当前数据库领域

的研究热点之一.特别是随着移动互联网技术与共享经济模式的快速发展,众包技术已融入到各类具有时空数据的

应用场景中,例如各类 O2O(online-to-offline)应用、实时交通监控与动态物流管理等.简言之,这种应用众包技术处

理时空数据的方式称为时空众包数据管理.对近期在时空众包数据管理方面的研究工作进行综述,首先阐述了时空

众包的概念,解释了其与传统众包技术的关系,并介绍了各类典型的时空众包应用;随后描述了时空众包应用平台的

工作流程及其任务特点;然后讨论了时空众包数据管理的 3 项核心研究问题和 3 类应用技术;最后,总结了时空众包

数据管理技术的研究现状并展望了其未来潜在的研究方向,为相关研究人员提供了有价值的参考.

关键词: 时空众包;共享经济;O2O 模式;任务分配;质量控制;隐私保护

中图法分类号: TP311

中文引用格式: 童咏昕,袁野,成雨蓉,陈雷,王国仁.时空众包数据管理技术研究综述.软件学报,2017,28(1):35−58. http://www.

jos.org.cn/1000-9825/5140.htm

英文引用格式: Tong YX, Yuan Y, Cheng YR, Chen L, Wang GR. Survey on spatiotemporal crowdsourced data management

techniques. Ruan Jian Xue Bao/Journal of Software, 2017,28(1):35−58 (in Chinese). http://www.jos.org.cn/1000-9825/5140.htm

Survey on Spatiotemporal Crowdsourced Data Management Techniques

TONG Yong-Xin

1,2

, YUAN Ye

, CHENG Yu-Rong

, CHEN Lei

, WANG Guo-Ren

(State Key Laboratory of Software Development Environmnt (Beihang University), Beijing 100191, China)

(School of Computer Science and Engineering, Beihang University, Beijing 100191, China)

(School of Computer Science and Engineering, Northeastern University, Shenyang 110004, China)

(Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Hong Kong, China)

Abstract: In recent years, crowdsourcing, which utilizes the intelligence of crowds to solve problems, provides a novel data processing

paradigm for traditional data management challenges and has become one of the hottest research topics. In particular, due to the rapid

development of mobile Internet and sharing economy, crowdsourcing not only becomes a new approach for data collection, but is also

integrated into all kinds of application scenarios especially spatiotemporal data management such as online-to-offline (O2O) applications,

∗ 基金项目: 国家重点基础研究发展计划(973)(2014CB340300); 国家自然科学基金(61502021, 61622202, 61572119, U1401256);

北京航空航天大学软件开发环境国家重点实验室开放课题(SKLSDE-2016ZX-13)

Foundation item: National Basic Research Program of China (973) (2014CB340300); National Natural Science Foundation of China

(61502021, 61622202, 61572119, U1401256); State Key Laboratory of Software Development Environment (Beihang University) Open

Program (SKLSDE-2016ZX-13)

收稿时间: 2016-10-08; 修改时间: 2016-10-24; 采用时间: 2016-11-17; jos 在线出版时间: 2016-11-24

CNKI 网络优先出版: 2016-11-24 13:41:16, http://www.cnki.net/kcms/detail/11.2560.TP.20161124.1341.007.html

Journal of Software 软件学报 Vol.28, No.1, January 2017

real-time traffic monitoring, and logistics management. In this paper, a survey is provided on existing research of spatiotemporal

crowdsourcing. First of all, the concept and representative applications of spatiotemporal crowdsourcing is described, and its relationship

with traditional crowdsourcing is explained. Then, the workflow of spatiotemporal crowdsourcing is illustrated. Furthermore, three core

research problems and three categories of techniques of spatiotemporal crowdsourcing are discussed. Finally, the state-of-the-art studies of

spatiotemporal crowdsourcing are summarized and promising future research directions for the research community are presented.

Key words: spatiotemporal crowdsourcing; sharing economy; O2O mode; task assignment; quality control; privacy protection

随着 Web 2.0 技术的兴起,大量在线 We b 应用正在悄然地改变着人类的生活模式,同时也为传统的人本计

算(human computation)提供了一种通过群体智慧求解问题的新模式——众包(crowdsourcing)

[1]

.所谓众包,通常

是指“一种把过去由专职员工执行的工作任务通过公开的 Web 平台,以自愿的形式外包给非特定的解决方案提

供者群体来完成的分布式问题求解模式”

[2]

.在过去的 10 余年里,众包技术已与人们的日常生活息息相关.例如,

早期的众包平台通常指“问答系统”平台,如维基百科(wikipedia)、雅虎问答(Yahoo! answers)与百度知道等,发展

至今已成为现代人们获取知识的必需品.近年来,由于早期众包平台所支持的任务类型单一,其已不能满足当前

数据类型多样化与任务复杂化的 Web 应用需求,这也促使新一代“在线众包平台”的诞生,即,大型在线工作招募

与任务分包管理平台,例如 Amazon Mechanical Turks(AMT)

[3]

,CrowdFlower

[4]

,oDesk

[5]

等.该类众包平台不但带

来了新的技术革命,更创造了巨大的市场经济价值.根据美国亚马逊公司的年度报告,截至 2010 年,该公司在

AMT 众包平台上的年度盈利已经超过 5.2 亿美元.因此,众包技术为当今互联网时代的技术革命带来了巨大潜

能,正如《人民日报》2014 年关于众包的报道所述:“众包模式,大势所趋”

[6]

.与此同时,随着大数据时代的到来,

虽然各类数据驱动型应用不断涌现,但由于受到传统数据管理技术自身瓶颈的制约,许多传统数据管理难题(例

如实体同一识别问题)在大数据时代将更难解决.然而,众包技术通过汇聚群智可将人类经验融入到求解问题之

中,为突破传统数据管理挑战开辟了全新的视角.因此,基于众包的数据管理技术(简称为“众包数据管理技术”)

已经引起学术界和产业界的广泛重视

[7−10]

作为一项新兴的研究热点,当前的众包数据管理技术主要关注如何将众包策略融入到传统数据库管理系

统之中,从而提高数据管理的质量.例如,筛选查询(filtering query)

[11,12]

、连接查询(join query)

[13]

、最大值查询

(top-1 query)

[14,15]

、Top-k 查询(top-k query)

[16]

与聚集查询(aggregation query)

[17]

等经典查询处理技术都已经被扩

展到新型的众包数据管理系统之中.而且,一些众包数据管理原型系统近年来也先后问世.例如,美国加州伯克

利大学研发的 CrowdDB 系统

[18]

、麻省理工学院研制的 Qurk 系统

[13]

和斯坦福大学开发的 Deco 系统

[19]

.由于现

有研究侧重于将众包技术集成到数据库管理系统内从而形成众包数据管理系统,因此可以说现有研究大多是

众包数据管理的内涵研究.

另一方面,随着移动互联网技术与共享经济模式的快速发展,移动计算技术为众包数据管理带来了更多的

外延需求,其不仅延伸了众包数据管理系统所需管理数据的类型,更延伸了众包数据管理系统可获取数据的方

式.所谓延伸所需管理数据的类型是指:由于移动设备自身携带着大量时空数据,且此类时空数据又与众包任务

和众包参与者(也称为“众包工人”)的行为密切相关,众包数据管理系统不得不考虑如何有效地处理此类新型数

据问题.例如,近年来全球流行的各类实时专车类服务平台,如滴滴出行

[20]

、神州专车

[21]

与 Uber

[22]

等,均采用时

空众包方式提供服务,其中,专车用户为众包任务请求者,专车司机即众包参与者.所谓延伸可获取数据的方式

是指:移动设备日益强大的功能产生了一类以获取数据为目标的新型众包任务.例如,美国的 Gigwalk 公司

[23]

组

织众包参与者通过智能手机收集不同超市的物品价格,而国内高德地图公司推出的“道路寻宝”服务也旨在组

织众包参与者收集国内各大城市的道路周边信息

[24]

综上所述,移动互联网与物联网等技术的飞速发展,使得众包数据管理技术从基于在线众包平台的模式转

变为一种新型的服务模式,称为“时空众包(spatiotemporal crowdsourcing)”(也称为空间众包或移动众包)

[25]

.简

言之,时空众包数据管理技术是指以时空数据管理平台为基础,将具有时空特性的众包任务分配给非特定的众

包参与者群体为核心操作,要求众包参与者以主动或被动的方式来完成众包任务并满足任务所指定时空约束

条件的一种新型众包计算模式.特别地,当前“互联网+”时代的共享经济模式为时空众包数据管理技术提供了大

of 24

免费下载

软件学报计算机技术

关注

评论