面向Web社会网络的查询处理关键技术研究

近年来，随着互联网应用的不断深化以及Web社会性特征的不断增强， Web社会网络，即各类Web实体及其之间的关系，日益成为了Web上的一种新颖的、重要的数据类型。与此同时，Web社会网络的查询应用以及高质量的Web社会网络分析，都对Web社会网络上的高效查询处理技术提出了需求。然而Web社会网络的海量规模、不确定性和动态性对于图查询处理技术提出了全新的挑战。针对这些挑战，本项目拟基于Web社会网络的结构特征和演化规律，从查询处理、数据组织和查询优化三个方面对面向Web社会网络数据的查询处理关键技术展开研究，以期提出一系列Web社会网络查询处理关键理论、技术和方法。本项目对于进一步提升图数据管理的研究水平、实现面向大图的数据管理系统具有重要的学术意义；对于提高Web社会网络分析质量、满足现实应用中的Web社会网络查询需求，具有实际应用价值。

本课题在基金资助下获得丰硕成果。先后在CCF A类会议SIGMOD、VLDB、ICDE、ICSE、SPLASH；国际四大综合SCI期刊Plos One(影响因子4)发表论文。截止结题，已累计发表5篇A类会议、4篇B类会议、3篇SCI影响因子1.0以上的期刊论文。这些成果针对大规模Web社会网络的查询处理、数据组织、查询优化展开研究，在可重叠社团搜索、带约束的可达性查询、最短距离查询优化、分布式图数据组织、数据压缩方法、数据编码方法等方面提出了新颖的模型以及高效的解决方法；并以Web社会网络的可视化与结构分析为应用示例，论证了模型与方法的有效性。. 其中发表于SIGMOD2013的《Online search of overlapping communities》所提出的可重叠社团搜索模型及相应的近似算法代表了当前国际上社团搜索领域最前沿技术。发表于PVLDB2013的《Toward a Distance Oracle for Billion-Node Graphs》提出的最短距离查询方案是目前国际该问题能够处理的最大规模Web社会网络。发表于ICDE2012《Branch Code: An Efficient Labeling Scheme for Query Answering on Trees》针对以XML格式存储的web社会网络提出了一种新颖的数据编码方法，在支持多种关系查询的同时，有着较低的存储代价。. 基于上述理论成果，先后发布了具有自主知识产权的GraphExplorer、XMLSnippet、SCuV、CGAP-Align等系统，分别应用于社会网络分析、代码关系分析、基因组序列分析等领域。部分算法在微软研究院的大规模图数据库系统Trinity中得以采用。. 本课题成果突出，在国内外产生一定影响力。课题负责人肖仰华博士在SIGMOD2012做了题为《Managing and Mining Large Graphs: Systems and Implementations》会议辅导（Tutorial），并应邀在HOTDB2012、HOTDB2013做大会报告。成果获得教育部2012年高校优秀科研成果二等奖，肖仰华博士获得ACM上海杰出青年科学家提名奖等等荣誉。课题组成果先后7次参加国际顶级会议并作论文报告。课题组先后培养了4位博士、3名硕士。