期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到3篇文章
< 1 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
一种高效的面向动态有向图的增量强连通分量算法 被引量：6
1
作者 廖小飞 陈意诚 +3 位作者 张宇 金海 刘海坤 赵进 《中国科学：信息科学》 CSCD 北大核心 2019年第8期988-1004,共17页
强连通分量(strongly connected component, SCC)算法可以将一个有向图缩略为有向无环图(directed acyclic graph, DAG),广泛应用于可达性查询等有向图分析应用.尽管现有工作已经提出多种面向静态有向图的强连通分量算法,但是它们需要... 强连通分量(strongly connected component, SCC)算法可以将一个有向图缩略为有向无环图(directed acyclic graph, DAG),广泛应用于可达性查询等有向图分析应用.尽管现有工作已经提出多种面向静态有向图的强连通分量算法,但是它们需要高额的运行时开销来反复对整个图进行全量计算,以响应现实世界中普遍存在的动态有向图结构的频繁变化.其实,在通常情况下,动态有向图每次改变量极小(少于5%).其允许我们以增量的方式对动态有向图进行强连通分量计算,以缩短响应时间.因此,为解决此问题,本文提出了一种高效的面向动态有向图的增量强连通分量算法Incremental Strongly Connected Components Algorithm,简称Inc-SCC,通过对不必要的计算进行裁剪以减少算法的数据访问量和计算量,并利用SCC的不相交性进行并行处理以提升SCC计算效率.其次,提出了一种启发式优化方法进一步加快算法收敛速度.实验结果显示,本方法可以用于实时响应有向图持续性动态变化,并且当整个有向图的边变化比例为5%时,本方法相对于现有算法的加速比可达2.8到12倍,当整个有向图的边变化比例为0.5%时,本方法相对于现有算法的加速比可达2.9到12倍. 展开更多
关键词 强连通分量 动态有向图 增量计算 收敛 有向无环图
原文传递
面向动态有向图的单调图算法硬件加速机制 被引量：1
2
作者 杨赟 余辉 +8 位作者 赵进 张宇 廖小飞 姜新宇 金海 刘海坤 毛伏兵 张吉 王彪 《中国科学：信息科学》 CSCD 北大核心 2023年第8期1575-1592,共18页
随着现实世界中动态图计算需求的快速增长,现有的研究工作已经提出了多种方法来有效支持单调图算法在动态有向图中的处理.然而,由于动态有向图的图结构频繁发生变化,其相邻图顶点之间的状态更新存在复杂的依赖关系,这使得现有的软硬件... 随着现实世界中动态图计算需求的快速增长,现有的研究工作已经提出了多种方法来有效支持单调图算法在动态有向图中的处理.然而,由于动态有向图的图结构频繁发生变化,其相邻图顶点之间的状态更新存在复杂的依赖关系,这使得现有的软硬件方法在处理单调图算法时依然面临着数据访问成本高和收敛速度慢的问题.为此,本文提出了一种面向动态有向图的单调图算法加速器DSGraph,它能够充分利用图顶点之间的依赖关系来加快单调图算法在动态有向图处理中的收敛速度,并有效降低数据访问成本.具体来说,DSGraph通过实时提取动态有向图中图顶点的局部拓扑依赖顺序来执行异步迭代处理,从而显著减少冗余的图顶点状态更新.同时,DSGraph设计了一种异步迭代流水线架构,其按照依赖顺序对图顶点状态进行异步迭代处理,从而加速图顶点状态传播速度并减少数据访问开销.最后,DSGraph提出了一种无阻塞数据同步机制,通过并行执行本地图顶点的状态更新和外部图顶点的数据同步来减少系统同步开销.实验显示,与目前最先进的面向单调图算法的动态图处理系统KickStarter相比,DSGraph将动态有向图处理速度平均提升了11.2倍. 展开更多
关键词 动态有向图 单调图算法 增量计算 依赖感知 图加速器
原文传递
基于DOG的异常行为监测模型的设计
3
作者 张春芳 张军 白会肖 《计算机工程与设计》 CSCD 北大核心 2008年第14期3815-3817,共3页
为了在监控系统中识别行人的动作,提出了一种用于异常行为预测和检测的实时视频监控系统模型,模型基于动态有向图(DOG)进行实时无人监控。通过单向连接点结构方式来描述观测行为,其中每个点定义了被观测的运动物体在标准属性多维空间的... 为了在监控系统中识别行人的动作,提出了一种用于异常行为预测和检测的实时视频监控系统模型,模型基于动态有向图(DOG)进行实时无人监控。通过单向连接点结构方式来描述观测行为,其中每个点定义了被观测的运动物体在标准属性多维空间的区域,并对产生异常行为的人确定可能性。实验结果表明,该方法能够成功跟踪运动的目标并区分其行为类型,跟踪效果可靠、精确。 展开更多
关键词 异常行为 动态有向图 单向连接点 视频跟踪 动态分类器
下载PDF
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
使用帮助 返回顶部