GPU에서 Contain-Link를 이용한 R-tree 구현

김민철(Mincheol Kim),유승범(Seungbum Yoo),최원익(Wonik Choi) 한국정보과학회 2014 정보과학회논문지 : 데이타베이스 Vol.41 No.2

1984년 R-tree가 제안된 이후 R-tree의 질의처리 성능을 높이고자 많은 노력들이 있었다. 하지만, 이러한 노력에도 불구하고 점점 빠르게 커져가는 빅데이타를 처리하기 위한 추가적인 질의처리 성능개선에 여전히 많은 관심이 집중되고 있다. 본 논문에서는 이러한 문제를 다루고자 CL-tree를 제안한다. 제안 기법은 범위질의 시에 질의영역과 노드의 엔트리들의 포함관계를 고려한다. CL-tree는 범위 질의 시엔트리들이 질의영역에 포함(contained)되어있다면 중간노드를 방문하지 않고 직접 단말레벨에 접근하기위해 contain-link라는 포인터를 이용한다. CL-tree의 설계 목표는 트리를 순회할 때 contain-link를 사용하여 불필요한 노드의 방문을 제거함으로써 오는 장점과 GPU의 병렬처리에서 오는 장점을 결합하는 것이다. 다양한 조건에서의 실험을 통해 CL-tree는 GPU에서의 선형검색에 비해 최대 3배, G-tree에 비해 1.3배 가량의 성능이 향상됨을 보인다. Since the R-tree was proposed in 1984, there have been numerous research efforts on R-tree variants for improving its query performance. Despite all of these efforts, there are still growing interests in further accelerating query performances with the big data that grows faster and bigger in size. To cope with this problem, we propose CL-tree(Contain-Link tree), a novel indexing method that takes into account the relationships between a query range and entries in a node during query processing. Specifically, CL-tree employs a special pointer called contain-link to directly access the leaf level without visiting intermediate nodes when nodes are contained within a given query. The rationale of CL-tree is to combine the benefits from avoiding unnecessary visits during tree traversal using the contain-links and the parallel processing power of GPU. Our extensive experiments show that CL-tree achieves query performance up to 3 times higher than that of a sequential scan in GPU and up to 1.3 times higher than that of a G-tree, respectively.

클라우드 컴퓨팅에서 프라이버시 보호를 지원하는 데이터 필터링 기반 병렬 영역 질의 처리 알고리즘

김형진 ( Hyeong Jin Kim ),장재우 ( Jae-woo Chang ) 한국정보처리학회 2021 정보처리학회논문지. 컴퓨터 및 통신시스템 Vol.10 No.9

Recently, with the development of cloud computing, interest in database outsourcing is increasing. However, when the database is outsourced, there is a problem in that the information of the data owner is exposed to internal and external attackers. Therefore, in this paper, we propose a parallel range query processing algorithm that supports privacy protection. The proposed algorithm uses the Paillier encryption system to support data protection, query protection, and access pattern protection. To reduce the operation cost of a checking protocol (SRO) for overlapping regions in the existing algorithm, the efficiency of the SRO protocol is improved through a garbled circuit. The proposed parallel range query processing algorithm is largely composed of two steps. It consists of a parallel kd-tree search step that searches the kd-tree in parallel and safely extracts the data of the leaf node including the query, and a parallel data search step through multiple threads for retrieving the data included in the query area. On the other hand, the proposed algorithm provides high query processing performance through parallelization of secure protocols and index search. We show that the performance of the proposed parallel range query processing algorithm increases in proportion to the number of threads and the proposed algorithm shows performance improvement by about 5 times compared with the existing algorithm.

Development of a CUBRID-Based Distributed Parallel Query Processing System

( Hyeong-il Kim ),( Hyeonsik Yang ),( Min Yoon ),( Jae-woo Chang ) 한국정보처리학회 2017 Journal of information processing systems Vol.13 No.3

Due to the rapid growth of the amount of data, research on bigdata processing has been highlighted. For bigdata processing, CUBRID Shard is able to support query processing in parallel way by dividing the database into a number of CUBRID servers. However, CUBRID Shard can answer a user`s query only when the query is required to gain accesses to a single CUBRID server, instead of multiple ones. To solve the problem, in this paper we propose a CUBRID based distributed parallel query processing system that can answer a user`s query in parallel and distributed manner. Finally, through the performance evaluation, we show that our proposed system provides 2-3 times better performance on query processing time than the existing CUBRID Shard.

Efficient Query Processing Platform for Uncertain Big Data

Zhenhua Huang,Jiawen Zhang,Qiang Fang 보안공학연구지원센터 2015 International Journal of Database Theory and Appli Vol.8 No.5

