Ahn9807: 새 문서: 분류: 시스템 벤치마크 == 개요 == https://github.com/sbeamer/gapbs 그래프 알고리즘은 점점 여러 분야에 사용되면서 중요성을 보이고 있다. 이러한 그래프 알고리즘의 처리에 대한 standard한 벤치마크를 제공하기 위해서 Graph500과 같은 유수의 그래프 탐색 경진대회에서 사용한 알고리즘을 이용한 벤치마크이다. == 종류 == 모두 6가지의 그래프들이 사용되었으며, 각각의...

2023-02-11T02:31:11Z

새 문서: 분류: 시스템 벤치마크 == 개요 == https://github.com/sbeamer/gapbs 그래프 알고리즘은 점점 여러 분야에 사용되면서 중요성을 보이고 있다. 이러한 그래프 알고리즘의 처리에 대한 standard한 벤치마크를 제공하기 위해서 Graph500과 같은 유수의 그래프 탐색 경진대회에서 사용한 알고리즘을 이용한 벤치마크이다. == 종류 == 모두 6가지의 그래프들이 사용되었으며, 각각의...

새 문서

[[분류: 시스템 벤치마크]]

== 개요 ==
https://github.com/sbeamer/gapbs

그래프 알고리즘은 점점 여러 분야에 사용되면서 중요성을 보이고 있다. 이러한 그래프 알고리즘의 처리에 대한 standard한 벤치마크를 제공하기 위해서 Graph500과 같은 유수의 그래프 탐색 경진대회에서 사용한 알고리즘을 이용한 벤치마크이다.

== 종류 ==
모두 6가지의 그래프들이 사용되었으며, 각각의 그래프는 social network, engineering, science 와 같은 분야에서 주로 나타나는 패턴을 대표할 수 있도록 하였다.
# Breadth-First Search (BFS): BFS는 그래프를 depth를 1씩 증가시키면서 현재 depth에 해당하는 모든 노드를 검사한다.
# Single-Source Shortest Paths (SSSP): 특정한 source node에서 다른 모든 노드로 향하는 최단 거리를 계산하였다. 모든 grpah weight은 양의 값으로 가정하여 구하였다.
# PageRank (PR): 그래프의 모든 정점에 대한 PageRank를 계산하였다. [[PageRank]]는 검색엔진에서 주로 쓰이는 노드의 중요도를 계산하는 알고리즘이다.
# Connected Componenets (CC): Graph에서 서로 연결된 그래프들의 개수를 구하고 각각의 Connected Componenet에 대해서, 라벨을 할당한다. https://en.wikipedia.org/wiki/Component_(graph_theory)
# Betwenness Centrality (BC): 그래프에서, 한 노드가 얼마나 중요한 의미를 가지고 있는지 계산한다. 이때 BC를 계산할때 중요도는, Shortest path에서 그 정점을 얼마나 많은 노드들이 건너냐로 계산할 수 있다.
# Triangle Counting (TC): 그래프에서 노드 3개가 연결된 triangle이 얼마나 있는지 계산한다.

== 사용한 알고리즘 ==
* Breadth-First Search (BFS) - direction
* Single-Source Shortest Paths (SSSP) - delta stepping
* PageRank (PR) - iterative method in pull direction
* Connected Components (CC) - Afforest & Shiloach-Vishkin
* Betweenness Centrality (BC) - Brandes
* Triangle Counting (TC) - Order invariant with possible relabelling

Gapbs - 편집 역사