디지털 라이브러리[ 검색결과 ]
제한된 메모리 환경에서 그래프 스트림 처리를 위한 효율적인 연속 서브 그래프 매칭 기법
이소민, 김상혁, 이현병, 최도진, 임종태, 복경수, 유재수
http://doi.org/10.5626/JOK.2022.49.12.1154
최근 소셜 네트워크 서비스의 확산으로 그래프 데이터의 크기는 점차 방대해지고 있으며 실시간으로 변화된다. 따라서 실시간 그래프 스트림 상에서 연속 질의 처리 수행의 필요성이 증가하고 있다. 또한, 실제 응용 환경에서는 메모리 크기가 제한되어 있기 때문에 크기가 큰 그래프 데이터를 모두 메모리에 유지하기 어렵다. 따라서 제한된 메모리 환경을 고려한 연속 서브 그래프 매칭 기법이 필요하다. 본 논문에서는 제한된 메모리 환경에서 그래프 스트림 처리를 위한 연속 서브 그래프 매칭 기법을 제안한다. 제안하는 기법은 효율적인 연속 서브 그래프 매칭을 위해 색인 관리자, 질의 처리기 및 캐시 관리자 등과 같은 모듈들로 구성된다. 제안하는 기법의 우수성을 입증하기 위해 다양한 성능 평가를 수행한다.
공간 키워드 유사도 기반의 부분적 집단 공간 키워드 질의처리 기법
http://doi.org/10.5626/JOK.2021.48.10.1142
집단적 공간 키워드 질의(collective spatial keyword query)는 질의 위치와 가까우면서 제시된 키워드 집합을 모두 포함하는 관심지점(point of interest; POI)들을 반환한다. 하지만 고정된 수의 질의 키워드를 고려하므로 사용자의 부분 키워드 집합에 대한 선호도를 충분히 반영할 수 없다. 따라서 POI 마다 선호도에 맞는 키워드를 유동적으로 고려하는 새로운 질의인 부분적 집단 공간 키워드 질의(partial collective spatial keyword query)를 제안한다. 이 질의는 조합 최적화 문제이므로 POI의 수가 늘어남에 따라 수행 시간이 급격하게 증가한다. 따라서 이러한 문제를 해결하기 위해 전체적인 탐색 공간을 줄이는 키워드 기반 탐색 기법을 제안한다. 또한 키워드의 부분집합을 계산하는 시간을 줄이기 위해 선형 탐색에 기반한 단말노드 가지치기 기법과 근사 알고리즘 기법 및 임계값에 기반한 가지치기 기법들을 제안한다.
데이터 재사용을 고려한 효율적인 연속 서브 그래프 매칭 기법
http://doi.org/10.5626/JOK.2019.46.8.842
다양한 응용에서 그래프 스트림에 대한 활용이 증가됨에 따라 실시간으로 변화되는 서브 그래프를 탐색하기 위해서는 연속 서브 그래프 매칭 기법이 필요하다. 본 논문에서는 그래프 스트림에서의 색인 재사용과 분산 처리가 가능한 효율적인 연속 서브 그래프 매칭 기법을 제안한다. 서브 그래프 매칭 질의를 분산 처리하기 위해 차수 기반의 질의 분할 기법을 제안하고 그래프 스트림을 분할된 질의 기반으로 색인한다. 다수의 질의가 입력되는 환경에서 야기되는 색인의 부하를 감소시키기 위해서 색인 정보를 재사용한다. 또한, 각 서버의 색인 부하를 계산하는 비용 모델을 통해 질의 할당을 수행한다. 제안하는 기법은 스트림 환경에서 효율적인 분산 처리를 수행하기 위해 스톰에서 구현된다. 우수성을 입증하기 위해 다양한 성능 평가를 수행한다.
