基于图结构的大数据分析与管理技术专刊前言

林学民1,2,  杜小勇3,4,  李翠平3,4
1(新南威尔士大学, 悉尼 1466)
2(华东师范大学 软件学院, 上海  200062)
3(数据工程与知识工程教育部重点实验室, 北京  100872)
4(中国人民大学 信息学院, 北京  100872)

中文引用格式: 林学民,杜小勇,李翠平.基于图结构的大数据分析与管理技术专刊前言.软件学报,2018,29(3). http://www.jos.org.cn/1000-9825/5458.htm

作为一种常用的描述事物之间复杂关联关系的普适结构,图结构被广泛用于表示万维网、社交网络、蛋白质交互网络、化学分子结构、软件代码剽窃检测、复杂对象识别、公路网络、模式识别、超大规模集成电路设计和生态系统中的食物链等.图结构在大数据价值发现中也发挥着重要的作用,如何对基于图结构的大数据进行有效分析和管理,已经成为学术界和工业界关注的新的热点.研究人员提出了很多新颖的图算法,如图生成器、图的可达性判定、相似子图查询、图的特性分析、图查询语言、图上的关键字查询、社交网络分析等,也出现了一些开源的图数据库系统,但总体而言,针对基于图结构的大数据的研究仍然处于起步阶段,还有很多需要研究的问题.

专刊公开征文,共收到投稿53篇(其中包括第34届中国数据库学术会议(NDBC 2017)推荐的22篇高质量论文).其中41篇论文通过了形式审查,内容涉及大数据系统和应用的方方面面.特约编辑先后邀请了80多位专家参与审稿工作,每篇投稿至少邀请2位专家进行评审.稿件经初审、复审、NDBC 2017会议宣读和终审4个阶段,历时5个月,最终有23篇论文入选本专刊.这些文章根据主题可以分为四组:

(一) 基于图结构的大数据并行计算模型、框架与系统.

这组文章有7篇.《S-Maiter:一种流式处理的异步图处理框架》结合累加迭代计算和单机并行处理技术,提出流式处理的异步计算模型ASP.《路径-维度 GraphOLAP大规模多维网络并行分析框架》设计并提出了一种新的图立方体模型:路径-维度立方体,并提出了立方体的物化策略和基于Spark框架的相关算法.《分布式图处理系统技术综述》总结了分布式图处理系统的3个优化目标,从计算粒度、任务调度、通信方式、负载划分等四个维度,对现有分布式图处理系统中的各类优化技术作一个详细的综述.《基于MapReduce的Coteries轨迹模式挖掘及个性化旅游路线推荐》提出基于语义的距离敏感推荐策略(DRSS)和基于语义的从众性推荐策略(CRSS).《基于距离度量的多样性图排序方法》提出一种描述节点间不相似性的距离度量,将多样性图排序问题建模为一个带权完全图的最大和 k-dispersion优化问题.《一种分布式无服务端框架下的因子分解机模型》提出一种新的端到端的分布式框架,并将其应用于分布式环境下符号网络中的链接关系的正负预测问题.《MRSCAN:一种基于MapReduce的图结构聚类算法》关注图结构聚类(SCAN)算法的可扩展性问题,提出了一种新颖的基于MapReduce的海量图结构聚类算法MRSCAN.

(二) 基于图结构的大数据索引和查询技术.

该主题包括了以下6篇文章.《路网环境下的最近邻查询技术研究》对路网环境下的最近邻查询技术进行综述,分别从最近邻查询采用的索引结构和查询处理过程对现有路网环境下的最近邻查询方法进行了分析和比较.《动态图数据匹配技术研究综述》关注动态更新的图数据中进行高效的查询、匹配问题. 从关键技术、代表性算法和性能评价方面对动态图匹配技术进行了综述.《一种基于SQL的图相似性查询方法》研究基于编辑距离的图相似性查询处理问题.针对已有方法在过滤阶段自身存在优缺点和适用性的问题,提出一种全新的面向关系型数据库的过滤框架.《路网环境下兴趣点查询的隐私保护方法》针对在路网环境下,用户查询过程中位置隐私泄露的问题,提出了一种新的位置k匿名隐私保护方法,克服了传统k-匿名不能抵御推断攻击的缺陷．《基于疾病信息网络的表型相似基因搜索》利用疾病公开数据库构建了疾病信息网络, 并设计了基于此的相似基因搜索算法gSim-Miner.《一种路网感知的在线轨迹压缩方法》提出了一种路网感知的在线轨迹压缩方法,在综合考虑移动轨迹的特点和地图质量的基础上,针对轨迹压缩的需要,设计了一种距离有界的地图匹配算法.

 (三) 基于图结构的大数据分析和挖掘技术、以及深度学习方法.

