检索结果-南通市图书馆

一种基于Sketch的Top-k紧密中心性快速搜索算法

在线全文

学校读者我要写书评

暂无评论

计算机学报 2016年第10期39卷 1965-1978页

作者：邵蓥侠崔斌马林阴红志北京大学信息科学技术学院高可信软件技术重点实验室北京100871 昆士兰大学信息技术和电子工程学院

在大数据的时代背景下,由于网络数据(network data)能有效简洁地描述社交网络、电子商务、医疗记录、在线教育等多种应用中各类复杂关系,越来越受到工业界和学术界的关注.在社交网络分析任务中,一个基本操作是从网络中发现重要程度前k... 详细信息

在大数据的时代背景下,由于网络数据(network data)能有效简洁地描述社交网络、电子商务、医疗记录、在线教育等多种应用中各类复杂关系,越来越受到工业界和学术界的关注.在社交网络分析任务中,一个基本操作是从网络中发现重要程度前k大的节点.紧密中心性(closeness centrality)是一种常见的节点重要性刻画指标,它用节点在网络中心的程度来反映节点的重要性.用紧密中心性衡量节点重要性进行节点搜索的问题称为top-k紧密中心性搜索问题.然而,传统的精确算法由于其多项式级别的复杂度无法高效地扩展到大规模的网络数据上.近来,研究人员提出了近似算法,通过牺牲结果精度来获得性能提升.通过分析发现,目前存在的近似算法虽然性能得到了有效提升,但是结果精度牺牲过大.为了解决这个问题,该文设计了一种新颖的近似算法,叫做基于Sketch的紧密中心性搜索算法.此近似算法应用了一个全新的计算方式,利用Sketch估计同一距离的邻居数目,然后得到近似的最短距离之和,最终得到各个节点的紧密中心性的估计值.此算法的时间复杂度为O(mt Dmax),其中t是常数,Dmax是网络直径,m是网络边数.根据实际社交网络的小世界现象的特性,此近似算法基本是个线性算法.最后,相比于目前存在的精确算法和近似算法,该文通过全面的实验验证了基于Sketch的紧密中心性搜索算法在时间性能和结果精度等两方面的优势.

关键词：紧密中心性图算法近似算法图分析社交网络

在线全文

学校读者我要写书评

暂无评论

面向高维特征和多分类的分布式梯度提升树

软件学报 2019年第3期30卷 784-798页

作者：江佳伟符芳诚邵蓥侠崔斌高可信软件技术教育部重点实验室(北京大学) 北京100871 北京邮电大学计算机学院北京100876

梯度提升树算法由于其高准确率和可解释性,被广泛地应用于分类、回归、排序等各类问题.随着数据规模的爆炸式增长,分布式梯度提升树算法成为研究热点.虽然目前已有一系列分布式梯度提升树算法的实现,但是它们在高维特征和多分类任务上... 详细信息

梯度提升树算法由于其高准确率和可解释性,被广泛地应用于分类、回归、排序等各类问题.随着数据规模的爆炸式增长,分布式梯度提升树算法成为研究热点.虽然目前已有一系列分布式梯度提升树算法的实现,但是它们在高维特征和多分类任务上性能较差,原因是它们采用的数据并行策略需要传输梯度直方图,而高维特征和多分类情况下梯度直方图的传输成为性能瓶颈.针对这个问题,研究更加适合高维特征和多分类的梯度提升树的并行策略,具有重要的意义和价值.首先比较了数据并行与特征并行策略,从理论上证明特征并行更加适合高维和多分类场景.根据理论分析的结果,提出了一种特征并行的分布式梯度提升树算法***-GBDT设计了一种高效的分布式数据集转置算法,将原本按行切分的数据集转换为按列切分的数据表征;在建立梯度直方图时,FP-GBDT使用一种稀疏感知的方法来加快梯度直方图的建立;在分裂树节点时,FP-GBDT设计了一种比特图压缩的方法来传输数据样本的位置信息,从而减少通信开销.通过详尽的实验,对比了不同并行策略下分布式梯度提升树算法的性能,首先验证了FP-GBDT提出的多种优化方法的有效性;然后比较了FP-GBDT与XGBoost的性能,在多个数据集上验证了FP-GBDT在高维特征和多分类场景下的有效性,取得了最高6倍的性能提升.

关键词：梯度提升树数据并行特征并行系统实现算法比较

