디지털 라이브러리[ 검색결과 ]
GPU 가속 스케줄링 및 연산 축소에 기반한 효율적인 동적 그래프 처리
송상호, 최지현, 차동현, 이현병, 최도진, 임종태, 복경수, 유재수
http://doi.org/10.5626/JOK.2024.51.12.1125
최근 대용량 동적 그래프를 효율적으로 처리하기 위해 GPU를 활용하는 연구가 활발히 진행되고 있으며, 동적 그래프 처리 시 같은 데이터가 반복적으로 전송되고 처리되는 문제가 발생하고 있다. 본 논문에서는 메모리가 제한된 GPU 환경에서 대규모 동적 그래프를 효율적으로 처리하기 위한 동적 스케줄링 방법과 연산 축소 방법을 제안한다. 동적 스케줄링 방법은 동적 그래프를 분할하여 각 파티션을 활성 정점과 예비 활성 정점을 고려한 스케줄링 방식으로 GPU에 배치함으로써 처리 성능을 극대화한다. 또한, 그래프의 변화 양상을 반영하기 위해 스냅샷을 활용한다. 연산 축소 방법은 스냅샷을 통해 동적 그래프에서 중복된 간선 및 정점의 변경을 감지하여 불필요한 연산을 줄임으로써 GPU의 연산량과 데이터 전송 비용을 최소화하는 기법이다. 이를 통해 동일한 간선이나 정점에 대한 중복 연산을 방지하여 성능을 향상시킨다. 다양한 성능 평가 결과 기존 정적 그래프 처리 기법 대비 평균 280%, 기존 동적 그래프 처리 기법 대비 평균 108%의 성능 향상을 확인하였다.
제한된 메모리 환경에서 그래프 스트림 처리를 위한 효율적인 연속 서브 그래프 매칭 기법
이소민, 김상혁, 이현병, 최도진, 임종태, 복경수, 유재수
http://doi.org/10.5626/JOK.2022.49.12.1154
최근 소셜 네트워크 서비스의 확산으로 그래프 데이터의 크기는 점차 방대해지고 있으며 실시간으로 변화된다. 따라서 실시간 그래프 스트림 상에서 연속 질의 처리 수행의 필요성이 증가하고 있다. 또한, 실제 응용 환경에서는 메모리 크기가 제한되어 있기 때문에 크기가 큰 그래프 데이터를 모두 메모리에 유지하기 어렵다. 따라서 제한된 메모리 환경을 고려한 연속 서브 그래프 매칭 기법이 필요하다. 본 논문에서는 제한된 메모리 환경에서 그래프 스트림 처리를 위한 연속 서브 그래프 매칭 기법을 제안한다. 제안하는 기법은 효율적인 연속 서브 그래프 매칭을 위해 색인 관리자, 질의 처리기 및 캐시 관리자 등과 같은 모듈들로 구성된다. 제안하는 기법의 우수성을 입증하기 위해 다양한 성능 평가를 수행한다.
스파크 환경에서 내용 기반 이미지 검색을 위한 효율적인 분산 인-메모리 고차원 색인 기법
최도진, 박송희, 김연동, 위지원, 이현병, 임종태, 복경수, 유재수
http://doi.org/10.5626/JOK.2020.47.1.95
영상에서 범죄 행위 모니터링 및 추적을 위해서 이미지 내에 포함된 객체를 검색하는 내용 기반 검색이 활용되고 있다. 본 논문에서는 내용 기반 이미지 검색을 위해 이미지 또는 객체에서 추출한 대용량 특징 벡터를 이용한 유사도 검색을 지원하는 분산 인-메모리 기반 고차원 색인 기법을 제안한다. 대용량 분산 처리를 위해 빅데이터 플랫폼인 스파크를 활용하고 효율적인 분산 질의 처리 할당을 위해 마스터/슬레이브 모델을 활용한다. 마스터에서는 데이터 및 질의 분배를 수행하고 슬레이브에서는 데이터를 색인한다. 더불어 기존 분산 고차원 색인 기법에서 k-최근접 질의 처리의 성능 문제를 해결하기 위해서 밀집도 및 탐색 비용을 고려한 k-최근접 질의 최적화 기법을 제안한다. 제안하는 기법의 우수성 및 타당성을 입증하기 위해 다양한 성능 평가를 수행한다.
소셜 사물 인터넷에서 상호 작용 분석을 통한 유사 사용자 추천
http://doi.org/10.5626/JOK.2020.47.1.61
최근 소셜 네트워크와 사물 인터넷을 결합한 소셜 사물 인터넷에 대한 연구가 많이 진행되고 있다. 소셜 사물 인터넷은 사물 또는 사용자간 정보 공유를 위해 사용자와 사용자 간에 연결 관계 뿐만 아니라 사용자와 객체 간에 관계 설정이 중요하다. 본 논문에서는 소셜 사물 인터넷에서 객체와 사용자간에 상호 작용을 고려한 유사 사용자를 추천하는 기법을 제안한다. 제안하는 기법은 객체를 중심으로 사용자의 행위를 분석함으로써 사용자와 유사한 사용자를 찾을 수 있다. 제안하는 기법은 소셜 네트워크에서 사용자들이 작성한 문서들을 기반으로 관심도를 판별해 유사도를 계산함으로써 유사도의 정확도를 향상시킬 수 있다. 최종적으로 두 유사도 값을 고려하여 사용자 Top-N명을 유사 사용자로 추천한다. 제안하는 기법의 우수성을 보이기 위해 다양한 성능평가를 수행한다.
데이터 재사용을 고려한 효율적인 연속 서브 그래프 매칭 기법
http://doi.org/10.5626/JOK.2019.46.8.842
다양한 응용에서 그래프 스트림에 대한 활용이 증가됨에 따라 실시간으로 변화되는 서브 그래프를 탐색하기 위해서는 연속 서브 그래프 매칭 기법이 필요하다. 본 논문에서는 그래프 스트림에서의 색인 재사용과 분산 처리가 가능한 효율적인 연속 서브 그래프 매칭 기법을 제안한다. 서브 그래프 매칭 질의를 분산 처리하기 위해 차수 기반의 질의 분할 기법을 제안하고 그래프 스트림을 분할된 질의 기반으로 색인한다. 다수의 질의가 입력되는 환경에서 야기되는 색인의 부하를 감소시키기 위해서 색인 정보를 재사용한다. 또한, 각 서버의 색인 부하를 계산하는 비용 모델을 통해 질의 할당을 수행한다. 제안하는 기법은 스트림 환경에서 효율적인 분산 처리를 수행하기 위해 스톰에서 구현된다. 우수성을 입증하기 위해 다양한 성능 평가를 수행한다.
분산 처리 환경에서 동적 분할 그리드 색인 기반 근사 k-최근접 질의 처리
http://doi.org/10.5626/JOK.2018.45.8.838
최근 스마트 기기의 대중화로 다양한 위치 기반 서비스가 제공되고 있다. 소셜 네트워크 서비스와 결합한 위치 기반 소셜 네트워크 서비스들은 대규모의 사용자가 존재한다. 이러한 서비스들은 사용자를 중심으로 가장 가까운 위치를 제공하는 k-최근접 질의 처리의 요구가 증가하고 있다. 본 논문에서는 실시간 응답 요구를 위해 동적 분할 기반의 그리드 색인을 구축하여 근사 k-최근접 질의 처리를 수행하는 기법을 제안한다. 제안하는 근사 k-최근접 질의 처리 기법은 사용자의 이동 방향을 고려하여 이동 방향에 위치하는 셀을 우선하여 탐색한다. 또한, 근사 k-최근접 질의의 정확성 개선을 위해 그리드 동적 분할 방법과 그리드 색인에서 셀 탐색을 최적화한다. 제안하는 기법은 스트림 환경에서 효율적인 분산 처리를 수행하기 위해 스톰에서 구현된다. 우수성을 입증하기 위해 다양한 성능 평가를 수행한다.
소셜 시맨틱 웹 환경에서 프로버넌스 기반의 웹 데이터 신뢰도 평가 기법
최근 사용자들 사이의 웹 데이터의 생성 및 공유가 활발해 지면서 시맨틱 웹과 소셜 웹이 결합한 소셜 시맨틱 웹에 대한 중요성이 증가되고 있다. 본 논문은 소셜 시맨틱 웹 환경에서 PROV 모델을 확장하여 프로버넌스 기반의 웹 데이터 신뢰성 평가 기법을 제안한다. 제안하는 기법은 소셜 시맨틱 웹환경에서 웹 데이터의 프로버넌스를 관리하고 신뢰성 평가를 위해 W3C의 PROV 모델에 필요한 요소를 추가하였다. 이와 같이 확장된 PROV 모델은 웹 데이터의 관리 및 프로버넌스 추적을 지원한다. 제안하는 신뢰성 평가 기법은 사용자의 신뢰도, 원본 데이터의 신뢰도 그리고 사람들의 평가 등과 같은 다양한 파라미터를 고려한다. 평가된 신뢰도는 프로버넌스 정보로 관리되고 사용자의 질의를 처리할 때 이 신뢰도를 고려하여 결과를 생성한다. 따라서 제안하는 기법은 소셜 시맨틱 웹 데이터의 프로버넌스를 관리할 수 있고 다양한 파라미터를 이용하여 웹 데이터 신뢰도를 정확하게 계산할 수 있다. 평가된 신뢰도는 사용자가 질의 결과의 신뢰 여부를 판단할 수 있는 기준이 된다. 제안하는 기법의 타당성을 보이기 위해 SPARQL 질의를 이용하여 신뢰성 평가의 성능을 검증한다.