Query processing technology has recently received a lot of attention in the business intelligence and information service communities. However, the existing approaches can not efficiently optimize the query performance in the uncertain big data environment. In this paper, we propose QPPUBG, a novel and efficient query processing platform for uncertain big data. QPPUBG mainly includes four modules: (i) query equivalence reconstructing for uncertain big data; (ii) multiple query optimization over probability relation components; (iii) query execution plan constructing over probability relation components, and (iv) physical implementation solution of query for uncertain big data. Specially, QPPUBG can support the possible world instance semantics and efficiently handle arbitrary decision spaces. Moreover, QPPUBG can seamlessly integrate the above four modules into the modern parallel computation frameworks. We present the extensive experiments that demonstrate QPPUBG is both efficient and effective.

Development of a CUBRID-Based Distributed Parallel Query Processing System

Kim, Hyeong-Il,Yang, HyeonSik,Yoon, Min,Chang, Jae-Woo Korea Information Processing Society 2017 Journal of information processing systems Vol.13 No.3

Due to the rapid growth of the amount of data, research on bigdata processing has been highlighted. For bigdata processing, CUBRID Shard is able to support query processing in parallel way by dividing the database into a number of CUBRID servers. However, CUBRID Shard can answer a user's query only when the query is required to gain accesses to a single CUBRID server, instead of multiple ones. To solve the problem, in this paper we propose a CUBRID based distributed parallel query processing system that can answer a user's query in parallel and distributed manner. Finally, through the performance evaluation, we show that our proposed system provides 2-3 times better performance on query processing time than the existing CUBRID Shard.

Development of a CUBRID-Based Distributed Parallel Query Processing System

김형일,양현식,윤민,장재우 한국정보처리학회 2017 Journal of information processing systems Vol.13 No.3

Due to the rapid growth of the amount of data, research on bigdata processing has been highlighted. For bigdata processing, CUBRID Shard is able to support query processing in parallel way by dividing the database into a number of CUBRID servers. However, CUBRID Shard can answer a user’s query only when the query is required to gain accesses to a single CUBRID server, instead of multiple ones. To solve the problem, in this paper we propose a CUBRID based distributed parallel query processing system that can answer a user’s query in parallel and distributed manner. Finally, through the performance evaluation, we show that our proposed system provides 2–3 times better performance on query processing time than the existing CUBRID Shard.

A parallel query processing system based on graph-based database partitioning

Nam, Yoon-Min,Han, Donghyoung,Kim, Min-Soo Elsevier science 2019 Information sciences Vol.480 No.-

<P><B>Abstract</B></P> <P>As parallel database systems have large amounts of data to process, it is important to utilize a scalable and efficient horizontal database partitioning method. The existing partitioning methods have major drawbacks that not only cause large amounts of data redundancy but also still require expensive shuffle operations for join queries in many cases—despite their high data redundancy. We elucidate upon the drawbacks originating from the tree-based partitioning schemes and propose a novel graph-based database partitioning method called GPT that both improves the query performance and reduces data redundancy. We integrate the proposed GPT method into a parallel query processing system, Spark SQL, across all the relevant layers and modules, including the query plan generator and the scan operator. Through extensive experiments using three benchmarks, TPC-DS, IMDB and BioWarehouse, we show that GPT significantly outperforms the state-of-the-art method in terms of both storage overhead and query performance.</P>

Parallel Range Query Processing with R-tree on Multi-GPUs

류홍수(Hongsu Ryu),김민철(Mincheol Kim),최원익(Wonik Choi) Korean Institute of Information Scientists and Eng 2015 정보과학회논문지 Vol.42 No.4

암호화된 빅데이터 상에서 효율적인 질의 처리를 지원하는 Prefix 트리를 사용한 GPU 기반 병렬 질의처리 기법

신영성,이현조,장재우 한국차세대컴퓨팅학회 2014 한국차세대컴퓨팅학회 논문지 Vol.10 No.2

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

Supergraph Search 알고리즘 IDAR의 병렬화에 대한 실험 분석

이연준,민승환,박근수 한국정보과학회 2023 정보과학회 컴퓨팅의 실제 논문지 Vol.29 No.6

그래프 분석에서 핵심적인 문제 중 하나는 Supergraph search 문제이다. Supergraph search 문제는 다수의 데이터 그래프들과 한 개의 쿼리 그래프에 대하여 쿼리 그래프에 임베딩(embedding)이 있는 데이터 그래프들을 찾는 문제이다. 이 문제를 해결하는 최신 알고리즘인 IDAR에서는 방향성 비사이클 그래프(IDAG)와 그래프 사이의 동적 계획법(IDAG-Graph DP) 그리고 active-first search를 통해 문제를 효율적으로 해결하였다. 본 논문에서는 IDAR에서 제안한 Supergraph search 중 query processing 과정을 병렬화를 통해 성능을 개선하였다. 또한, 병렬화를 위한 새로운 자료 구조를 도입하였고, 실제 데이터 그래프를 통해 실험을 진행하여서 성능을 측정하고 결과를 분석하였다.