PS-Hybrid:面向大规模推荐模型训练的混合通信框架

在线全文

学校读者我要写书评

暂无评论

清华大学学报（自然科学版） 2022年第9期62卷 1417-1425页

作者：苗旭鹏张敏旭邵蓥侠崔斌北京大学信息科学技术学院北京100871 北京邮电大学计算机学院北京100876

传统的分布式深度学习训练系统大多基于参数服务器和全局规约通信框架,缺陷日益显著:参数量大,基于全局规约的去中心化通信架构由于无法存储全量模型而无法使用;通信量大,基于参数服务器的中心化通信架构面临着严重的通信瓶颈。为了解... 详细信息

传统的分布式深度学习训练系统大多基于参数服务器和全局规约通信框架,缺陷日益显著:参数量大,基于全局规约的去中心化通信架构由于无法存储全量模型而无法使用;通信量大,基于参数服务器的中心化通信架构面临着严重的通信瓶颈。为了解决以上问题,该文提出了面向大规模深度学习推荐模型的混合通信训练框架PS-Hybrid,分离了嵌入层参数和其他参数的通信逻辑,实现了PS-Hybrid原型系统。实验结果证明了所提出的混合通信方案能够比纯参数服务器方案取得更好的性能,在16个计算节点下比TensorFlow-PS加速48%。

关键词：推荐模型分布式深度学习参数服务器全局规约

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

社交网络高效高精度去匿名化算法

软件学报 2018年第3期29卷 772-785页

作者：刘家霖史舒扬张悦眉邵蓥侠崔斌高可信软件技术教育部重点实验室(北京大学) 北京100871

自从社交网络成为重要的研究课题,社交网络隐私保护也成为了重要的研究内容,尤其是关于公开发布以供研究的大规模社交网络图数据的隐私保护.为了评估用户的隐私风险,研究者们设计了不同的方法对图进行去匿名化,在不同的图网络中识别个... 详细信息

自从社交网络成为重要的研究课题,社交网络隐私保护也成为了重要的研究内容,尤其是关于公开发布以供研究的大规模社交网络图数据的隐私保护.为了评估用户的隐私风险,研究者们设计了不同的方法对图进行去匿名化,在不同的图网络中识别个体的身份.但是,当前的去匿名化算法或者需要高质量的种子匹配,或者在精确度和效率上颇有不足.提出一种高效高精度的无种子去匿名化算法RoleMatch,基于社交网络的拓扑结构识别个体身份.该算法包括:(1)可以快速计算的两图结点间相似度度量方法 RoleSim++;(2)一种有效的结点匹配算法,此法同时考虑了结点间的相似度和中间匹配结果的反馈.在实验部分,利用LiveJournal的数据,用RoleMatch对比了多种流行的匿名化算法,并根据实际应用情景,在传统实验的基础上增加了局部去匿名化的实验,实验结果验证了所提出的去匿名化算法的优秀性能.

关键词：社交网络去匿名化匿名化隐私保护结点相似度

基于Transformer与技术词信息的知识产权实体识别方法

在线全文

学校读者我要写书评

暂无评论

智能系统学报 2023年第1期18卷 186-193页

作者：王宇晖杜军平邵蓥侠北京邮电大学计算机学院北京100876 北京邮电大学智能通信软件与多媒体北京市重点实验室北京100876

专利文本中包含了大量实体信息,通过命名实体识别可以从中抽取包含关键信息的知识产权实体信息,帮助研究人员更快了解专利内容。现有的命名实体提取方法难以充分利用专业词汇变化带来的词层面的语义信息。本文提出基于Transformer和技... 详细信息

专利文本中包含了大量实体信息,通过命名实体识别可以从中抽取包含关键信息的知识产权实体信息,帮助研究人员更快了解专利内容。现有的命名实体提取方法难以充分利用专业词汇变化带来的词层面的语义信息。本文提出基于Transformer和技术词信息的知识产权实体提取方法,结合BERT语言方法提供精准的字向量表示,并在字向量生成过程中,加入利用字向量经迭代膨胀卷积网络提取的技术词信息,提高对知识产权实体的表征能力。最后使用引入相对位置编码的Transformer编码器,从字向量序列中学习文本的深层语义信息,并实现实体标签预测。在公开数据集和标注的专利数据集的实验结果表明,该方法提升了实体识别的准确性。

关键词：中文命名实体识别知识产权 Transformer编码器信息融合向量表示科技大数据专利深度学习

