[논문]FlashGraph에서 너비우선탐색 알고리즘의 성능 개선 방안

이현진; 조용연; 김상욱

FlashGraph에서 너비우선탐색 알고리즘의 성능 개선 방안
Performance Improvement of BFS Algorithm on FlashGraph 원문보기

이현진 (한양대학교 컴퓨터공학부) , 조용연 (한양대학교 컴퓨터 소프트웨어학과) , 김상욱 (한양대학교 컴퓨터 소프트웨어학과)

SNS 사용자가 급증함에 따라 그와 관련된 데이터 또한 폭발적으로 증가하고 있다. 이로 인해, 사회 연결망 데이터 분석을 위한 여러 그래프 처리 엔진들이 개발되었다. 본 논문에서는 최신 그래프 처리 엔진 중 하나인 FlashGraph의 특징을 분석하고 수행 시간을 개선하기 위해 무작위로 매겨진 입력 데이터의 노드 번호를 지역성을 고려해 너비우선탐색 순서로 바꾸어 저장하는 방법을 제안하였다. 실험결과, 수행 시간을 약 1.4배 향상시켰다.

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

4배 정도 빨라졌다는 것을 알 수 있다. 따라서 본 논문을 통해 이와 같은 노드 배치에 따라 알고리즘들의 성능을 개선시킬 수 있는 것으로 판단된다.
본 연구에서는 급증하고 있는 사회 연결망 데이터를 분석하기 위해 개발된 여러 그래프 처리 엔진 중 하나인 FlashGraph의 특징에 대해 분석하고 이를 개선 방안을 찾고 실험을 통해 증명하였다.

제안 방법

본 논문에서는 다양한 응용이 가능한 너비우선탐색 (breadth first search, BFS) 알고리즘에 초점을 맞추어 진행하였다. 너비우선 탐색알고리즘의 성능을 개선하기위해서 노드 번호를 BFS 순서로 매김으로써 성능 개선을 하였다.
따라서 이러한 점을 착안하여 BFS 알고리즘 수행 시, 노드의 순차적인 접근을 유도할 수 있도록 지역성을 고려하여 BFS을 기반으로 노드를 재정렬한다.
이는 그래프엔진이 저장장치에 접근하는 패턴에 있어 성능 악화에 원인이 될 수 있다. 따라서 이를 개선하기 위해 알고리즘의 특성을 분석하였다.
또한 그래프를 모두 접근해야만 처리가 가능했던 기존 그래프 처리 엔진인 GraphChi [2], X-Stream [3]과 달리 엣지 리스트에 선택적인 접근이 가능해서 그래프 알고리즘에서 필요한 데이터들만 읽고 계산함으로써 자원을 절약하였다 [1].
본 논문에서는 다양한 응용이 가능한 너비우선탐색 (breadth first search, BFS) 알고리즘에 초점을 맞추어 진행하였다. 너비우선 탐색알고리즘의 성능을 개선하기위해서 노드 번호를 BFS 순서로 매김으로써 성능 개선을 하였다.
본 실험에서는 주어진 5개의 그래프 데이터에 대해 기존 그래프 입력 데이터 (기존 데이터)와 BFS 순서의 노드로 정렬된 데이터 (변환 데이터)로 각각 수행 시간을 측정하였다.
수행방법에 있어, 스레드의 수에 맞게 그래프의 노드를 균등하게 나누어 처리함으로써 그래프 알고리즘을 병렬적으로 처리하여 성능을 개선시켰다.

성능/효과

다양한 데이터들에 대해 실험을 한 결과 BFS 알고리즘 수행시간에서 기존 방식에 비해 약 1.4배 좋은 성능을 보였다.
본 논문에서는 FlashGraph에서 사용된 그래프 자료구조의 노드의 순서가 무작위로 번호 매겼다는 것을 판단하였다. 이를 개선할 수 있는 방안으로 보고, 그래프 처리에 있어서 응용성이 높은 너비우선 탐색 순서로 번호를 매겼다.
이를 개선할 수 있는 방안으로 보고, 그래프 처리에 있어서 응용성이 높은 너비우선 탐색 순서로 번호를 매겼다. 실험 결과, 기존 파일을 이용했을 때보다 약 1.4배 수행 시간이 향상됨을 확인할 수 있었다.
3배 빨라졌다. 종합적으로, 변환 데이터에서 수행한 알고리즘의 성능이 기존 데이터에서 수행했을 때보다 평균적으로 약 1.4배 정도 빨라졌다는 것을 알 수 있다. 따라서 본 논문을 통해 이와 같은 노드 배치에 따라 알고리즘들의 성능을 개선시킬 수 있는 것으로 판단된다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

FlashGraph에서 너비우선탐색 알고리즘의 성능 개선 방안
Performance Improvement of BFS Algorithm on FlashGraph 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

제안 방법

성능/효과

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

FlashGraph에서 너비우선탐색 알고리즘의 성능 개선 방안 Performance Improvement of BFS Algorithm on FlashGraph 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

성능/효과

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

FlashGraph에서 너비우선탐색 알고리즘의 성능 개선 방안
Performance Improvement of BFS Algorithm on FlashGraph 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper