Invention Publication
- Patent Title: 一种基于SCC‑DAG的图计算迭代处理方法
- Patent Title (English): Graphic calculation iteration processing method based on SCC-DAG
-
Application No.: CN201611070021.6Application Date: 2016-11-28
-
Publication No.: CN106776858APublication Date: 2017-05-31
- Inventor: 廖小飞 , 金海 , 石翔 , 张宇 , 李陈希
- Applicant: 华中科技大学
- Applicant Address: 湖北省武汉市洪山区珞喻路1037号
- Assignee: 华中科技大学
- Current Assignee: 华中科技大学
- Current Assignee Address: 湖北省武汉市洪山区珞喻路1037号
- Agency: 华中科技大学专利中心
- Agent 赵伟
- Main IPC: G06F17/30
- IPC: G06F17/30

Abstract:
本发明公开了一种基于SCC‑DAG的图计算迭代处理方法,包括预处理步骤和计算步骤;具体地,在预处理阶段获取给定的图中的所有SCC并通过各SCC之间的连接构建SCC‑DAG;在计算阶段,按照SCC‑DAG中SCC的拓扑排序依次在SCC‑DAG的各SCC内进行迭代直至所有SCC收敛,输出收敛状态的数据作为相应算法的运行结果;本发明提供的基于SCC‑DAG的图计算迭代处理方法将迭代处理限定在SCC内部,每个SCC内部独立进行迭代操作,当SCC‑DAG内所有的SCC都收敛时,整张图达到收敛状态;该图计算迭代处理方法用很小的预处理开销换取图收敛速度的提高,减少了计算冗余,降低了IO资源开销。
Information query