同方期刊数据库博看期刊评论

在线全文

学校读者我要写书评

暂无评论

基于影响力剪枝的图神经网络快速计算图精简

计算机科学 2023年第1期50卷 52-58页

作者：顾希之邵蓥侠北京邮电大学计算机学院(国家示范性软件学院) 北京100876

计算图精简是提升图神经网络(Graph Neural Network,GNN)模型训练速度的一种优化技术,它利用节点间存在共同邻居的特性,通过消除聚合阶段的冗余计算,来加速图神经网络模型的训练。但是,在处理大规模图数据时,已有的计算图精简技术存在... 详细信息

计算图精简是提升图神经网络(Graph Neural Network,GNN)模型训练速度的一种优化技术,它利用节点间存在共同邻居的特性,通过消除聚合阶段的冗余计算,来加速图神经网络模型的训练。但是,在处理大规模图数据时,已有的计算图精简技术存在计算效率低的问题,影响了计算图精简技术在大规模图神经网络中的应用。文中详细分析了当前的计算图精简技术,统计了包括搜索和重构两阶段处理的时间开销,并总结了现有方法的不足。在此基础上,提出了基于影响力剪枝的图神经网络快速计算图精简算法。该算法应用影响力模型刻画各个节点对计算图精简的贡献,并基于影响力对共同邻居的搜索空间进行剪枝,极大地提升了搜索阶段的效率。此外,详细分析了算法复杂度,从理论上证明了该技术期望的加速效果。最后,为验证所提算法的有效性,将所提算法应用到两种主流的计算图精简技术上,选取常见的图神经网络模型在多个数据集上进行测试,实验结果表明所提算法在保证一定冗余计算去除量的前提下,能够显著地提升计算图精简的效率。相比基线计算图精简技术,所提技术在PPI数据集上搜索阶段的加速效果最高提升了3.4倍,全过程最高提升了1.6倍;在Reddit数据集上搜索阶段的加速效果最高提升了5.1倍,全过程最高提升了3.2倍。

关键词：图神经网络计算图精简共同邻居冗余计算剪枝

在线全文

学校读者我要写书评

暂无评论

面向多GPU的图神经网络训练加速

软件学报 2023年第9期34卷 4407-4420页

作者：苗旭鹏王驭捷沈佳邵蓥侠崔斌北京大学计算机学院北京100871 北京邮电大学计算机学院北京100876

图神经网络由于其强大的表示能力和灵活性最近取得了广泛的关注.随着图数据规模的增长和显存容量的限制,基于传统的通用深度学习系统进行图神经网络训练已经难以满足要求,无法充分发挥GPU设备的性能.如何高效利用GPU硬件进行图神经网络... 详细信息

图神经网络由于其强大的表示能力和灵活性最近取得了广泛的关注.随着图数据规模的增长和显存容量的限制,基于传统的通用深度学习系统进行图神经网络训练已经难以满足要求,无法充分发挥GPU设备的性能.如何高效利用GPU硬件进行图神经网络的训练已经成为该领域重要的研究问题之一.传统做法是基于稀疏矩阵乘法,完成图神经网络中的计算过程,当面对GPU显存容量限制时,通过分布式矩阵乘法,把计算任务分发到每个设备上,这类方法的主要不足有:(1)稀疏矩阵乘法忽视了图数据本身的稀疏分布特性,计算效率不高;(2)忽视了GPU本身的计算和访存特性,无法充分利用GPU硬件.为了提高训练效率,现有一些研究通过图采样方法,减少每轮迭代的计算带价和存储需求,同时也可以支持灵活的分布式拓展,但是由于采样随机性和方差,它们往往会影响训练的模型精度.为此,提出了一套面向多GPU的高性能图神经网络训练框架,为了保证模型精度,基于全量图进行训练,探索了不同的多GPU图神经网络切分方案,研究了GPU上不同的图数据排布对图神经网络计算过程中GPU性能的影响,并提出了稀疏块感知的GPU访存优化技术.基于C++和CuDNN实现了该原型系统,在4个不同的大规模GNN数据集上的实验表明:(1)通过图重排优化,提高了GPU约40%的缓存命中率,计算加速比可达2倍;(2)相比于现有系统DGL,取得了5.8倍的整体加速比.

关键词：图神经网络分布式计算内存优化 GPU加速

在线全文

学校读者我要写书评

