2016年12月数据科学与工程论坛回顾

2016年12月18日，来自于北京航空航天大学的马帅教授和来自于北京大学的邹磊副教授在数据科学与工程论坛，分别作了题为“Towards Big Graph Search: Challenges and Techniques”和“基于图的RDF知识图谱数据管理”的学术报告。

随着数据量的不断增大，数据处理的需求与传统应用产生巨大差异，数据的存储与处理发生了一系列的转变。从最早期仅支持非常简单的搜索功能的文件系统存储，到支持SQL查询语言的数据库，再至更关心关键字搜索的互联网。随着FACEBOOK于2013年初提出“graph search”的概念，大数据的研究进入了一个新的阶段。

图搜索是一种新型的社会搜索模式。所有的社会活动构成了社会网络，本质上这是图的一种表现形式。图搜索与传统关系数据库搜索相比，可以更高效地处理社交网络中的相关查询。而与WEB搜索相比较，相对于传统的基于关键字的查询，图搜索还支持基于自然语言的查询。此外，图搜索还支持基于实体，如人、社群等对象的查询。同时，图搜索更好地支持了针对不断变化的数据的查询。

马帅教授

马帅老师介绍了他在图搜索中的一系列研究工作。

子图查询是图搜索中常用的查询之一，其是指对于给定一个输入图，输出给定图中与其“匹配”的子图集合。常见的子图查询有三类：凝聚子图查询、关键词图查询和图模式匹配查询。而其中的“匹配”在不同应用中有不同的含义，如：最短路径、子图同构、图同态及其扩展、图模拟及其扩展、图关键字搜索、紧邻查询等。

对于大规模图数据的查询，则具有更多的挑战：数据量的增大需要高效的图搜索算法从而在查询性能与准确性间找到平衡，而数据的频繁变化则需要在搜索时考虑数据的动态性和时间特征。大规模图数据中的数据丢失和不确定性则对如何提高数据的质量，减少负面影响提出了挑战。基于此，对于大规模的图数据搜索，报告提出了FAE法则，即提供友好的搜索界面、更准确地搜索需要的信息，以及更快地返回搜索结果。

“

为了支持对大规模图数据的查询，马帅老师主要运用了查询近似技术，即对一类查询复杂性高的查询语言Q，变换为一类查询复杂性低的查询语言Q’，并且尽量不影响查询结果的准确性。为了平衡查询的复杂性和查询准确性，在不同的子图查询中，可以运用一系列查询近似技术，如用强模拟图查询替代子图同构查询、利用数据驱动的查询近似方法配合数据筛选提高时态稠密图的效率等。

除此之外，马帅老师还利用了数据近似技术缩小图数据的规模，提高查询效率，即对一类查询复杂性高的查询语言Q，将查询数据D变 换机器能够高效处理的较小量D’，并且尽量不影响查询结果的准确性。这一方法可以被应用于最短路径查询、网络异常检测、网络链接预测等领域。

分布式的数据处理技术亦可用于提高大图搜索的效率。现实中的图通常非常大，使用单机来管理和查询图不现实，分布式计算模型可以利用多台机器组成的机群通过本地计算和消息传送的形式协同完成搜索。而增量计算技术则是应对大规模数据的不断变化的手段之一，可以在历史搜索结果的基础上只搜索增量数据提高搜索效率。同时，其它一些技术亦被用于提高搜索效率，如数据索引、数据压缩、数据划分等。

”

邹磊副教授

邹磊老师则介绍了他在RDF数据查询、系统研发及其应用中的工作。

RDF是一种数据模型，是由万维网联盟组织的资源描述框架工作组于1999年提出的一个解决方案，并于2004年2月正式成为万维网联盟推荐标准。其目标是构建一个综合性的框架来整合不同领域的元数关键词：RDF数据管理关键词检索据，实现在万维网上交换元数据，促进网络资源的自动化处理。

RDF的基本数据模型包括资源（resource）、属性（property）及陈述（statements）。所有能够使用RDF表示的对象都称为资源，包括网络上的所有信息、虚拟概念和现实事物等等。资源以唯一的统一资源标识（uniform resource identifiers，URI）来表示。属性则用来描述资源的特征或资源间的关系。每一个属性都有其意义，用于定义资源的属性值、描述属性所属的资源形态、与其他属性或资源的关系。而一条陈述包含三个部分，通常称为RDF三元组。其中主体一定是被描述的资源，由URI表示。客体表示主体在属性上的取值，可以是另外一个资源（由URI表示）或者是文本。

目前，海量RDF数据存储和查询的方案分为两种：一种是将三元组数据映射成关系数据库中的表结构，利用现有的关系型数据库管理系统来完成面向RDF查询检索；另一种是基于图结构的存储方式。因为RDF数据本身就是基于图结构的，所以可以利用图数据库中的操作来完成对RDF数据的查询。

SPARQL查询语言是由万维网联盟的“RDF Data Access”工作组（DAWG）开发的一种面向RDF数据的查询语言，目前已经成为万维网联盟的RDF查询语言的推荐标准。SPARQL语言与关系数据库中的SQL语言类似，这方便了用户对于SPARQL语言的使用。例如在SPARQL语法中，也是在SELECT部分指定查询变量，在WHERE部分指定查询条件，而查询条件通常由三元组来构成，其中三元组的某一项或者某几项可以由变量来表示。

通过将RDF三元组看作带标签的边，RDF数据很自然地符合图模型结构。因此，可以从RDF图模型结构的角度来看待RDF数据。通过将RDF数据视为一张图，并以图的形式存储来解决RDF数据的存储问题。图模型符合RDF模型的语义层次，可以最大限度地保持RDF数据的语义信息，也有利于对语义信息的查询。此外，以图的方式来存储RDF数据，可以借鉴成熟的图算法、图数据库来设计RDF数据的存储方案与查询算法。然而，利用图模型来设计RDF存储与查询也存在难以解决的问题：第一，相对于普通的图模型，RDF图上的边具有标签，并可能成为查询目标；第二，典型的图算法时间复杂度较高，需要精心的设计以降低实时查询的时间复杂度。

“

邹磊提出用gStore系统来存储RDF和回答SPARQL查询语句。通过编码的方法，将RDF图G中的每个实体节点、邻居属性和属性值编码成一个带有Bitstring的节点，从而得到一张标签图G*。也可以将查询图Q表示成一张查询的标签图Q*。可以证明Q*在G*上的匹配是Q在G上匹配的超集。为了有效地支持在G*上查找Q*的匹配位置，gStore系统提出了VS-tree索引。在所有G*的叶子节点上建立S-tree索引，S-tree每个叶子节点对应G*上的一个点。为了构建VS-tree，当且仅当S-tree上的两个非叶子节点的子孙之间在RDF图上存在一条边时，引入一条边连接这两个非叶子节点。也就是说，VS-tree每个非叶子层是底层G*的不同粒度的摘要图。利用每层的摘要图，gStore系统利用VS-query算法来削减查询空间，加快查询速度。

”

◆ ◆ ◆ ◆

DaSE全体同仁恭祝您

2017新年快乐

HAPPY NEW YEAR

◆ ◆ ◆ ◆

华东师范大学数据科学与工程学院