RISS 검색 - 국내학술지논문 상세보기

국문 초록 (Abstract)

최근 페이스북, 트위터 등의 SNS(Social Networking Service)가 발전함에 따라, 사용자가 생성하는 데이터가 급격히 증가하고 있다. 사용자 데이터는 민감한 개인정보를 포함하기 때문에, 원본 데이...

최근 페이스북, 트위터 등의 SNS(Social Networking Service)가 발전함에 따라, 사용자가 생성하는 데이터가 급격히 증가하고 있다. 사용자 데이터는 민감한 개인정보를 포함하기 때문에, 원본 데이터를 공격자로부터 보호하기 위해서는 데이터를 암호화하는 것이 필요하다. 따라서 암호화된 데이터의 복호화 없이 질의를 처리하는 암호화 질의 처리 기법이 제안되었다. 그러나 기존의 질의처리 기법은 암호화 데이터에 대한 색인 구조를 구축하고 이를 순차적 으로 탐색하기 때문에, 데이터의 크기가 증가함에 따라 질의탐색 비용이 증가하는 문제점이 존재한다. 이를 위해, P.B.Volk, et al.은 prefix 트리 기반 병렬 질의처리 알고리즘을 제안하였다. 제안하는 알고리즘은 암호화된 데이 터를 위해 prefix 트리 구조를 구축하고, 트리를 부분 트리로 분할하여 생성된 모든 부분 트리를 병렬적으로 탐색한 다. 그러나 이 알고리즘은 모든 부분 트리를 탐색하기 때문에, 트리 깊이에 따라 연산 비용이 급격히 증가하는 문제 점이 존재한다. 아울러, 이 알고리즘은 범위 질의나 부분 매칭 등의 다양한 질의를 지원하지 못하는 문제점이 존재 한다. 이러한 문제를 해결하기 위해, 본 논문에서는 prefix 트리 및 해시 테이블을 사용하는 GPU 기반 병렬 질의처 리 알고리즘을 제안한다. 제안하는 알고리즘은 prefix 트리 loop-up 테이블을 사용하여 범위 질의 및 부분매칭 질 의를 지원한다. 아울러 제안하는 알고리즘이 기존 P.B.Volk, et al. 의 알고리즘보다 검색 시간 측면에서 약 30% 우수한 성능을 나타냄을 보인다.

목차 (Table of Contents)

요약
Abstract
1. 서론
2. 관련 연구
2.1 prefix tree

요약
Abstract
1. 서론
2. 관련 연구
2.1 prefix tree
2.2 GPU
2.3 GPU 기반 병렬 질의처리 기법
3. 빅데이터 상의 암호화 질의 처리를지원하는 Prefix 트리 기반의 GPU 병렬 질의처리 기법
3.1 기존 기법의 문제점
3.2 질의처리 성능 향상을 위한 GPU 할당 최적화지원 Prefix 트리 색인 구조
3.3 PLU 테이블 기반 질의 처리 알고리즘
4. 성능 평가
4.1 정확 매칭 질의 성능비교
4.2 범위 질의 성능비교
4.3 부분 매칭 질의 성능평가
4.4 성능 고찰
5. 결론
참고문헌

참고문헌 (Reference)

1 Martin Traverso, "“Presto: Interacting with petabytes of data at Facebook" Facebook

2 H. Wu, "Red Fox:An Execution Environment for Relational Query Processing on GPUs" 44-54, 2014

3 R. J. Barrientos, "Range query processing on single and multi GPU environments" 39 (39): 2656-2668, 2013

4 J. Kim, "Parallel multidimensional range query processing with R-trees on GPU" 73 (73): 1195-1207, 2013

5 M. L. Yiu, "Outsourcing of Private Spatial Data for Search Services" 1140-1143, 2009

6 P. B. Volk, "GPU-Based Speculative Query Processing for Database Operations" 51-60, 2010

7 N. K. Govindaraju, "Fast computation of Database Operations using Graphics Processors" 215-226, 2004

8 M. Boehm, "Efficient In-Memory Indexing with Generalized prefix-trees" 180 : 227-246, 2011

9 J. Manyika, "Big data:The next frontier for innovation, competition, and productivity" McKinsey Global Institute 2011

10 K. Wang, "Artificial Societies and GPU-Based Cloud Computing for Intelligent Transportation Management" 22-28, 2011