暂无评论

面向知识产权的科技资源画像构建方法

软件学报 2022年第4期33卷 1439-1450页

作者：杨佳鑫杜军平邵蓥侠李昂奚军庆智能通信软件与多媒体北京市重点实验室(北京邮电大学) 北京100876 中华人民共和国司法部信息中心北京100020

大数据时代,面向知识产权的科技资源呈现数据规模大、时效性高和价值密度较低等趋势,为有效利用知识产权资源带来严峻的挑战.同时,各个国家对知识产权中隐匿信息挖掘的需求日益增加,使得面向知识产权的科技资源画像构建成为当下的研究热... 详细信息

大数据时代,面向知识产权的科技资源呈现数据规模大、时效性高和价值密度较低等趋势,为有效利用知识产权资源带来严峻的挑战.同时,各个国家对知识产权中隐匿信息挖掘的需求日益增加,使得面向知识产权的科技资源画像构建成为当下的研究热点.目标是通过智能化的数据获取、实体识别以及可视化的方式对知识产权进行画像构建.然而,现有的科技资源画像构建方法只适用于结构化数据,忽略了词语的词性对句子语义理解的影响.因此,提出了一种新颖的面向知识产权的科技资源画像构建算法,针对自动获取的知识产权资源,通过引入词性级别的注意力机制提高实体识别准确率,并以可视化的形式构建知识产权科技资源画像.相比于现有方法,所提出的面向知识产权的科技资源画像构建方法具有以下优势:1)该算法利用词语的词性信息学习句子语义层面的含义,并融合注意力机制,以有监督的方式避免语义理解中的歧义;2)该模型能够智能自动地完成科技数据获取、命名实体识别、科技资源画像构建;3)大量实验结果表明,所提方法利用词语的词性进行有监督学习,在命名实体识别任务中综合性能优于对比算法.

关键词：科技资源画像实体识别数据获取知识产权

HybriG:一种高效处理大量重边的属性图存储架构

在线全文

学校读者我要写书评

暂无评论

计算机学报 2018年第8期41卷 1766-1779页

作者：黄权隆黄艳香邵蓥侠孟嘉任鑫琦崔斌冯是聪北京大学信息科学技术学院高可信软件技术重点实验室北京100871 北京明略软件系统有限公司北京102218

在图中,起点和终点都相同的两条边称为重边.属性图是一种带标志和重边的有向图,图中的点和边可以拥有任意数目的属性值.属性图由于其丰富的表达能力而广泛应用于实际建模中.实际应用中一般用图数据库解决属性图的存储需求.相比于传统的... 详细信息

在图中,起点和终点都相同的两条边称为重边.属性图是一种带标志和重边的有向图,图中的点和边可以拥有任意数目的属性值.属性图由于其丰富的表达能力而广泛应用于实际建模中.实际应用中一般用图数据库解决属性图的存储需求.相比于传统的关系型数据库,图数据库在做多跳邻域查询、路径查询等与图结构相关的查询时,具有更优异的性能.Titan是产业界日渐关注的一个开源的分布式图数据库,Titan的数据以邻接表的方式组织,每个点的邻接表存储了相邻的所有边,这使得与邻接点集相关的查询都需要遍历整个邻接表.当图中含有大量重边时,邻接表规模巨大,这种数据组织方式导致邻域查询性能严重受损.邻域查询是大部分图查询的基础,如多跳邻域查询、路径查询、局部聚集系数查询(计算)等,这些查询往往由嵌套的邻域查询实现,随着邻域深度的增加,这种性能受损将被急剧放大.文中提出了一种基于Titan和列式存储数据库HBase的复合架构设计——HybriG,基于Titan和HBase建立存储层,用Titan来存储图的结构信息和点集的属性信息,HBase存储边集的所有属性信息.在HybriG中邻接表保持了项数和数据量上的精简,从而能克服上述图数据库的缺点.相比于传统图数据库Titan,HybriG在邻域点集相关查询以及边集数据批量导入上的性能提升一个量级以上.文中介绍了HybriG基于Titan和HBase的存储设计,并描述了在此存储设计基础上,如何高效地实现图查询以及图数据的插入操作.此外,文中还提出了图数据的高效导入方案,并保证导入过程中Titan与HBase存储数据的一致性.最后通过实验验证了HybriG在处理大量重边时的优异性能.

关键词：属性图重边图数据库 Titan HBase 架构设计