【明日报告】博士学位论文答辩公告及教授讲座

李卫榜
学位论文简介

随着信息技术的不断发展,物联网、移动互联网等技术不断进步,各种信息和数据呈爆炸式增长,人们已经步入大数据时代。大数据不仅仅意味着数据规模大,更意味着其中蕴含的数据价值很大,如对企业大数据的充分利用和挖掘可以为企业带来巨大的商业价值。虽然大数据蕴含着很大的价值,但是对数据质量也有着一定的要求,高质量是大数据的效能充分发挥的基础和前提。在数据存在不一致性的情况下,为找出数据中隐含的约束规则,有必要进行诸如函数依赖等约束规则的发现。为提高数据质量,有必要进行不一致性检测,从中发现违反约束规则的不一致性数据。现实世界中脏数据是普遍存在的,脏数据可能导致不正确的结论和错误的决策,提高数据质量或者对数据进行有效清洗成为一个迫切的问题。本文的研究工作得到了得到国家重点基础研究项目(973项目)、国家自然科学基金的支持。


本文的研究内容以及创新点主要体现在如下几个方面:

(1)分布式大数据函数依赖发现方法。

指出函数依赖发现问题面临的挑战和现有函数依赖发现方法的不足,提出了适用于分布式水平切分和垂直切分大数据的函数依赖发现方法。制定了函数依赖发现过程中候选函数依赖搜索策略,给出了发现问题的响应时间代价模型,将负载分配问题划归为整数规划问题并给出近似最优解。定义了适合分布式环境函数依赖发现的剪枝策略,基于广播对发现的局部结果及时进行消息传递和剪枝,从而提升发现效率。基于真实和人工数据集的实验结果表明,提出的函数依赖发现方法在节点扩展性、数据扩展性和属性个数扩展性方面表现良好。


(2)分布式大数据近似函数依赖发现方法。

指出近似函数依赖的应用价值、近似函数依赖发现面临的挑战和现有研究现状和不足,提出了一种适用于分布式水平切分大数据的近似函数依赖并行发现方法。制定了候选近似函数依赖搜索策略。为提高近似函数依赖发现效率,给出了近似函数依赖集合剪枝策略,基于阶段发现结果进行候选函数依赖集合的剪枝,对剪枝效果进行了定量分析。由于任务分配问题为NP-hard问题,给出了近似最优的任务分配方法。实验结果表明,提出的近似函数依赖发现方法与集中式方法相比在数据扩展性和节点扩展性方面优势明显。


(3)分布式大数据不一致性检测方法。

在大数据背景下,为提高函数依赖不一致性检测效率,提出了单个函数依赖和多个函数依赖不一致性并行检测算法。通过散列函数进行数据重分布,确保检测结果的正确性和算法的并行执行。由于检测问题为NP-hard问题,给出近似最优解。针对多个函数依赖不一致性检测问题,根据函数依赖的结构特征进行分组和批量并行检测,研究了分组的最优化问题。提出了一种基于等价类的普适性分布式并行多函数依赖冲突检测方法,给出了检测的响应时间代价模型和任务分配的近似最优算法。将动态均衡负载问题划归为二次规划问题,并采用拉格朗日算子法得到近似最优解。实验结果表明提出的检测方法在数据规模、节点个数、函数依赖个数方面扩展性良好,而且在减少响应时间方面优势明显。


(4)基于统计关系学习的自动数据清洗方法。

分析了现有数据清洗方法的不足和问题的挑战,提出了一种基于统计关系学习和概率推理的无监督自动数据清洗方法,适用于缺乏现成的数据质量模式/规则同时无需人工介入情况下的大规模数据清洗。从全部数据或者数据采样当中学习数据模型并转换成一阶谓词逻辑规则,对一阶谓词逻辑规则权重进行了确定,将一阶谓词逻辑规则转换成DeepDive推理规则并将于DeepDive平台进行推理,结果用于数据修复。实验结果表明,本文提出的方法与已有贝叶斯方法相比在精确度、召回率和F-值等方面明显占优。

学术成果

[1] 李卫榜,李战怀,陈群,姜涛,刘海龙,潘巍. 分布式大数据函数依赖发现[J]. 计算机研究与发展, 2015, 52(2): 282-294. (EI: 0151400720653) 对应博士论文第2章


[2] Weibang Li, Zhanhuai Li, Qun Chen, Tao Jiang, Hailong Liu. Discovering Functional Dependencies in Vertically Distributed Big Data [C]. 16th International Conference on Web Information System Engineering (WISE’15), November 2015, Miami, USA. LNCS 9419 Springer-Verlag, 199–207. (中国计算机学会推荐 C 类会议, EI: 20155101690207) 对应博士论文第3章


