디지털 라이브러리[ 검색결과 ]
제한된 메모리 환경에서 그래프 스트림 처리를 위한 효율적인 연속 서브 그래프 매칭 기법
이소민, 김상혁, 이현병, 최도진, 임종태, 복경수, 유재수
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
다양한 응용에서 그래프 스트림에 대한 활용이 증가됨에 따라 실시간으로 변화되는 서브 그래프를 탐색하기 위해서는 연속 서브 그래프 매칭 기법이 필요하다. 본 논문에서는 그래프 스트림에서의 색인 재사용과 분산 처리가 가능한 효율적인 연속 서브 그래프 매칭 기법을 제안한다. 서브 그래프 매칭 질의를 분산 처리하기 위해 차수 기반의 질의 분할 기법을 제안하고 그래프 스트림을 분할된 질의 기반으로 색인한다. 다수의 질의가 입력되는 환경에서 야기되는 색인의 부하를 감소시키기 위해서 색인 정보를 재사용한다. 또한, 각 서버의 색인 부하를 계산하는 비용 모델을 통해 질의 할당을 수행한다. 제안하는 기법은 스트림 환경에서 효율적인 분산 처리를 수행하기 위해 스톰에서 구현된다. 우수성을 입증하기 위해 다양한 성능 평가를 수행한다.
도로 교통망에 대한 사용자의 선호도 변화를 반영한 경로 추천
http://doi.org/10.5626/JOK.2019.46.1.77
위치기반 서비스는 지도 및 주변 정보를 제공하거나 특정 목적지까지 가기 위한 경로를 제공한다. 그 중 경로 추천 시스템은 각 사용자의 경로에 대한 평가 기준에 가장 적합한 경로를 추천하는 시스템이다. 기존의 개인화된 경로 추천 시스템은 시간대의 변화와 관계없이 사용자의 선호도가 일정하다는 가정하에서 추천한다는 단점이 존재한다. 하지만 이는 오전 시간대에는 이동 거리를 중시하고, 오후 시간대에는 위험도를 중시하는 것처럼 시간대마다 중요하게 생각하는 요소가 다른 다양한 사용자의 요구사항을 반영하지 못하는 문제가 존재한다. 본 논문은 해당 문제를 해결하기 위해 먼저 시간 속성을 고려한 다익스트라 기법을 제안한다. 또한 계산 비용을 줄이기 위해 G-tree 인덱스 구조를 사용하여 시간대에 따른 선호 요소 가중치 변화를 반영한 경로를 탐색할 수 있는 효율적인 알고리즘을 제안한다.
데이터 접근 패턴 은닉을 지원하는 암호화 인덱스 기반 kNN 질의처리 알고리즘
데이터베이스 아웃소싱 환경에서, 클라우드는 인증된 사용자에게 아웃소싱된 데이터베이스를 기반으로 질의 서비스를 제공한다. 그러나 금융, 의료 정보와 같은 민감한 데이터는 클라우드에 아웃소싱 되기 전에 암호화되어야 한다. 한편, kNN 질의는 다양한 분야에서 폭넓게 사용되는 대표적인 질의 타입이며, kNN 질의 결과는 사용자의 관심사 및 선호도와 밀접하게 연관된다. 따라서 데이터 보호와 질의 보호를 동시에 고려하는 kNN 질의 처리 알고리즘에 대한 연구가 진행되어 왔다. 그러나 기존 연구는 높은 연산 비용이 요구되거나, 탐색한 인덱스의 노드 및 반환된 질의 결과가 드러나기 때문에 데이터 접근 패턴이 노출되는 문제점이 존재한다. 이러한 문제를 해결하기 위해 본 논문에서는 암호화 데이터베이스 상에서의 kNN 질의처리 알고리즘을 제안한다. 제안하는 알고리즘은 데이터 보호 및 질의 보호를 지원한다. 또한, 제안하는 알고리즘은 데이터 접근 패턴을 보호하는 동시에 효율적인 질의처리를 지원한다. 이를 위해, 데이터 접근 패턴 노출 없이 데이터 필터링을 지원하는 암호화 인덱스 탐색 기법을 제안한다. 성능 분석을 통해, 제안하는 알고리즘이 기존 기법에 비해 질의처리 시간 측면에서 우수한 성능을 보임을 검증한다.
대용량 데이터 분석을 위한 맵리듀스 기반 kNN join 질의처리 알고리즘
최근 모바일 기술의 발달 및 소셜 네트워크 서비스의 활성화를 통해 사용자 데이터가 급격히 증대되고 있다. 이에 따라 대용량 데이터에 대한 효율적인 데이터 분석 기법에 대한 연구가 활발히 이루어지고 있다. 대표적인 대용량 데이터 분석 기법으로는 맵리듀스 환경에서 보로노이 다이어그램을 이용한 k 최근접점 조인(VkNN-join) 알고리즘이 존재한다. 데이터집합 R, S에 대해, VkNN-join 알고리즘은 부분집합 Ri에 연관된 부분집합 Sj만을 후보탐색 영역으로 선정하여 질의처리를 수행하기 때문에, 대용량 데이터에 대한 join 질의처리 시간을 감소시키는 장점이 존재한다. 그러나 VkNN-join은 보로노이 다이어그램을 사용하기 때문에, 색인 구축 비용이 높은 단점이 존재한다. 아울러 kNN 질의처리를 위한 후보 영역선정 시 k값에 비례하여 후보영역의 크기가 증가하기 때문에, kNN 연산 오버헤드가 증가하는 문제점이 존재한다. 이를 해결하기 위해 본 논문에서는 대용량 데이터 분석을 위한 맵리듀스 기반 kNN join 질의처리 알고리즘을 제안한다. 제안하는 질의처리 알고리즘은 시드 기반의 동적 분할을 통해 색인구조 구축비용을 절감한다. 또한 시드 간 평균 거리를 기반으로 질의 처리 후보 영역을 선정함으로써, kNN-join 질의를 위한 연산 오버헤드를 감소시킨다. 아울러, 성능 평가를 통해 제안하는 기법이 질의처리 시간 측면에서 기존 기법에 비해 우수함을 보인다.
