基于分布式流处理的动态图在线查询技术研究

With the rapid development of World Wide Web and Internet of Things, dynamic graph has become an important model for large-scale data management. Efficient online query over dynamic graph is an essential requirement for achieving graph applications, including social network and intelligent traffic. When making query over dynamic graph, however, existing distributed graph processing systems face technical challenges such as, insufficient scalability, significant query latency, and inability of updating the results dynamically. In this project, we focus on dynamic graph and propose an online query method over dynamic graph via distributed stream processing. We study dynamic graph partition processing, online query based on asynchronous mechanism and incremental updating for query results. We aim at addressing key scientific problems in load imbalance of dynamic graph processing, the delay of online query and the inaccuracy of query results. This project facilitates the real-time analysis on dynamic graph, and it effectively provides online query approaches for real-world dynamic graph applications.

随着互联网和物联网的快速发展，动态图已成为大规模数据管理的重要模型。高效的动态图在线查询是实现社交网络、智能交通等图应用的基本要求。然而，现有的分布式图处理系统在处理动态图查询时，仍面临可扩展性不足、实时性不强、以及难以满足查询结果动态变化等技术挑战。本项目以动态图为研究对象，提出基于分布式流处理的动态图在线查询的方法，分别开展面向动态图的分区处理、异步在线查询和在线查询结果的增量更新方法的研究工作，力图解决动态图处理的负载不均衡问题、在线查询的延迟性与查询结果的不准确性等关键科学问题。通过本项目的核心技术研究，将有效提高动态图的实时分析水平，为现实的动态图应用提供行之有效的在线查询方法。

随着互联网和物联网的快速发展，动态图已成为大规模数据管理的重要模型。高效的动态图在线查询是实现社交网络、智能交通等图应用的基本要求。然而，现有的分布式图处理系统在处理动态图查询时，仍面临可扩展性不足、实时性不强、以及难以满足查询结果动态变化等技术挑战。本项目以动态图为研究对象，提出基于分布式流处理的动态图在线查询的方法，分别开展面向动态图的分区处理、异步在线查询和在线查询结果的增量更新方法的研究工作，力图解决动态图处理的负载不均衡问题、在线查询的延迟性与查询结果的不准确性等关键科学问题。通过本项目的核心技术研究，将有效提高动态图的实时分析水平，为现实的动态图应用提供行之有效的在线查询方法。..本项目基于分布式流处理的动态图在线查询技术展开多方面的研究。为解决动态图实时变化造成集群负载不均衡问题，提出了基于聚类与频率分析的实时图分区算法，快速处理实时图数据，为实时分析提供了一个统一的、高扩展性基础架构；针对海量轨迹数据，提升用户查询与降低存储空间，分析并实现25个轨迹压缩算法，给轨迹数据存储和空间数据库的设计提供指导意见；提出在动态路网中识别K条最短路径问题并设计了两层路径的索引机制，解决分布式实时K条最短路径查询与增量更新问题。此外项目组还提出一个基于分布式流处理系统的内存访问与计算的优化算法、在小样本上预测分布式系统的最优配置模型等方面的研究。..项目组在执行过程中对基于分布式流处理的动态图查询技术、算法进行研究并获得了较丰富的成果。目前已经在国内外学术期刊与会议上共发表论文19篇（包含CCF 推荐会议/期刊论文12篇），其中SCI源刊论文10篇，EI国际会议/期刊论文7篇，2篇国内期刊；申请技术发明专利3项；产生3个开源项目。部分成果CCF A类/B类会议和期刊上，如SIGMOD、VLDB、Information Science、TSC、Empir. Softw. Eng、Wirel. Networks、ICA3PP、FGCS等，部分研究成果还处于审稿中。接下来，将围绕动态图查询算法在交通轨迹应用、传感器应用、社交网络应用拓展研究。