[3] 李卫榜,李战怀,陈群,杨婧颖,姜涛.分布式大数据不一致性检测[J].软件学报,2016,27(8):2068-2085. (EI: 20163302717061) 对应博士论文第5章


[4] 李卫榜,李战怀,姜涛. 分布式大数据多函数依赖冲突检测[J].计算机学报, 2017, 40(1):144-160. [doi: 10.11897/SP.J.1016.2017.00144] (EI: 20171403526169)对应博士论文第6章


[5] Weibang Li, Zhanhuai Li, Qun Chen, Tao Jiang, Zhilei Yin. Discovering Approximate Functional Dependencies from Distributed Big Data [C]. The 18th Asia Pacific Web Conference (APWeb’16), September 2016, Suzhou, China. LNCS 9932 Springer-Verlag, 289–301. (中国计算机学会推荐 C 类会议, EI: 20164102893741) 对应博士论文第4章


[6] Weibang LI, Zhanhuai LI, Qun CHEN. Statistical relational learning based automatic data cleaning. Frontiers of Computer Science 外审中. 对应博士论文第7章


索勃
学位论文简介

近些年,随着MapReduce、BSP等同步编程模型和相应开源计算框架的不断涌现,分布式并行图数据处理计算框架凭借其在可扩展性、容错性和易用性等方面的优势,已逐渐成为解决大数据相关问题的首选。基于这些框架与平台的开源实现,结合图数据及其应用的特点,现有研究提出了很多大规模图数据处理与分析的方法,但仍存在如下问题与挑战:(1)在图数据处理与分析计算框架方面,基于同步编程模型设计的计算框架随迭代增加,通讯和同步代价成为瓶颈,如何设计实现突破该瓶颈的通用计算框架;(2)在图数据处理解决方案方面,如何通过并行解决方案设计实现迭代优化,提升响应速度;(3)在图数据处理与分析编程模型方面,面对种类繁多的同步和异步计算框架,以及众多与计算框架紧耦合的并行图算法,如何设计统一编程模型保证算法在不同框架中的兼容性。本文针对分布式计算环境下,并行图数据处理与分析在迭代计算中存在的问题,从计算框架层面提出了基于混合式处理的迭代优化计算框架;从并行解决方案层面,提出了基于迭代优化的并行图模式匹配解决方案;从编程模型层面提出了基于统一编程模型的建模方法,并在社区发现场景借助所提出的编程模型设计和实现了并行化解决方案。本文的研究工作得到了国家自然科学基金重点项目、西北工业大学研究生创业种子基金的支持。


本文的研究内容以及创新点主要体现在如下几个方面:

(1)从图数据处理与分析计算框架的角度,针对同步编程模型在不同场景图数据处理分析中的迭代计算瓶颈,对标准BSP的性能局限展开实践分析。为了减少图数据处理所需全局迭代次数,提出了一种基于混合式处理的优化技术。该优化技术在计算中引入了图分区内部本地伪超步迭代的概念,通过对分区内部和分区间计算区别处理,减少通讯和同步操作,加速收敛。并沿用以节点为中心的编程方式,在BSP编程模型的开源实现上设计和实现了GraphHP计算框架,保持了BSP编程模型的易用性。实验表明了优化后的计算框架在经典应用场景中对于迭代次数、通讯量、处理速度的提升,以及优于现有异步平台的性能表现。


(2)从图数据处理与分析并行解决方案的角度,针对图数据处理与分析算法的迭代开销,提出了基于迭代优化的并行图模式匹配解决方案。 通过将同步编程模型下并行图模式匹配的计算过程抽象为以连接操作为基础的迭代过程,把每轮迭代划分为计算和通讯两个阶段,并围绕迭代过程深入展开了代价分析,提出了并行图模式匹配代价的优化方法。 该优化方法从查询图分解和连接操作两方面均对迭代次数和通讯开销分别进行考量。 在查询图分解优化中,通过控制查询图分解个数降低所需迭代次数,并利用查询图不同标签候选节点差异性优化中间结果规模;在连接操作中,通过bushy-tree的方式构建连接计划,并分别对连接树高度、本地连接、连接代价估计进行了优化。 所提出的解决方案能够兼容现有的单机图模式匹配相关研究。 基于MapReduce的实现验证了所提出并行图模式匹配解决方案所带来的性能收益,以及在处理和响应速度方面优于现有非迭代优化解决方案的性能表现。


