面向大规模图数据的高效结构查询技术研究

With rapid developments of social media, online communities, mobile communications, cyber security, public health, transportation, and collectively produced knowledge resources, huge volumes of digital data are accumulated where data objects are often involved complex relationships. Due to the high expressive power of graph models, these applications usually model their data as graphs to specify intra relationships by edges. This not only brings strong demands for effectively supporting structure search over large-scale graphs to serve key applications but also brings grand challenges in computation...This project focuses on a key area in graph data analytics, efficiently processing structure-based graph queries over large graphs. We aim to develop, analyze, implement, and evaluate novel techniques to efficiently conduct such structure-based graph queries over large-scale graphs. Particularly, we will develop novel indexing, parallel processing, approximation, and incremental techniques to process the primitive structure-based graph queries over large-scale graphs, including sub-containment (super-containment) search, containment all-match, similarity search, probabilistic search, and top-k search etc. A system prototype will be developed to demonstrate the utility/effectiveness by combining the developed techniques in the project.

随着社交媒体、在线社区、移动通信、网络空间安全、公共卫生、交通网络和知识资源等应用领域的快速发展，大量包含对象间复杂关系的数据涌现出来。作为具有较强表达能力的数据结构，图通常应用于上述领域的数据建模中：结点建模对象，边表达对象间的关系。迅猛增长的图数据带动了各类面向图结构的查询需求，同时也对大规模图数据的传统计算模式带来了极大挑战。..本课题围绕大规模图数据中的结构查询这一图数据分析的核心问题，旨在研究、分析、实现和评估适应大规模图数据的新颖、高效结构查询技术。通过系统的理论研究和技术实践，我们力图构建新颖的索引技术、并行算法、近似算法和增量处理技术等一系列解决方案，具体研究子包含查询、子包含的全匹配，父包含查询等查询类型，以及相似查询、概化查询和排序查询等应用中的重要问题。同时，基于课题的研究成果，我们将筑建高效的面向大规模图数据的查询原型系统。

大规模图数据中的结构查询是图数据分析应用中的核心问题，对于提高大图数据计算分析的服务质量起到至关重要的作用。我们针对模式结构查询问题的理论分析与具有最优性的查询算法设计两个关键科学问题进行了系统深入的研究。旨在提出新颖的面向图数据的结构查询计算理论，以及新颖、有效、快速的索引方法和处理算法，进而构造新颖的图数据实验平台和原型展示系统。本项目的主要贡献如下：第一，在基本结构的查询处理方面提出了高效的查询算法、新颖的索引结构及增量更新的高效处理方法；第二，在相似结构查询处理方面提出新的相似结构度量方式及查询处理技术；第三，在概化结构查询方面，提出了概化结构查询的精确算法与索引技术；第四，在排序查询方面，提出了排序结构查询框架及排序结构查询剪枝算法；第五，基于上述研究成果，开发完成了支持大规模图数据结构查询的原型系统。其中部分成果已经应用于阿里巴巴集团电商业务。 .项目取得的研究成果已全部达到项目任务要求，在高水平国际期刊和国际会议发表学术论文共24篇，其中在CCF推荐为A类的顶级学术期刊如VLDBJ,TKDE和顶级会议如SIGMOD,PVLDB,ICDE等发表学术论文共17篇，申请专利2项，开发大规模图数据结构查询原型系统；项目执行期间，项目负责人应国内外知名会议的邀请，做了多场大会特邀报告，扩大了团队在相关领域的国际影响力。