大规模空间关键字数据流中查询和订阅技术研究

With the rapid development of mobile Internet, a large number of applications and services based on users' location and text information have emerged. In these applications and services, there is a large number of geo-textual data, which typically occurs in the form of data streams. The data is huge and frequently updated. Real time analysis and mining of large-scale geo-textual streams has important social significance and commercial value, which also brings great challenges to existing processing technology. Despite receiving a tremendous amount of attention in the literature, existing research on spatial-keyword queries cannot properly handle big geo-textual streams effectively and efficiently. This project focuses on two basic queries, namely, spatial-keyword search and subscription, and aims to develop effective, efficient and scalable query processing techniques for big geo-textual streams. It will be the first project to conduct systematic investigation on how to enhance results' quality by applying advanced ranking models. In terms of efficiency and scalability, this project designs efficient single-machine algorithms and distributed algorithms for conventional models and advanced ranking models. We plan to design novel index structure, update mechanism, and filtering algorithms to investigate single-machine algorithms. By considering the data partition strategy, load balance, single-node efficiency, communication cost and other factors, we design efficient and scalable distributed solutions. To sum up, through this project, it will lay solid foundations for establishing large-scale geo-textual stream processing system.

随着移动互联网的飞速发展，涌现出大量基于用户位置和文本信息的应用和服务。在这些应用和服务中，包含大量的空间关键字数据。这些数据通常以数据流的形式出现，规模巨大、更新频繁。针对大规模空间关键字数据流的实时分析和挖掘有着重要的社会意义和商业价值，同时也给传统处理技术带来极大挑战。本项目围绕大规模空间关键字数据流的两个基本操作，即查询和订阅，展开研究。旨在从有效性、处理效率、扩展性角度对已有工作进行完善。在有效性方面，本项目首次将高级排序模型引入到查询和订阅操作中，并进行系统性研究，提高返回结果质量。在处理效率和扩展性方面，本项目针对传统模型和高级排序模型，设计有效的单机算法和分布式算法。通过设计新颖的索引结构、更新机制，以及搜索过滤算法实现对单机算法的有效支持。通过综合考虑数据划分、负载均衡、节点效率、通信代价等指标设计高效的分布式解决方案。为建立大规模空间关键字数据流的处理系统打下扎实基础。

随着智能手机的普及和移动互联网的快速发展，在线用户数据也随之飞速增长，涌现出大量基于用户位置信息和复杂数据的服务，移动网络流量也成为众多企业争夺的高地。许多应用，例如微信、微博、大众点评、Facebook、Yelp等，通过获取和分析用户的复杂数据，从而为用户提供更好的服务支持。在这些应用中，数据不仅结构复杂，而且规模巨大、更新频繁。而传统的解决方案通常针对小规模的静态数据，给已有的处理技术提出了严峻的挑战。在项目初期，项目负责人主要针对空间数据和文本数据进行分析和研究，除了传统的top-k查询，还涉及到k-regret查询的设计，以及对应的理论分析。随着项目的展开，项目组成员进一步利用图模型来刻画空间实体之间的关联关系，进行更加复杂和有效的模式挖掘和查询。由于图数据的灵活性、图问题的复杂性，给各类查询问题带来了新的挑战。项目组成员基于前期研究基础，对更复杂的关键实体、关联关系、子结构的查询和挖掘问题进行刻画，并设计高效的索引和算法。受本课题资助，项目组取得了较好的理论和实践成果。在项目执行期间，项目组累计发表高水平论文34篇（29篇以本项目为第一/唯一标注），其中在CCF A类期刊和会议上发表论文13篇，在CCF B类期刊和会议上发表论文11篇，在CCF C类期刊和会议上发表论文8篇,其他EI检索和SCI检索论文各1篇。申请专利8项，目前均处于实质审查阶段，部分研究成果在相关机构进行了初步的测试和部署。