(3)从图数据处理与分析编程模型的角度,针对计算框架与并行解决方案的迭代优化兼容性问题,深入分析了同步、异步编程模型各种计算框架迭代优化的差异性,以及并行图算法迭代优化与计算框架的紧耦合特征,为以节点为中心的并行图数据计算框架提出了一种基于统一编程模型—DFA-G的建模方法。 该统一的编程模型通过将图数据处理与分析算法描述为消息驱动的节点状态转移过程,解耦了算法执行的正确性与消息到达顺序的关系,使得根据该模型设计的任何图算法能够保证在异步优化的计算框架上正确执行。 同时,基于DFA-G编程模型设计和实现了一个原型,用户通过图形化界面即可完成模型的创建。 原型根据不同计算框架,提供了模型到可执行程序的自动转换,并通过一系列典型图算法,实验验证了所提出编程模型的正确性与有效性。


(4)针对如何利用统一的编程模型设计和实现真实应用环境中社区发现并行化解决方案的问题,深入分析了典型的图数据处理与分析应用—动态社区发现产生的背景与现实意义,基于信息流动分析提出了动态社区发现方法的新思路,并利用统一编程模型实现了在混合式处理计算框架上的算法并行化建模。 该动态社区发现方法通过对比传染病传播与信息流动过程,结合传染病动力学模型量化节点间交互的密切程度。 并在社区发现质量函数中加入信息流动特征,提高社区发现结果的层次性与时效性。 同时,对集中式社区发现方法的可扩展性问题进行了探讨,并基于DFA-G编程模型完成了算法并行解决方案的建模,利用建模原型生成基于GraphHP的可执行程序,完成了分布式优化和算法移植。 实验证明了所提出动态社区发现方法对社区发现结果的质量提升,以及通过动态社区发现实现社交网络变化过程分析的有效性。

学术成果

[1] Bo Suo, Jing Su, Qun Chen, Zhanhuai Li, and Wei Pan. "DFA-G: A Unified Programming Model for Vertex-Centric Parallel Graph Processing."[C] In Data Mining Workshops (ICDMW), 2016 IEEE 16th International Conference on, pp. 1328-1331. IEEE, 2016. (ICDM Demo, EI: 20171103449972) 对应博士论文第4章


[2] Bo Suo, Zhanhuai Li, Qun Chen, and Wei Pan. "Towards Scalable Subgraph Pattern Matching over Big Graphs on MapReduce."[C] In Parallel and Distributed Systems (ICPADS), 2016 IEEE 22nd International Conference on, pp. 1118-1126. IEEE, 2016. (中国计算机学会推荐C类会议, EI: 20171703592808) 对应博士论文第3章


[3] 索勃, 李战怀, 陈群, 王忠. 基于信息流动分析的动态社区发现方法[J].软件学报. 2014;25(3):547r-59. (一级学报, EI: 20141317523622) 对应博士论文第5章


[4] Bo Suo, Zhanhuai Li, and Wei Pan. "Parallel subgraph matching on massive graphs."[C] In Image and Signal Processing, BioMedical Engineering and Informatics (CISP-BMEI), International Congress on, pp. 1932-1937. IEEE, 2016. (EI: 20171303496360) 对应博士论文第3章


Pascal KLEIMANN
报告人简介

Pascal KLEIMANN 1992年毕业于法国里昂高等化学、物理及电子学校(CPE Lyon)的电子与信息处理学科的微电子专业,获得工程师文凭。于1993年至1997年在里昂国立应用科学学院(INSA Lyon)的LPM研究所攻读博士学位,期间作为主要参与人之一,参与从事“硼掺杂LPCVD多晶硅薄膜的高温压阻特性的重新评估”的基础研究工作。于1997年至1998年在瑞士KTH大学的电子学院攻读博士后,并于1998年回到法国里昂第一大学担任讲师。Pascal KLEIMANN现阶段主要从事通过光电化学蚀刻微硅和纳米结构硅、纳米流体晶体管和微纳流体系统应用于健康领域的研究与设计等3个方面的研究。

报告简介

Electrostatic effects at interfaces are fundamentals in physics and are the source of numerous famous applications (photovoltaic cells, MOS transistors...). After a presentation of the distribution of electrical charges at interfaces, their properties and the key point of polarization, a special attention will be paid to the case of solid/liquid interfaces which are widely encountered in the field of microfluidics and Lap-On-a-Chip. We will show that electrostatic effects can be wisely used to sort, to detect, or to concentrate biomolecules. They can also be used to form high aspect ratio silicon submicrometer structures and membranes.


文案来源丨研究生院

机电学院

美编丨又清