空间众包数据处理及其优化关键技术研究

With the prevalence of Web 2.0 techniques, crowdsourcing provides a novel data processing paradigm for traditional challenges of data management by utilizing the intelligence of crowds to solve problems. Thus, crowdsourced data processing becomes one of the hottest research topics. Especially, due to the rapid development of Mobile Internet and Internet of Things, crowdsourcing not only becomes a new approach for data collection, but is also used in all kinds of new application scenarios, e.g. traffic mentoring, logistics management, etc. Most existing techniques of crowdsouced data processing aim to integrate crowdsourced strategy into traditional relational database systems. However, the studies regarding data processing techniques in spatial crowdsourcing are very limited. Therefore, this project focuses on the topic of key techniques of data processing and optimization in spatial crowdsourcing and studies it deeply. Furthermore, task assignment operations are considered as the core of in this project. We intend to make breakthroughs regarding data model of spatial crowdsourcing, storing and indexing, and query optimization processing. We also build the prototype system of data processing in spatial crowdsourcing in order to verify the efficiency and effectiveness of the research results. Our results provide a new solution to data processing in spatial crowdsourcing and extend the application areas of spatial crowdsourcing. Hence, this project has important theoretical significance and application value.

随着Web 2.0技术的兴起，众包为传统数据管理挑战提供了一种通过汇聚群体智慧求解问题的新型数据处理模式，使得众包数据处理技术成为当前数据库领域的研究热点之一。特别是由于移动互联网与物联网等技术的快速发展，不但令众包技术成为一种数据获取的新方式，更为众包数据处理技术提供了各类基于时空数据的新型应用场景，例如交通监控与物流管理等。现有的众包数据处理技术侧重于将众包策略融入传统关系数据库管理系统中，但是针对大规模、实时性的空间众包数据处理技术的研究十分有限。因此，本项目紧紧围绕空间众包数据处理及其优化关键技术展开深入研究，以空间众包任务的分配操作为核心，力争在空间众包数据模型、存储与索引、查询优化处理等方面取得原创性的突破成果，并通过构建空间众包数据处理原型系统来验证研究成果的有效性。相关研究成果将为空间众包数据处理问题提供新的解决方案，进一步拓宽其应用范围，具有重要的理论意义与实际应用价值。

本项目的执行时间为2016年1月~2018年12月，这期间，项目主要研究了空间众包数据处理及其优化关键技术的各个方面，现总结如下：..1. 在空间众包的任务分配方面，项目组提出了基于双边在线二分图的空间众包实时任务分配模型和“过滤-验证”的冲突任务分配通用框架。特别针对单边在线二分图最小化完美匹配这一特例问题，证明了朴素贪心算法在平均分析下具有常数竞争比的良好性能，并证明了现存最差分析中的指数阶竞争比发生概率极低，从而澄清了理论研究对该算法性能的误解。..2. 在空间众包的激励机制方面，项目组首先提出了面向空间众包市场的需求与供给有效预测方法。基于预测的供需关系，申请人进一步提出了两种定价策略。针对供大于求市场，提出最小化支付成本模型；反之，针对供小于求市场，提出最大化期望效用模型。基于两种激励模型，提出了有效的近似算法并证明其近似比，为解决供需驱动的激励机制构建提供了有效方法。..3. 基于空间众包的共享出行应用方面，项目组将空间众包技术应用于共享出行技术已经在滴滴出行与百度地图等大型互联网企业的共享出行、网约车调度、群体出行供需预测等业务场景之中实施部署并落地应用，使其核心业务指标显著提高。..4. 本项目实施过程中，项目组已在IEEE TKDE、ACM TOIS、SIGMOD、SIGKDD、VLDB、ICDE等国际权威期刊会议上发表论文（含已录用）23篇，其中CCF A类期刊和会议15篇、SCI检索5篇。其中获得阿里巴巴集团评选的首届“达摩院青橙奖”（全国仅9位得主），和国际重要会议WAIM 2016的“最佳论文奖等奖励。项目组所开发基于空间众包的共享出行技术已经在滴滴出行与百度地图等大型互联网企业得到落地应用，并申请国家发明专利3项。项目负责人童咏昕博士在项目执行期内获得国家自然科学基金优秀青年基金资助，项目培养毕业博士生2名，硕士生4名。关于空间众包数据管理的一系列建模机制与优化算法为项目组成员在国际上率先提出，并在国际权威会议VLDB 2017做“Tutorial报告”，成为该会议创办43年首位做此类报告的大陆学者，奠定了我国在空间众包技术的国际领先地位。