该主题包括以下8篇文章.《基于边采样的网络表示学习模型》提出一个能够编码节点间丰富关系信息的无监督网络表示学习模型NEES.《RoleMatch:一种社交网络高效高精度去匿名化算法》提出了一种高效高精度的无种子去匿名化算法“RoleMatch”,基于社交网络的拓扑结构识别个体身份.《一种融合节点先验信息的图表示学习方法》提出了一种改进的图表示学习方法GeVI.该方法将已知的节点特征看作先验知识,并基于DeepWalk思想,将图表示学习问题转化为词表示学习问题.《基于循环神经网络的数据库查询开销预测》提出了一种基于循环神经网络的查询开销预测方法,该方法不仅能预测出查询计划的执行时间,而且在查询执行前就能得到预测结果.《一种基于全视角特征结合众包的跨社交网络用户识别方法》关注识别出不同社交网络上的同一用户,提出了一种基于全视角特征结合众包的跨社交网络用户识别方法(OCSA).《基于树分解的空间众包最优任务分配算法》研究空间众包中最优任务分配问题,利用树分解技术将工人分割成独立的集合,并提出一种带启发式的深度优先搜索算法.《一种多维图结构聚类的社交关系挖掘算法》提出了一种有效的子空间聚类算法SCA,首次对多维度下子空间的图结构聚类进行研究,目的是探索如何通过图数据挖掘发现对象间真实的社交关系.《基于社区的动态网络节点介数中心度更新算法》针对动态网络中节点介数中心度计算困难的问题,提出一种基于社区的节点介数中心度更新算法.

(四)新型硬件下的图数据管理技术.

论文《一种应对倾斜数据流在线连接的方法》基于二部图连接模型,提出了一种应对倾斜数据流的在线连接方法.论文《基于向量引用的Platform-oblivious内存连接优化技术研究》通过优化内存哈希表设计,消除哈希代价对内存连接算法的影响,从而更加准确地测量内存连接算法在不同硬件相关因素影响下的性能特征.

本专刊主要面向大数据、数据库、数据挖掘、机器学习、体系结构等多领域的研究人员和工程人员,反映了我国学者在基于图结构的大数据分析与管理技术领域最新的研究进展.感谢《软件学报》编委会和数据库专委会对专刊工作的指导和帮助,感谢专刊全体评审专家及时、耐心、细致的评审工作,感谢向本专刊踊跃投稿的所有作者.希望本专刊能够对大数据相关领域的研究工作有所促进.

林学民(1963-),男,国家“千人计划”教授,博士生导师. 国际期刊IEEE Transactions on Knowledge and Data Engineering主编,多次应邀担任SIGMOD, VLDB, ICDE, KDD等国际会议的程序委员.主要研究领域为数据库理论、算法与技术研究,时空数据和流数据的查询、图和文本的匹配查询、不确定数据的概化查询及图数据可视化等.在本领域顶级国际学术会议与期刊上发表论文90余篇.
 
杜小勇(1963－),男,中国人民大学信息学院计算机科学与技术系教授,博士生导师,教育部数据工程与知识工程重点实验室主任.中国计算机学会会士,数据库专委会主任,《大数据》期刊副主编,国家重点研发专项“云计算和大数据”专家组成员等.长期从事数据库与大数据方面的教学与研究工作,先后承担核高基、973等多项国家级课题,在本领域国际重要期刊和会议上发表高水平学术论文100余篇.

 
李翠平(1971-),女,中国人民大学信息学院计算机科学与技术系教授,博士生导师.长期从事数据库教学与科研工作,在本领域国际重要期刊和学术会议上发表高水平学术论文100余篇.2007年入选北京市组织部优秀人才培养资助计划.2009年入选教育部新世纪优秀人才支持计划.2011年获得中国计算机学会青年科学家奖.目前研究方向为社会网络分析、社会推荐、大数据分析和挖掘等.