디지털 라이브러리[ 검색결과 ]
공간 키워드 유사도 기반의 부분적 집단 공간 키워드 질의처리 기법
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의 수가 늘어남에 따라 수행 시간이 급격하게 증가한다. 따라서 이러한 문제를 해결하기 위해 전체적인 탐색 공간을 줄이는 키워드 기반 탐색 기법을 제안한다. 또한 키워드의 부분집합을 계산하는 시간을 줄이기 위해 선형 탐색에 기반한 단말노드 가지치기 기법과 근사 알고리즘 기법 및 임계값에 기반한 가지치기 기법들을 제안한다.
도로 교통망 환경에서 G-트리 구조를 이용한 단일 그룹 콜렉티브 여행 질의 처리
http://doi.org/10.5626/JOK.2020.47.5.513
본 연구에서는, 위치 기반의 승차 공유 서비스에서 전체 여행비용을 최소화 하는 단일 그룹 콜렉티브 여행 질의 처리를 다루려고 한다. 단일 그룹 콜렉티브 여행 질의는 여러 명의 사용자들이 특정 지점에 모여서 하나의 운송 수단을 이용하여 도착 지점으로 이동을 할 때, 이 때 소요되는 전체 비용을 최소화 하는 지점을 찾는 것이 목표이다. 콜렉티브 여행 질의와 관련된 연구들이 많이 진행이 되었지만 특정 상황에서만 효과적인 성능을 보인다는 문제점을 가지고 있다. 따라서 우리는 단일 그룹 콜렉티브 여행질의의 기초 해결 방안을 소개하고 해당 방안보다 더 나은 성능을 보이는 G-트리 기반의 효과적인 가지치기 기법을 제시한다. 추가로, 기존에 연구되었던 방법들의 한계를 밝히고, 제시하는 기법이 기존 연구들이 갖는 한계에 영향을 받지 않고 최적 결과를 구할 수 있음을 실험을 통해 보인다.
GPGPU를 이용한 Hilbert R-tree 벌크로딩 고속화 기법
R tree는 공간 데이터베이스 분야에서 가장 널리 쓰이는 색인 구조이며 다양한 변형된 기법들이 제안되었다. 이 기법들 중 Hilbert R tree는 공간 채움 곡선인 Hilbert 곡선을 이용해서 대용량의 데이터를 고비용의 분할 과정 없이 R tree를 구성하는 기법이다. 하지만 기존의 CPU기반의 Hilbert R tree는 대용량의 데이터를 처리할 때는 순차적인 접근으로 발생되는 고비용의 전처리 비용과 느린 구축시간으로 실제 응용에 적용되기에는 한계가 있다. 본 논문에서는 이러한 문제를 해결하기 위해 GPU를 이용해서 데이터의 Hilbert 매핑을 병렬화 하고 이를 통해서 최종적으로 GPU의 메모리에 Hilbert R tree의 벌크로딩을 고속화하는 기법을 제안한다. GPU기반의 Hilbert R tree는 inversed cell 기법과 트리구조 패킹의 병렬화 기법을 통해서 벌크로딩의 성능을 향상시켰다. 실험 결과에서는 기존의 CPU 기반의 벌크로딩에 비해 최대 45배의 성능향상을 보여주었다.
