研究概述

海量图数据管理

传统的数据管理集中于关系型数据的研究,关系型数据的特点是有清晰的模式(Schema);并且数据库系统在确定了模式以后才进行数据的存储和管理。然而在社会网络、知识图谱等很多应用中,数据并没有统一和清晰的模式,所以提前设计好固定的模式是一件非常困难的事情。因此为了解决这个问题,Key-Value等NoSQL数据库系统被广泛地应用到目前大数据管理中。然而简单的Key-Value存储方式忽略了数据和数据之间的关联;我们知道数据是对真实世界事物的描述,真实世界中的事物之间具有千丝万缕的联系,因此数据之间也具有天然的关联性;例如在社会网络中的人物之间关联关系,以及在知识图谱中的实体之间的关联关系。以图的形式来对这些复杂的关联进行建模,并且设计有效的存储和索引机制来支持面向图数据的查询是图数据管理的核心。

在此方向上,我们的研究重点在于设计基于图结构的索引策略和查询优化算法,从而支持图数据上的典型查询和分析,例如子图匹配查询和路径检索等。

代表性工作:

[1] Liang Hong, Lei Zou, Xiang Lian, Philip S. Yu: Subgraph Matching with Set Similarity in a Large Graph Database. IEEE Trans. Knowl. Data Eng. (TKDE) 27(4): 964-978 (2015)

[2] Weiguo Zheng, Lei Zou, Xiang Lian, Dong Wang, Dongyan Zhao: Efficient Graph Similarity Search Over Large Graph Databases. IEEE Trans. Knowl. Data Eng. (TKDE) 27(9): 2507-2521 (2015)

[3] Weiguo Zheng, Lei Zou, Yansong Feng, Lei Chen, Dongyan Zhao: Efficient SimRank-based Similarity Join Over Large Graphs. Proceeding of VLDB (PVLDB) 6(7): 493-504 (2013) 

[4] Lei Zou, Lei Chen, M. Tamer Özsu, Dongyan Zhao: Answering pattern match queries in large graph databases via graph embedding. VLDB Journal (VLDB J). 21(1): 97-120 (2012)

[5] Lei Zou, Lei Chen: Pareto-Based Dominant Graph: An Efficient Indexing Structure to Answer Top-K Queries. IEEE Trans. Knowl. Data Eng. (TKDE) 23(5): 727-741 (2011) 

 

基于图的RDF知识库数据管理

近期知识图谱的研究引起了学术界和工业界的普遍关注。目前RDF(资源描述框架)是知识图谱数据的事实标注,它以<Subject, Predicate,Object>的三元组格式描述知识。现有工业界管理RDF数据的主要策略仍然是利用关系数据库系统来进行RDF数据的存储和查询;然而RDF数据本身的特征对这种关系数据库模式下的查询优化提出了很多新的挑战。不同于传统方法,我们以图数据库的方式,直接存储RDF图数据本身,进而利用图结构信息进行查询优化;具体的,我们从事以下3个方面的工作:

RDF存储和SPARQL查询引擎构建

以图的方式存储RDF数据;将SPARQL查询表示成查询图,以子图匹配的方式回答面向RDF的SPARQL查询。基于此原理,我们设计了基于图结构的多层索引结构,有效地降低查询响应时间。所构建的原型系统gStore在单机环境下40亿三元组规模的Benchmark数据集上,实现了秒级以下的查询响应时间。并且gStore系统可以有效地支持在线的RDF数据更新(即增删改);另外,我们研究了多种分布式环境下的RDF存储查询策略。

面向RDF知识库的自然语言问答和交互式检索系统

知识图谱数据与关系数据库数据的区别在于,知识图谱数据缺乏明晰的模式(Schema),而关系数据库一种基于Schema的数据模型。正是由于RDF数据没有明确的模式,检索RDF数据是一件很困难的事情。因此,在本项目中我们将具体研究如何为用户提供一种简单易用的交互式的检索方式。目前,我们的研究重点是面向RDF数据的自然语言问答系统。系统自动理解用户输入的“自然语言问题”或者“关键词”,将其转换为面向RDF的结构化查询语句SPARQL,并利用我们在研究(1)中开发的系统gStore回答用户查询。进一步,我们将研究基于可视化交互方式和基于用户反馈的交互式知识图谱检索方法。

RDF知识库构建过程中的数据质量问题

RDF知识库构建是知识图谱应用的前提,然而知识库数据质量评估和提示是目前仍然亟待解决的问题。在此方面,我们拟研究基于图结构的函数依赖模型,并利用该依赖模型进行数据质量的研究。

代表性工作:

[1] Lei Zou, Jinghui Mo, Lei Chen, M. Tamer Özsu, Dongyan Zhao: gStore: Answering SPARQL Queries via Subgraph Matching. Proceeding of VLDB 4(8): 482-493 (2011)

[2] Lei Zou, Ruizhe Huang, Haixun Wang, Jeffrey Xu Yu, Wenqiang He, Dongyan Zhao: Natural language question answering over RDF: a graph data driven approach. SIGMOD Conference 2014: 313-324 

[3] Peng Peng, Lei Zou, M. Tamer Özsu, Lei Chen, Dongyan Zhao: Processing SPARQL queries over distributed RDF graphs. VLDB J. 25(2): 243-268 (2016)

[4] Peng Peng, Lei Zou, M. Tamer Özsu, Dongyan Zhao: Multi-query Optimization in Federated RDF Systems. DASFAA (1) 2018: 745-765 (BEST PAPER Award)

[5] Sen Hu, Lei Zou, Xinbo Zhang, A State-transition Framework to Answer Complex Questions over Knowledge Base. EMNLP 2018. 

 

动态图和图流数据的管理与分析

很多图数据应用中,图数据本身是在不断变化的;传统基于结构索引的图数据管理方法,不适合在高速变化的图流数据场景。因此,面向高速变化的图数据查询和分析问题是一个亟待解决的研究内容。在此方向,我们主要考虑如下问题:如何设计一种面向图流和动态图特征的图数据结构以支持在其上多种图流查询和分析任务,针对图流的高速变化特点,如何设计高效的并发计算策略,以及面向图流数据的概要数据结构(Sketch)等。

代表性工作:

[1] Youhuan Li, Lei Zou, Tamer Ozsu, Dongyan Zhao, Time Constrained Continuous Subgraph Search over Streaming Graphs, ICDE 2019

[2] Xiangyang Gou, Lei Zou, Chenxingyu Zhao,Tong Yang, Fast and Accurate Graph Stream Summarization, ICDE 2019