袁野(1981-),男,博士,教授,博士生导师,CCF专业会员,主要研究领域为图数据管理,众包数据管理,不确定数据管理,云计算
成雨蓉(1989-),女,学士,CCF学生会员,主要研究领域为不确定图数据管理与挖掘,众包数据管理,社交网络分析,时空数据管理与挖掘
陈雷(1972-),男,博士,教授,博士生导师,主要研究领域为众包数据管理,不确定数据管理与挖掘,Web数据管理,时空数据管理与挖掘
王国仁(1966-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为数据密集型计算,众包数据管理,非结构数据管理,云计算,生物信息学
近年来,众包为传统数据管理提供了一种通过汇聚群体智慧求解问题的新模式,并成为当前数据库领域的研究热点之一.特别是随着移动互联网技术与共享经济模式的快速发展,众包技术已融入到各类具有时空数据的应用场景中,例如各类O2O(online-to-offline)应用、实时交通监控与动态物流管理等.简言之,这种应用众包技术处理时空数据的方式称为时空众包数据管理.对近期在时空众包数据管理方面的研究工作进行综述,首先阐述了时空众包的概念,解释了其与传统众包技术的关系,并介绍了各类典型的时空众包应用;随后描述了时空众包应用平台的工作流程及其任务特点;然后讨论了时空众包数据管理的3项核心研究问题和3类应用技术;最后,总结了时空众包数据管理技术的研究现状并展望了其未来潜在的研究方向,为相关研究人员提供了有价值的参考.
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, 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.
随着Web 2.0技术的兴起,大量在线Web应用正在悄然地改变着人类的生活模式,同时也为传统的人本计算(human computation)提供了一种通过群体智慧求解问题的新模式——众包(crowdsourcing)[
作为一项新兴的研究热点,当前的众包数据管理技术主要关注如何将众包策略融入到传统数据库管理系统之中,从而提高数据管理的质量.例如,筛选查询(filtering query)[
另一方面,随着移动互联网技术与共享经济模式的快速发展,移动计算技术为众包数据管理带来了更多的外延需求,其不仅延伸了众包数据管理系统所需管理数据的类型,更延伸了众包数据管理系统可获取数据的方式.所谓延伸所需管理数据的类型是指:由于移动设备自身携带着大量时空数据,且此类时空数据又与众包任务和众包参与者(也称为“众包工人”)的行为密切相关,众包数据管理系统不得不考虑如何有效地处理此类新型数据问题.例如,近年来全球流行的各类实时专车类服务平台,如滴滴出行[
综上所述,移动互联网与物联网等技术的飞速发展,使得众包数据管理技术从基于在线众包平台的模式转变为一种新型的服务模式,称为“时空众包(spatiotemporal crowdsourcing)”(也称为空间众包或移动众包)[
由于应用驱动研究,时空众包数据管理技术成为国际数据库与数据挖掘领域新近发展起来的一个研究热点[
本文第1节简介时空众包的相关概念与典型应用.第2节详细论述时空众包平台的工作流程和任务特征.第3节介绍时空众包研究中的3项核心研究问题:任务分配、质量控制与隐私保护.第4节从时空众包数据管理技术的角度详细综述其在数据集成、数据查询与数据挖掘这3类应用中的研究现状,并对各类技术进行完整的对比分析.第5节展望时空众包数据管理未来潜在的研究方向.第6节是结束语.
本节介绍时空众包的概念,阐明其与传统众包技术之间的关系,并介绍时空众包技术的代表性应用领域.
对于任意的时空众包任务(下文简称“众包任务”),上述五元组中的前三者应必须被包括以标记此任务的时空属性;是否包含后两者视具体应用而定.例如,某些任务希望众包平台的每位众包参与者都获知,则可去除此空间范围约束.另外,如果某些任务不为参与者带来任何奖励,也可删除该项内容.
此外,时空众包参与者定义如下.
与时空众包任务的定义相似,对于任意时空众包参与者(下文简称“众包参与者”或“参与者”)的六元组,也是前三者应被包括,而后三者可视具体应用而定.注意:上述时空众包任务与时空众包参与者的定义皆为基础性定义,根据不同的应用需求,可在上述两个定义的基础上进行扩展.因此,基于上述定义,可将时空众包定义如下.
综上所述,时空众包旨在通过整合移动互联网中线上空闲的大众群体,组织其在线下物理世界完成机器难以解决的问题,从而有效地利用线上与线下的闲置资源.因此,时空众包计算正是各类O2O应用的通用计算范式.
自Howe[
一方面,时空众包属于传统众包思想的延伸.从时空众包的名称即可知,其属于众包研究中的一类子问题,更是传统众包在时空维度的新衍生形态.另一方面,时空众包并不是传统众包技术与时空数据的简单组合,其与传统众包有着本质的不同.下文从时空众包的3类基本研究对象(即众包任务、众包参与者与众包平台)的视角分别阐述时空众包与传统众包的差异.
· 众包任务的差异.
传统众包任务通常只需参与者在线上完成,所以其一般仅受到在线参与者数量与参与者历史正确率等线上因素的影响.例如,在传统众包平台AMT上发布一项图片标注的任务,其完成情况通常依赖于任务发布时的在线参与者数量与参与者的认真态度[
· 众包参与者的差异.
传统众包参与者一般只在线完成众包任务,对其工作地点并无特定要求.而时空众包参与者的工作方式通常需要其在线下移动到指定位置完成任务.以在国内流行的时空众包平台滴滴出行为例,作为众包参与者的专车司机每当被分配任务后,则需要从当前位置驱车至任务指定地点,接到乘客,并将其送达至任务目的地.此外,传统众包与时空众包中众包参与者工作方式的差异也导致了二者的众包参与者男女比例恰好相悖.传统众包中,女性参与者通常多于男性参与者.根据文献[
· 众包平台的差异.
下文将从众包平台外在的业务类型特征与内在的数据管理技术两个方面进一步比较时空众包平台与传统众包平台的异同.
(1) 服务范围与业务特征.
传统众包平台通常是面向全球众包参与者的,因此该类平台24小时内总有在线的众包参与者,并未明显受到具体业务类型与参与者所在地理区域的影响;反之,时空众包平台一般只服务于某一个固定区域范围(例如一个国家或一个城市),而且根据时空众包平台的业务类型,其访问量通常存在明显的周期性规律.例如,出行类的时空众包平台,滴滴出行与Uber,每日产生的众包任务数量与在线众包参与者数量呈周期性变化.因此,时空众包平台在服务范围与业务类型特征等方面与传统众包平台存在着本质上的不同.
(2) 数据管理技术.
传统众包平台内部的数据管理技术多为传统关系型数据库的查询处理技术,基础操作也多为连接(join)与排序(ranking)等.例如,传统众包平台经常会根据众包参与者的历史数据筛选出最可信的
综上所述,通过对众包任务、众包参与者与众包平台这3类众包研究基础对象的比较可知,传统众包与时空众包存在着本质的差异.
传统众包与时空众包的对比
Comparison between traditional crowdsourcing and spatotemporal crowdsourcing
众包类型 | 众包任务 | 众包参与者 | 众包平台 | ||||
任务类型 | 任务约束 | 工作方式 | 性别比例 | 服务范围 | 业务特征 | 基础操作 | |
传统众包 | 线上任务 | 线上约束 | 线上完成 | 女多男少 | 国际范围 | 不依赖业务特征 | 结构化查询 |
时空众包 | 线下任务 | 时空约束 | 线下移动 | 男多女少 | 固定范围 | 业务特征驱动 | 时空查询 |
本节将介绍4类时空众包数据管理技术的典型应用,从应用实例的视角剖析时空众包技术如何应用于人们的日常生活之中.
· 实时O2O应用
共享经济时代典型的互联网+商业模式之一正是O2O商业模式,旨在借助移动互联网技术通过线上招募的方式来整合调度线下的空闲资源,以达到线下空闲资源的高效共享.当前流行的O2O应用有实时专车类的滴滴出行[
· 交通管理应用
交通实时路况监控时刻影响着人们的日常出行与生活方式.近年来,随着便携式移动计算设备的普及,基于位置服务的提供商所开发的移动导航类软件,例如国内的百度地图与高德地图,或国外的Waze[
· 灾情监控应用
近年来,由于国内外重大自然灾害频发,如海地地震、日本福岛海啸、我国四川雅安地震等,各国政府均高度重视灾后监控,以减轻后续余震等对灾区的影响.因为基础设施破坏严重,灾后的官方监控消息发布与更新通常迟缓与滞后,一些大型社交媒体所开设的灾情信息分享平台反而成为了第一手信息获取的源头.例如,Twitter在2010年1月的海地大地震后构建了灾情分享平台,众多灾区人民采用智能手机等移动设备发布自己所在地的第一时间灾情.其实,该分享平台背后隐含着时空众包数据管理技术.换言之,Twitter分享平台所发布的灾情调查可被视为其发布的一项时空众包任务,任务内容即上报用户所在地灾情,而每位分享灾情的用户充当了众包参与者的角色.若欲对此类应用的监控质量与救援情况作进一步优化,则可根据灾情分享信息的时空特征更有针对性地分配救助小组,这种任务分配技术恰恰就是时空众包数据管理技术的研究重点所在.
· 社交媒体应用
随着Web 2.0技术的迅猛发展,各类在线社交媒体(online social medias)如雨后春笋般地不断涌现.特别是随着移动互联网技术的普及,众多社交媒体开始推出一种“基于事件的社交服务[
综上所述,以上4类应用的关键挑战都可以被形式化建模为时空众包数据管理中的核心研究问题,因此,时空众包数据管理技术不仅具有重要的理论研究意义,更具有广泛的实际应用价值.
本节首先描述时空众包平台的通用工作流程,随后介绍典型时空众包任务的3个基本特性.
时空众包的主要参与者包括众包任务的请求者与众包参与者,他们通过时空众包平台建立联系.如
时空众包平台的工作流程
Workflow of spatotemporal crowdsourcing platforms
下面分别从请求者和参与者视角阐述工作流程.
· 任务请求者工作流程.当请求者打算使用时空众包平台完成任务时,需要依次执行以下步骤:首先,请求者需要设置任务的时空约束,例如派送类任务通常需要设置派送时间和地点等;设置完成后,请求者即可将任务提交到平台;随后,请求者等待平台反馈;
· 众包参与者工作流程.参与者为了完成任务,首先需要提交自己的时空信息.例如,当前所在位置等,以供平台判定其是否满足相关时空约束.在一些平台上,参与者可浏览并自主选择任务,如
以上即为时空众包平台的通用工作流程.
本节将从任务的实时性、参与者需求量以及任务选择权这3方面介绍不同时空众包应用中任务的独有特性.
根据任务的实时性,可将任务分为静态离线任务和动态在线任务.它们的主要区别在于:动态在线任务中对任务和参与者出现的情况是未知的,参与者与任务随机(或按照某种未知分布)到来,平台只能根据当前参与者和任务的时空分布情况进行分配决策,而无法预知未来参与者和任务的时空分布;对静态离线任务而言,所有的任务和参与者的信息都是已知的,这些信息中没有不确定性,因此往往可以很容易地得到全局最优目标.
以前述物流派送类应用为例,该应用为典型的静态离线任务.通常在一次送货前,派送员(可视为众包参与者)就已经清楚所有的送货地点,因此,平台可为派送员安排出最佳的送货路线.但在实际应用中,通常面对的是动态在线任务,即,任务是实时动态变化的.例如,滴滴出行平台中,出租车司机对于未来可能出现的请求打车服务的用户是无法预测的,因此,平台也只能根据当前时刻已知司机与乘客的信息匹配合理的订单,而当前的匹配策略会对未来订单的匹配结果产生影响,即便当前时刻的匹配策略是最优的,当考虑到下一时刻的订单分布情况时,当前的匹配很可能并不是非常合理的.因此,在各类不同的时空众包应用中,众包任务的实时性特点将在很大程度上影响着众包平台的工作策略.
根据任务对参与者的需求量,可将任务分为单一参与者需求任务和多参与者需求任务,其区别在于完成任务需要的参与者数量不同.一些任务对众包参与者能力要求较单一,这类任务往往限定仅需一个参与者完成.例如,滴滴出行等专车服务以及最近出现的代驾服务等都是典型的单一参与者需求类任务.另一方面,有一些任务或者由于要求能力种类较多,或者由于任务工作量较大或对工作技能要求较复杂,则需要多个参与者协同完成任务.例如,需要多种能力的参与者共同举办聚会就属于多参与者需求类任务.对于此类多人参与的工作,如何控制协同完成工作的质量并不简单.因此,在各类不同的时空众包应用中,众包任务对参与者需求量的不同将影响到对众包任务完成质量的控制方式.
根据众包参与者是否拥有任务选择权,时空众包任务可分为参与者主动选择任务和平台主动分派任务两种形式.对于参与者主动选择类任务,众包参与者拥有对任务的选择权,其可基于自己的偏好选择适宜的任务.但在很多应用场景中,众包参与者们偏好趋同,这将导致少量性价比高的任务供不应求,反而很多性价比不高的任务无人问津,从而致使时空众包平台的整体效用较低.因此,这也导致了另一类平台主动分配型任务的出现.此类任务仅由时空众包平台根据任务分配算法进行分派,被分配到任务的众包参与者应执行任务,否则会受到平台的相应惩罚.仍以实时专车类应用为例,滴滴出行平台采用了参与者主动选择型任务,其每项专车任务(众包任务)都可由专车司机(众包参与者)选择,当一项任务有多位司机选择时,该平台采用“抢单”策略来保证任务分派的唯一性,但其任务本质为参与者主动选择型任务.与之相反,神州专车与Uber平台却采用了平台主动分派型任务,即,每位司机只能被动等待平台分派任务,当任务被分派后,司机需执行此任务,否则将接受惩罚.因此,在各类不同的时空众包应用中,众包参与者对任务的选择权将影响该平台对众包任务的分配机制.
近年来,关注时空众包数据管理的各类研究大都聚焦于如下3个核心问题:任务分配、质量控制与隐私保护.因此,一个很自然的问题就是为什么是这3个核心问题?其主要原因来自如下两个方面.
· 一方面,任务分配与质量控制本就是传统众包数据管理中的两个核心问题,其在时空众包环境下更具有研究意义.正如第1.2节所述,时空众包与传统众包有着本质的区别,这也导致任务分配与质量控制这两个问题在时空众包环境下的优化目标与约束条件都发生了较大改变.就任务分配问题而言,传统众包研究中的任务分配问题通常只采用离线静态二分图匹配模型加以刻画,但该方法难以适应时空众包环境下任务实时性的约束和参与者完成多项任务时路径规划的需求.就质量控制问题而言,传统众包研究中质量控制问题通常以最大化单一参与者或参与者群体完成任务的预期正确率作为优化目标,而在一些实时性时空众包应用中质量控制的优化目标变为最小化参与者完成任务所需的时空成本,因此,时空众包环境下的质量控制方式也与传统众包中的质量控制策略存在较大差异;
· 另一方面,时空众包中隐私保护问题是由其真实应用所产生的全新挑战.由于时空众包平台需根据众包任务位置(或众包任务请求者位置)和众包参与者位置信息进行任务分配,因此,任何时空众包平台都存在泄露任务请求者与参与者隐私的潜在风险.仍以实时专车类时空众包平台为例,一旦平台遭受攻击而泄露隐私信息,则每位专车订单请求者与专车司机在过去每日的精准出行信息将被公布于众.但传统众包平台因为无需收集任务请求者与参与者的时空信息而无此类风险.因此,时空众包的隐私保护问题是其独有的核心研究问题,该问题旨在如何设计隐私保护策略,使其既保护任务请求者与众包参与者的时空信息,又可根据保护后的时空信息指导平台进行有效的任务分配.
综上所述,时空众包环境下的任务分配、质量控制与隐私保护这3个研究问题彼此间并不独立且相互影响,它们之间的关系如
时空众包的核心研究问题
Core research problems of spatial-temporal crowdsourcing
任务分配问题是指时空众包平台根据众包任务与众包参与者的时空属性和任务特点,为每个任务分配最适合执行的众包参与者.由于不同的时空众包应用对任务分配的需求不同,因此,现存研究通常采用两种不同的算法模型对不同应用场景进行建模:一种建模采用二分图匹配模型,旨在一段时间内为每位众包参与者分配一项众包任务,其典型应用场景为实时专车类服务,如滴滴出行等;另一种建模采取任务规划模型,旨在一段时间内为每位众包参与者分配多项众包任务并规划出执行这些任务的详细顺序与路径,其典型应用场景为物流派送类服务,如百度外卖等.下文将对这两类模型分别展开阐述.
该类模型通常将实际问题规约为经典的最大化或最小化加权的二分图匹配问题[
· 静态离线匹配模型.此场景下的任务分配问题通常等价于空间匹配(spatial matching)[
· 动态在线匹配模型.在此应用场景下,每位众包参与者或每项众包任务在分配前均无法获知未来任务与参与者的信息,换言之,仅根据部分二分图信息来进行匹配决策[
该类模型适用于对众包参与者在给定时间内要求执行多项众包任务,则众包平台需要为该参与者规划出一份优化的任务执行计划.相似于基于匹配的任务分配模型,现有的基于规划的任务分配模型也可根据任务实时性要求的不同分为静态离线场景的规划模型与动态在线场景的规划模型.
· 静态离线规划模型.此场景下的任务规划问题通常被规约为经典的旅行商问题[
· 动态在线规划模型.有别于静态离线规划模型,在动态在线应用场景下,每当有新任务在众包平台发布时,每位众包参与者需要实时地决定是否将此项新任务加入到其当前的任务规划之中[
除了上述任务分配问题,质量控制问题也是当前时空众包数据管理研究的一个核心问题[
· 一方面,与传统众包数据管理中的质量控制相似,一些时空众包任务也由多位众包参与者重复完成,所以质量控制的关键在于,如何对不同众包参与者反馈进行有效的汇聚从而形成高质量的任务结果.但与传统研究不同的是:时空众包参与者通常还受到空间服务范围的限制,因此在时空众包环境下,基于结果汇聚的质量控制研究通常着重考虑空间服务范围对所汇聚结果的影响;
· 另一方面,许多时空众包任务虽然具有实时性的要求,但是由于众包参与者和众包任务之间存在一定的空间距离,参与者移动到任务所在位置所需时间会直接影响任务的完成质量或任务请求者的满意度.因此,这种由于移动时间引起的延迟也是时空众包质量控制所需研究的新的挑战性问题.
下面分别介绍上述两种时空众包质量控制方法.
如上所述,该类研究旨在对不同众包参与者反馈进行有效的汇聚,从而形成高质量的任务结果.所以,任务结果通常会受到如下两类因素的影响:众包参与者的可靠性与众包结果的汇聚机制.由于传统众包数据管理关于质量控制的研究已广泛涉及如何估计众包参与者的可靠性与反馈误差[
具体而言,此类研究通常针对每个众包任务给定一组众包参与者,每位参与者根据其历史表现评估得出其正确完成该任务的可靠性,研究的核心问题旨在为每个众包任务寻找到
此外,不同于传统众包数据管理研究通常采用众包参与者集合的可靠性作为质量控制的核心指标,实时性时空众包数据管理通常将完成任务所需的时间开销视为其质量控制的关键指标.例如,对于实时专车服务平台,如滴滴出行,当司机(即众包参与者)接单后,如果需要花费较长时间才能将车驾驶到乘客(即众包任务请求者)所在位置,则该乘客的用户体验通常较差.另外,如果所有的司机所接任务都需要将车开出较远的距离才能接到乘客,那么大量的时间都会被浪费在司机空驶过程中,从而减少司机完成任务的总数量.
文献[
综上所述,质量控制与任务分配问题相互影响.质量控制一方面是任务分配问题的重要优化目标,为任务分配提供指导;另一方面,质量控制结果的好坏也依赖于任务分配策略制定得是否合理.因此,两者互相影响且相互依存.
除了上述任务分配与质量控制两个问题外,隐私保护问题更是时空众包所带来的全新挑战.该问题的目标在于如何既保护众包参与者的时空信息,又可根据众包参与者保护后的时空信息指导其有效地完成任务.
目前,在传统众包数据管理的研究中,隐私保护并未被特别研究.这是因为,在传统众包数据管理中,无论在众包任务的请求者发布任务的过程还是在众包参与者完成任务的环节,人们均无需提供其在真实物理世界中的个人信息,如空间位置信息等.换言之,传统众包数据管理问题并未对现存的隐私保护技术提出新的挑战,因此,隐私保护并非传统众包数据管理研究所关注的问题.然而,时空众包数据管理的研究则不然,由于时空众包平台要求众包任务请求者与参与者提供其在真实物理世界中的时空信息,一旦时空众包平台遭受攻击,时空众包任务请求者与参与者的个人隐私信息将面临泄漏.因此,在时空众包数据管理的研究中,针对新型应用挑战设计合理的隐私保护策略是非常必要的.
当前,面向时空众包数据的隐私保护框架通常如下:首先,众包任务请求者与众包参与者将其敏感的时空信息发送给一个可信的服务器,并在该可信服务器上对其时空信息进行模糊化;随后,该可信服务器将模糊后的信息发送给时空众包平台;最后,该时空众包平台再根据模糊后的信息为任务请求者与参与者提供服务[
虽然目前已存在一些针对时空数据的隐私保护研究[
综上所述,以隐私保护为目的的任务请求者与参与者空间信息模糊化操作会降低任务分配的质量,因此,如何在隐私保护时保障时空众包平台的任务分配质量,是该类问题的研究重点.
本节首先从数据集成、数据查询与数据挖掘这3个方面分别介绍各类时空众包数据应用技术,随后对所介绍的应用技术进行深入而完整的对比分析.具体内容如下.
数据集成研究近十几年来一直是数据库与数据挖掘研究领域的核心主题之一,指的是将众多的异构数据源进行有效地清洗、去冗、归并、匹配,且最终将融合后的数据形成统一视图的过程[
地图数据是众多基于位置服务(location-based service)的基础.传统的地图数据集成主要通过测绘等手段完成,一方面成本较高,另一方面难以应对真实世界中道路、建筑等变化导致的地图数据更新.Google公司每年维护地图数据的花费高达10亿美金.时空众包数据管理技术为地图数据集成提供了一种新思路,通常称为众包地图(crowdsourced map).开放街道地图(open street map,简称OSM)[
在地图数据集成过程中,道路类型信息在导航和路径规划方面应用广泛,是不可或缺的重要信息.因此,在众包地图应用中,众包参与者不仅需要标注道路的拓扑结构,还需要对道路类型进行标注.Ding等人[
信息点(point of interest,简称POI)是指人们认为重要或感兴趣的地理坐标,如学校、大型超市、车站等.POI数据在城市管理、知识发现和基于位置服务等领域都具有广泛的应用价值.例如,Yuan等人[
为了提高POI数据标注的质量,Hu等人[
除了上述的地图数据集成与POI数据标注外,时空众包数据管理技术在数据集成方面的另一个典型应用为交通状况监测,即,对道路交通情况进行实时监测和预估.传统的交通状况监测一般通过在道路上部署传感器来获取车流量与车速等信息,从而监控交通状况.但是由于道路基数大以及道路交通状况复杂等原因,当前所部署的传感器通常无法覆盖全部道路网络,甚至十分稀疏,从而导致当前大多数交通状况监测系统所收集的数据不完备,可用性较差.此外,交通数据具有较强的时效性,也是交通状况监测的另一大挑战.基于上述原因,近年来,时空众包数据管理技术逐渐成为提高交通状况监测质量的一种新策略.
例如,Artikis等人[
除了对城市整体交通状况进行监测,实时车速监测更是交通状况监测的核心内容.然而,现有交通状况监测系统仅能在少数道路上获取粗粒度的车速数据,而无法获得全部道路上细粒度的实时车速信息.为了解决这一问题,Hu等人[
时空众包数据处理以空间匹配查询为核心,首先关注时空众包任务的匹配查询,即:给定一个任务集合与一个众包参与者集合,在满足任务匹配要求的约束条件下优化任务匹配的目标函数.由于不同时空任务匹配查询的优化目标函数与约束条件不同,不同任务匹配问题的建模方式也有所不同.现有的相关研究工作针对不同场景采用了如下4种建模方式:最大二分图权值和的匹配模型、最小化二分图权值和的匹配模型、集合覆盖的匹配模型以及基于隐私保护的匹配模型.此外,时空众包数据自身的动态性特征也将产生不同类型的时空众包任务匹配场景,因此在二分图模型中,又可细分为静态离线场景和动态在线场景.
根据不同应用对任务的实时性要求的不同,最大化二分图权值和匹配模型的适用场景又可进一步分为静态离线场景与动态在线场景.
(a) 静态离线场景
Kazemi等人[
二分图匹配模型
Bipartite matching model
除静态离线场景外,文献[
基于文献[
· 基于质量约束的任务分配.
文献[
· 基于任务冲突约束的任务分配.
考虑到不同众包任务之间可能存在冲突,She等人[
· 基于任务时空散度的任务分配.
在上述基于质量约束的任务分配查询的基础上,Cheng等人[
(b) 动态在线场景
由于许多时空众包的现实应用对众包任务的实时性有较高要求,故众包平台仅可根据当前出现的众包任务与众包参与者执行任务分配,且在分配前无法获知后续众包任务与众包参与者的信息.因此,近年来各类针对动态在线场景空间匹配问题成为研究热点.本节将介绍3类动态在线场景中的最大化二分图权值和匹配查询.
· 在线双边动态任务分配.
上述基于静态离线场景任务分配策略需要获知全部任务和参与者信息后方可执行[
如
第1种在线抵达顺序的贪心算法匹配过程
Procedure of the greedy algorithm under the first online arrival order
两种不同的在线抵达顺序
Two different online arrival orders
抵达时间 | 8:00 | 8:01 | 8:02 | 8:07 | 8:08 | 8:09 | 8:09 | 8:15 | 8:18 |
第1种顺序 | |||||||||
第2种顺序 |
· 基于任务冲突约束的在线任务分配.
针对上述文献[
· 基于摇臂赌博机的在线动态任务分配.
摇臂赌博机(multi-armed bandit)模型是在线学习(online learning)研究领域中的一个重要模型,该模型假设存在一个多臂赌博机,每摇其中一个臂,就可根据该臂相关的某概率分布获得收益.基于该模型的典型优化问题是最大化有限次摇臂后的总收益.Hassan等人[
与第4.2.1.1节相似,本节也从静态离线场景和动态在线场景分别介绍最小化二分图权值和匹配模型.
· 静态离线场景
Alfarrarjeh等人[
· 动态在线场景
相较于动态在线最大化二分图权值和匹配模型[
现存该模型的研究一直认为:贪心算法求解此问题会产生极差的效果,其竞争比为
本节目前所介绍的空间匹配查询均假设针对简单类型的时空众包任务,即,任务仅需要单一众包参与者即可完成.但在实际时空众包应用中存在一些复杂类型的众包任务,需要多位众包参与者组成团队协同完成.具体而言,可在第1.1节众包任务与众包参与者的基础定义中分别增添任务技能约束和参与者技能属性,从而令每个众包参与者团队需满足众包任务的技能约束要求方可执行该任务.对于此类由多位众包参与者组队协同完成任务的空间匹配查询,通常采用集合覆盖模型对问题加以刻画,现存的相关研究可分为如下两类.
· 满足集合覆盖约束.
当任务较为复杂、需要多位众包参与者组成团队协同完成时,就自然地涉及到队伍组建(team formation)问题.队伍组建问题来源于集合覆盖问题,最早由Lappas等人[
不同于上述传统队伍组建问题,在时空众包环境下,众包任务与参与者的时空属性也会对队伍组建产生影响.对该类涉及时空信息的队伍组建问题,Cheng等人[
· 最大化覆盖率.
上述队伍组建问题要求在覆盖任务所需全部技能的条件下最小化目标函数,称为完全覆盖问题.该问题的另一变种为在参与者数量不超过某上限的约束下组建队伍,从而最大化覆盖技能的数量,称为最大化覆盖率问题.文献[
在传统众包中,众包参与者通过Web平台接受和完成任务,并不需要考虑隐私保护问题.而在时空众包中,众包参与者需将空间位置信息提交至平台,因此存在隐私泄露的风险.位置隐私保护问题在基于位置服务领域已有所研究,一系列方案[
· 基于差分隐私保护模型
时空众包平台要求众包参与者提交其实时位置信息,而众包平台并非一个可完全信任的实体,因此,To等人[
· 基于隐蔽位置保护模型
除了差分隐私保护模型外,同样,为了保护众包参与者的位置信息,Pournajaf等人[
传统的最佳路径查询通常是指在路网中的最短路径查询(shortest path query),即:在路网中给定起始点和终止点,查找这两点之间距离最短或者时间最短的路径.该问题已经得到广泛研究.根据优化目标的不同,现有研究主要可分为两类:第1类为距离最短路径查询,此类研究通常先构建高效的索引,再基于索引设计查询算法[
最佳路径查询与最短路径查询相比,除需考虑路径距离与通过时间外,还应考虑其他可能影响交通状况的因素,如路面平坦程度、道路是否施工、车辆拥堵情况、交通信号灯数量、天气情况等.计算机难以处理上述复杂因素,导致很难通过传统建模方法得到高质量的最佳路径查询结果.相比通过计算机算法进行查询,有经验的司机选择的路径可能更为实用.因此,可利用时空众包技术,从司机推荐的路径中选择最佳路径,提高查询质量.例如,Su等人[
时空众包环境下,由于众包任务要求参与者满足一定的时空约束,参与者对移动路径和任务完成顺序的选择都将影响任务完成的效率.为解决上述问题,路径规划查询研究如何为众包参与者规划路径和任务完成顺序,以使其在给定时空约束下获取更多收益.Deng等人[
路径规划示例
Routing planning example
在文献[
文献[
此外,随着移动设备的普及,利用移动设备进行传感测量正受到广泛关注.移动设备的位置实时地发生变化,而传感测量要求传感器接近测量目标,如何高效地利用移动设备进行传感测量,可视为路径规划查询问题.例如,He等人[
一方面,时空众包技术为其他研究领域提供了新思路;另一方面,诸如数据挖掘等其他研究领域的研究成果可用于对时空众包系统进行优化.具体地,通过对时空众包数据进行挖掘,可分析出众包参与者重要的行为模式,用以优化任务分配质量和时空众包系统的用户体验.
对时空众包数据进行挖掘的一个典型实例是实时专车系统中的用户上车地点推荐问题[
综上所述,本节从数据集成、数据查询与数据挖掘这3方面出发,较详细地介绍了时空众包数据管理的19种具体应用技术.为了便于读者区分上述应用技术的异同,本节将从任务实时性、参与者需求量、任务选择权、应用技术的科学问题与优化目标这5个维度进一步对其进行深入而完整的对比分析.具体内容见
时空众包应用技术对比
Comparison on different spatotemporal crowdsourced application techniques
应用技术 | 文献 | 任务实时性 | 参与者需求量 | 任务选择权 | 科学问题 | 优化目标 | |||
数据集成 | 地图数据集成 | [ | 动态在线 | 多位参与者 | 参与者选择 | 质量控制 | 最大化正确率 | ||
POI数据标注 | [ | 动态在线 | 多位参与者 | 参与者选择 | 质量控制 | 最大化正确率 | |||
交通状况监测 | [ | 动态在线 | 多位参与者 | 平台分派 | 质量控制 | 最大化正确率 | |||
数据查询 | 空间匹配查询 | 最大化二分图权值和匹配模型 | 基于匹配规模 | [ | 静态离线 | 单一参与者 | 平台分派 | 任务分配 | 最大化任务数 |
基于质量约束 | [ | 静态离线 | 多位参与者 | 平台分派 | 质量控制 | 最大化匹配数 | |||
基于任务冲突 | [ | 静态离线 | 多位参与者 | 平台分派 | 任务分配 | 最大化效用值 | |||
基于时空散度 | [ | 静态离线 | 多位参与者 | 平台分派 | 任务分配 | 最大化散度值 | |||
基于双边在线 | [ | 动态在线 | 多位参与者 | 平台分派 | 任务分配 | 最大化效用值 | |||
基于动态冲突 | [ | 动态在线 | 多位参与者 | 平台分派 | 任务分配 | 最大化效用值 | |||
基于摇臂赌博机 | [ | 动态在线 | 多位参与者 | 平台分派 | 任务分配 | 最大化接受率 | |||
最小化二分图权值和匹配模型 | [ | 静态离线 | 单一参与者 | 平台分派 | 任务分配 | 最小化等待时间 | |||
[ | 动态在线 | 单一参与者 | 平台分派 | 任务分配 | 最小化距离和 | ||||
基于集合覆盖的匹配模型 | 集合覆盖约束 | [ | 静态离线 | 多位参与者 | 平台分派 | 任务分配 | 最大化效用值 | ||
最大化覆盖率 | [ | 静态离线 | 单一参与者 | 平台分派 | 质量控制 | 最大化覆盖率 | |||
基于隐私保护的匹配模型 | 基于差分隐私 | [ | 静态离线 | 多位参与者 | 平台分派 | 隐私保护 | 最大化效用值 | ||
基于隐蔽位置 | [ | 静态离线 | 多位参与者 | 平台分派 | 隐私保护 | 最大化效用值 | |||
最佳路径查询 | [ | 动态在线 | 多位参与者 | 平台分派 | 质量控制 | 最大化正确率 | |||
路径规划查询 | 单一参与者规划 | [ | 静态离线 | 单一参与者 | 平台分派 | 任务分配 | 最大化任务数 | ||
[ | 动态在线 | 单一参与者 | 平台分派 | 任务分配 | 最大化效用值 | ||||
全体参与者规划 | [ | 静态离线 | 多位参与者 | 平台分派 | 任务分配 | 最大化任务数 | |||
挖掘数据 | 任务最优执行地点推荐 | [ | 动态在线 | 多位参与者 | 平台分派 | 质量控制 | 最小化等待时间 |
目前,时空众包数据管理技术作为一个新型的研究领域,还有很多研究方向值得学者们深入探究.下面简述其中4类潜在的研究方向,供后续研究者们参考.
(1) 时空众包数据的建模问题.
现有工作中,对时空众包的位置信息(众包参与者和请求者的所在地)均采用网格坐标的方式进行建模,且众包参与者在空间的移动方式也只简单地建模为直线移动,这并不符合现实生活中众包参与者真实的应用场景.因此,如何利用路网来建模位置信息及参与者移动方式,是未来建立时空众包数据模型的一个挑战性问题.
(2) 时空众包的存储与索引问题.
由于时空众包数据自身包含动态的时空数据、高维属性数据与时空冲突数据,故传统离线静态场景中的时空数据查询索引技术并不适用于该类问题[
(3) 时空众包的激励机制问题.
相似于传统众包数据管理技术的研究,激励机制也将成为未来时空众包数据管理的重要研究问题之一[
(4) 时空众包在社交网络中的数据管理问题.
某些数据清洗与集成的时空众包应用,如高德推出的“道路寻宝”等,要求用户到指定地点拍摄符合要求的图片并发送到应用平台中.有些众包参与者在完成这些任务的过程中更喜欢与朋友结伴而行.因此,在进行时空众包任务分配时,若综合考虑不同众包参与者之间的社交关系,将会提升众包参与者使用时空众包平台的满意度和用户体验[
本文主要阐述了时空众包数据管理技术的研究进展,不但介绍了时空众包的基本概念、典型应用及其工作流程,还从时空众包数据管理的3个核心研究问题(任务分配、质量控制和隐私保护)和3类应用技术(基于时空众包的数据清洗、数据查询与数据挖掘)这两个视角对该研究领域进行了深入且全面的综述.特别针对3类19种时空众包应用技术进行了5个维度的比较分析,并针对目前的研究状况给出了未来值得探讨的研究方向.具体而言,未来的时空众包数据管理研究在数据模型、存储索引、激励机制与社交关系等方向都值得进一步深入研究.随着移动互联网技术与共享经济模式的快速发展,时空众包数据管理技术作为各类O2O应用的一种新型通用计算范式正受到学术界与产业界的双重关注.希望本文所做的工作可以为致力于从事时空众包数据管理的相关研究人员提供参考.
Law E, Ahn L. Human computation. Synthesis Lectures on Artificial Intelligence and Machine Learning, 2011,5(3):1-121.
Howe J. Crowdsourcing: Why the Power of the Crowd is Driving the Future of Business. Crown Business, 2009.
https://www.mturk.com/mturk/]]>
http://www.crowdflower.com/]]>
http://www.odesk.com/]]>
林琳.众包模式,大势所趋.人民日报,2014-4-4.
Doan A, Franklin MJ, Kossmann D, Kraska T. Crowdsourcing applications and platforms: A data management perspective. Proc. of the VLDB Endowment, 2011,5(11):1495-1506.
doi:10.1145/2213836.2213905]]]>
http://dblp.uni-trier.de/rec/bibtex/conf/cikm/2014]]>
doi:10.1109/ICDE.2015.7113418]]]>
doi:10.1145/2213836. 2213878]]]>
Parameswaran AG, Boyd S, Garcia-Molina H, Gupta A, Polyzotis N, Widom J. Optimal crowd-powered rating and filtering algorithms. Proc. of the VLDB Endowment, 2014,7(9):685-696.[doi: 10.14778/2732939.2732942]
Marcus A, Wu E, Karger D, Madden S, Miller R. Human-Powered sorts and joins. Proc. of the VLDB Endowment, 2011,5(1): 13-24.[doi: 10.14778/2047485.2047487]
doi:10.1145/2213836.2213880]]]>
doi:10.1145/2187836.2187969]]]>
doi:10.1145/2448496.2448524]]]>
Marcus A, Karger D, Madden S, Miller R, Oh S. Counting with the crowd. Proc. of the VLDB Endowment, 2012,6(2):109-120.[doi: 10.14778/2535568.2448944]
doi:10.1145/1989323.1989331]]]>
Park H, Pang R, Parameswaran AG, Garcia-Molina H, Polyzotis N, Widom J. Deco: A system for declarative crowdsourcing. Proc. of the VLDB Endowment, 2012,5(12):1990-1993.[doi: 10.14778/2367502.2367555]
http://www.xiaojukeji.com/index/index]]>
http://www.10101111.com/]]>
https://www.uber.com/]]>
http://www.gigwalk.com/]]>
http://xunbao.amap.com/]]>
doi:10.1145/2470654.2470745]]]>
doi:10.1145/2424321.2424346]]]>
doi:10.1145/2525314.2525346]]]>
doi:10.1145/2525314. 2525370]]]>
doi:10.1109/INFOCOM.2014.6848001]]]>
doi:10.1109/ICDE.2014.6816730]]]>
To H, Ghinita G, Shahabi C. A framework for protecting worker location privacy in spatial crowdsourcing. Proc. of the VLDB Endowment, 2014,7(10):919-930.[doi: 10.14778/2732951.2732966]
Chen Z, Fu R, Zhao ZY, Liu Z, Xia LH, Chen L, Cheng P, Cao CC, Tong YX, Zhang CJ. gMission: A general spatial crowdsourcing platform. Proc. of the VLDB Endowment, 2014,7(13):1629-1632.[doi: 10.14778/2733004.2733047]
http://dblp.uni-trier.de/rec/bibtex/conf/edbt/ArtikisWSBLPBMKMGMGK14]]>
doi:10.1007/978-3-319-05813-9_26]]]>
Zhang CJ, Tong YX, Chen L. Where to: Crowd-Aided path selection. Proc. of the VLDB Endowment, 2014,7(14):2005-2016.[doi: 10.14778/2733085.2733105]
doi:10.1109/UIC-ATC-ScalCom.2014.68]]]>
Cheng P, Lian X, Chen Z, Fu R, Chen L, Han JS, Zhao JZ. Reliable diversity-based spatial crowdsourcing by moving workers. Proc. of the VLDB Endowment, 2015,8(10):1022-1033.[doi: 10.14778/2794367.2794372]
doi:10.1109/ICDE.2015.7113387]]]>
To H, Shahabi C, Kazemi L. A server-assigned spatial crowdsourcing framework. ACM Trans. on Spatial Algorithms and Systems, 2015,1(1):2.[doi: 10.1145/2729713]
doi:10.1145/2820783.2820831]]]>
Deng D, Shahabi C, Demiryurek U, Zhu L. Task selection in spatial crowdsourcing from worker’s perspective. GeoInformatica, 2016,20(3):529-568.[doi: 10.1007/s10707-016-0251-4]
doi:10.1109/MDM.2015.55]]]>
doi:10.1109/ICDE.2016.7498229]]]>
doi:10.1109/ICDE.2016.7498298]]]>
doi:10.1109/ICDE.2016.7498228]]]>
Tong YX, She JY, Ding BL, Chen L, Wo TY, Xu K. Online minimum matching in real-time spatial data: Experiments and analysis. Proc. of the VLDB Endowment, 2016,9(12):1053-1064.[doi: 10.14778/2994509.2994523]
doi:10.1007/978-3-319-39937-9_15]]]>
Cheng P, Lian X, Chen L, Han J, Zhao J. Task assignment on multi-skill oriented spatial crowdsourcing. IEEE Trans. on Knowledge and Data Engineering, 2016,28(8):2201-2215.[doi: 10.1109/TKDE.2016.2550041]
doi:10.1109/PERCOM.2016.7456507]]]>
Li GL, Wang JN, Zheng YD, Franklin JM. Crowdsourced data management: A survey. ACM Trans. on Knowledge and Data Engineering, 2016,28(9):2296-2319.[doi: 10.1109/TKDE.2016.2535242]
Chittilappilly AI, Chen L, Amer-Yahia S. A survey of general-purpose crowdsourcing techniques. ACM Trans. on Knowledge and Data Engineering, 2016,28(9):2246-2266.[doi: 10.1109/TKDE.2016.2555805]
Garcia-Molina H, Joglekar M, Marcus A, Parameswaran AG, Verroios V. Challenges in data crowdsourcing. ACM Trans. on Knowledge and Data Engineering, 2016,28(4):901-911.[doi: 10.1109/TKDE.2016.2518669]
Feng JH, Li GL, Feng JH. A survey on crowdsourcing. Chinese Journal of Computers, 2015,9:1713-1726(in Chinese with English abstract).[doi: 10.11897/SP.J.1016.2015.01713]
冯剑红,李国良,冯建华.众包技术研究综述.计算机学报,2015,9:1713-1726.
Ipeirotis P. Demographics of mechanical turk. Social Science Electronic Publishing, 2012,35:119
http://waimai.baidu.com/]]>
http://www.taskrabbit.com/]]>
https://www.waze.com/]]>
doi:10.1145/ 2339530.2339693]]]>
doi:10.1145/2623330.2623724]]]>
doi:10.1109/ICDE.2015.7113329]]]>
doi:10.1145/2723372.2749446]]]>
She JY, Tong YX, Chen L, Cao CC. Conflict-Aware event-participant arrangement and its variant for online setting. IEEE Trans. on Knowledge and Data Engineering, 2016,28(9):2281-2295.[doi: 10.1109/TKDE.2016.2565468]
http://www.meetup.com/]]>
Plancast. http://plancast.com
https://whova.com/]]>
Burkard RE, Dell’Amico M, Martello S. Assignment Problems. Philadelphia: Society for Industrial and Applied Mathematics, 2009.
Wong RC, Tao YF, Fu AW, Xiao XK. On efficient spatial matching. In: Koch C, Gehrke J, Garofalakis MN, et al., eds. Proc. of the 33rd Int’l Conf. on Very Large Data Bases. ACM Press, 2007. 579-590.
doi:10.1145/1376616.1376621]]]>
http://dblp.uni-trier.de/rec/bibtex/conf/aaai/2012]]>
http://dblp.uni-trier.de/rec/bibtex/conf/icml/2013]]>
Karger D, Oh S, Shah D. Budget-Optimal task allocation for reliable crowdsourcing systems. Operations Research, 2014,62(1): 1-24.[doi: 10.1287/opre.2013.1235]
Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1979.
Vansteenwegen P, Souffriau W, Oudheusden DV. The orienteering problem: A survey. European Journal of Operational Research, 2011,209(1):1-10.[doi: 10.1016/j.ejor.2010.03.045]
doi:10.1007/978-3-319-22363-6_8]]]>
doi:10.1145/1837885.1837906]]]>
Liu X, Lu M, Ooi B, Shen Y, Wu S, Zhang M. CDAS: A crowdsourcing data analytics system. Proc. of the VLDB Endowment, 2012,5(11):1495-1506.[doi: 10.14778/2350229.2350264]
Cao CC, She JY, Tong YX, Chen L. Whom to ask? Jury selection for decision making tasks on micro-blog services. Proc. of the VLDB Endowment, 2012,5(11):1495-1506.[doi: 10.14778/2350229.2350264]
doi:10.1145/2487575.2487642]]]>
doi:10.1145/2463676.2465307]]]>
http://dblp.uni-trier.de/rec/bibtex/conf/nips/2009]]>
Raykar V, Yu S. Eliminating spammers and ranking annotators for crowdsourced labeling tasks. Journal of Machine Learning Research, 2012,13:491-518.
doi:10.1145/1401890. 1401965]]]>
doi:10.1145/2488388.2488414]]]>
doi:10.1145/2465529.2465761]]]>
doi:10.1145/2487575.2487595]]]>
doi:10.1145/1376616. 1376631]]]>
doi:10.1109/MDM.2014.15]]]>
doi:10.1145/2820783.2820788]]]>
Pournajaf L, Garcia-Ulloa DA, Xiong L, Sunderam VS. Participant privacy in mobile crowd sensing task management: A survey of methods and challenges. SIGMOD Record, 2015,44(4):23-34.[doi: 10.1145/2935694.2935700]
Doan A, Halevy A, Ives Z. Principles of Data Integration. San Francisco: Morgan Kaufmann Publishers, 2012.
Wang J, Kraska T, Franklin MJ, Feng J. CrowdER: Crowdsourcing entity resolution. Proc. of the VLDB Endowment, 2012,5(11): 1483-1494.[doi: 10.14778/2350229.2350263]
doi:10.1145/2463676.2465280]]]>
Vesdapunt N, Bellare K, Dalvi N. Crowdsourcing algorithms for entity resolution. Proc. of the VLDB Endowment, 2014,7(12): 1071-1082.[doi: 10.14778/2732977.2732982]
Whang S, Lofgren P, Garcia-Molina H. Question selection for crowd entity resolution. Proc. of the VLDB Endowment, 2013,6(6): 349-360.[doi: 10.14778/2536336.2536337]
doi:10.1145/2588555.2588576]]]>
Zhang C, Chen L, Jagadish H, Cao CC. Reducing uncertainty of schema matching via crowdsourcing. Proc. of the VLDB Endowment, 2013,6(9):757-768.[doi: 10.14778/2536360.2536374]
doi:10.1109/ICDE.2014.6816716]]]>
doi:10.1109/ICDE.2014.6816736]]]>
Haklay M, Weber P. OpenStreetMap: User-Generated street maps. IEEE Pervasive Computing, 2008,7(4):12-18.[doi: 10.1109/ MPRV.2008.80]
https://www.mapbox.com/osm-data-report/]]>
doi:10.1145/2339530.2339561]]]>
doi:10.1145/1557019.1557074]]]>
Wu L, Xiao X, Deng D, Cong G, Zhu A, Zhou S. Shortest path and distance queries on road networks: An experimental evaluation. Proc. of the VLDB Endowment, 2012,5(5):406-417.[doi: 10.14778/2140436.2140438]
doi:10.1145/2463676.2465287]]]>
Zhou AY, Yang S, Jin CQ, Ma Q. Location-Based services: Architecture and progress. Chinese Journal of Computers, 2011,34(7): 1155-1171(in Chinese with English abstract).[doi: 10.3724/SP.J.1016.2011.01155]
周傲英,杨彬,金澈清,马强.基于位置的服务:架构与进展.计算机学报,2011,34(7):1155-1171.
Hu J, Fan J, Li GL, Chen SS. Top-k fuzzy spatial keyword search. Chinese Journal of Computers, 2012,35(11):2237-2246(in Chinese with English abstract).[doi: 10.3724/SP.J.1016.2012.02237]
胡骏,范举,李国良,陈珊珊.空间数据上Top-k关键词模糊查询算法.计算机学报,2012,35(11):2237-2246.
Liu XP, Wang CX, Liu DX, Liao GQ. Survey on spatial keyword search. Ruan Jian Xue Bao/Journal of Software, 2016,27(2): 329-347(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4934.htm[doi: 10.13328/j.cnki.jos.004934]
刘喜平,万常选,刘德喜,廖国琼.空间关键词搜索研究综述.软件学报,2016,27(2):329-347. http://www.jos.org.cn/1000-9825/4934.htm[doi: 10.13328/j.cnki.jos.004934]
Wang JB, Gao H, Li JZ, Yang DH. An index supporting spatial approximate keyword search on disks. Journal of Computer Research and Development, 2012,49(10):2142-2152(in Chinese with English abstract).
王金宝,高宏,李建中,杨东华.RB树:一种支持空间近似关键字查询的外存索引.计算机研究与发展,2012,49(10):2142-2152.
Dai J, Xu JJ, Liu KE, Wu B, Ding ZM. DKR-Tree: A dynamic-keyword-R tree. Journal of Computer Research and Development, 2013,50(S1):163-170(in Chinese with English abstract).
戴健,许佳捷,刘奎恩,武斌,丁治明.DKR-Tree:一种支持动态关键字的空间对象索引树.计算机研究与发展,2013,50(S1): 163-170.
doi:10.1145/2488388.2488489]]]>
doi:10.1145/2488388.2488490]]]>
Gao Y, Parameswaran AG. Finish them!: Pricing algorithms for human computation. Proc. of the VLDB Endowment, 2014,7(14): 1965-1976.[doi: 10.14778/2733085.2733101]
Wu Y, Zeng JR, Peng H, Chen H, Li CP. Survey on incentive mechanisms for crowd sensing. Ruan Jian Xue Bao/Journal of Software, 2016,27(8):2025-2047(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5049.htm[doi: 10.13328/j. cnki.jos.005049]
吴垚,曾菊儒,彭辉,陈红,李翠平.群智感知激励机制研究综述.软件学报,2016,27(8):2025-2047. http://www.jos.org.cn/1000-9825/5049.htm[doi: 10.13328/j.cnki.jos.005049]
Tong YX, She JY, Meng R. Bottleneck-Aware arrangement over event-based social networks: The max-min approach. World Wide Web Journal, 2016,19(6):1151-1177.[doi: 10.1007/s11280-015-0377-6]
doi:10.1145/2623330.2623647]]]>