[우수논문] 데이터베이스 아웃소싱 환경에서 암호화된 데이터의 질의 결과 무결성 검증 기법

장미영(Miyoung Jang),장재우(Jae-Woo Chang) 한국정보과학회 2014 한국정보과학회 학술발표논문집 Vol.2014 No.6

맵리듀스를 이용한 그리드 기반 인덱스 생성 및 k-NN 조인 질의 처리 알고리즘

장미영(Miyoung Jang),장재우(Jae Woo Chang) 한국정보과학회 2015 정보과학회논문지 Vol.42 No.11

맵리듀스는 대용량 데이터 처리를 위한 시스템 안정성과 유용성을 제공한다. 맵리듀스 기반 k-최근접점 조인 질의처리 알고리즘은 두 데이터 집합 R과 S를 기반으로 R의 모든 레코드에 대해 S의 데이터 중 가장 인접한 k개의 레코드를 탐색하는 알고리즘으로써, 대용량 데이터 분석을 위한 중요한 질의 처리 알고리즘이다. 그러나 기존 k-최근접점 조인 질의처리 알고리즘은 높은 인덱스 구축비용 문제로 인해 대용량 데이터 처리에 적합하지 않은 문제점을 지닌다. 따라서, 본 논문에서는 그리드 기반 인덱스 생성 및 k-최근접점 질의 처리 알고리즘을 제안한다. 제안하는 기법은 질의 셀로부터 인접한 데이터만을 찾아 맵리듀스 테스크에 전송함으로써 데이터 전송 및 k-최근접점 연산 오버헤드를 줄인다. 성능평가를 통해, 제안하는 기법이 정확 매칭 질의를 제공하는 동시에 기존 기법에 비해 질의 처리 시간 측면에서 최대 7배의 성능을 개선함을 보인다. MapReduce provides high levels of system scalability and fault tolerance for large-size data processing. A MapReduce-based k-nearest-neighbor(k-NN) join algorithm seeks to produce the k nearest-neighbors of each point of a dataset from another dataset. The algorithm has been considered important in bigdata analysis. However, the existing k-NN join query-processing algorithm suffers from a high index-construction cost that makes it unsuitable for the processing of bigdata. To solve the corresponding problems, we propose a new grid-based, k-NN join query-processing algorithm. Our algorithm retrieves only the neighboring data from a query cell and sends them to each MapReduce task, making it possible to improve the overhead data transmission and computation. Our performance analysis shows that our algorithm outperforms the existing scheme by up to seven-fold in terms of the query-processing time, while also achieving high extent of query-result accuracy.

위치 기반 서비스에서 정보 보호를 지원하는 그리드 기반 근사 k-최근접점 질의 처리 알고리즘

장미영(Miyoung Jang),장재우(Jaewoo Chang) 한국정보과학회 2011 정보과학회논문지 : 정보통신 Vol.38 No.6

최근 무선 통신 기술의 발달 및 위치 측정 장치 사용의 증가로 위치 기반 서비스가 폭넓게 발전하고 있다. 그러나 현재 위치 기반 서비스는 질의 요청자가 자신의 정확한 위치 정보를 질의 처리 서버에 전송하기 때문에, 사용자의 개인 정보가 노출될 수 있는 취약성을 지닌다. 따라서 LBS 환경에서 사용자의 위치 정보 보호 기법이 꾸준히 연구되어왔다. 대표적인 기법으로는 사용자의 위치 좌표를 질의 영역으로 확장하여 질의를 처리하는 Cloaking 영역 기반 질의 처리 기법과 질의 요청자가 전송한 인덱스를 기반으로 한 수학적 연산을 통해 질의를 수행하고, 사용자의 위치 정보 및 질의에 대한 정보를 얻지 않고도 결과를 탐색하고 반환하는 PIR 기반 질의 처리 기법이 존재한다. 그러나 기존의 연구들은 높은 통신비용 및 질의 처리 시간을 요구한다. 따라서 본 논문에서는 기존 연구의 장점을 융합한 그리드 기반 근사 k-최 근접점 질의 처리 알고리즘을 제안한다. 첫째, 근사 k-최근접점 질의 처리를 위해 POI 밀집도 기반 영역 확장 기법을 제안하고 둘째, 정확도 높은 질의 결과 탐색을 위한 영역 중첩 인덱스 기법을 제안한다. 마지막으로, 성능평가를 통해 제안하는 기법이 기존 연구에 비해 우수함을 보인다. Location-Based Services (LBSs) are becoming popular due to the advances in mobile networks and positioning capabilities. When a user sends a query with his exact location to the LBS server, the server processes the query and returns a result to the user. Providing user’s exact location to the LBS server may lead revealing his private information to unauthorized parties (e.g., adversaries). Therefore, there exist two main methods to overcome this problem. They are cloaking method which blurs a user’s location into a cloaking region and Private Information Retrieval (PIR) based methods which encrypt location data by using PIR protocol. However, they suffer from high computation and communication overheads. To resolve these problems, we, in this paper, propose a hybrid scheme to process an approximate k-Nearest Neighbor (k-NN) query by combining above two methods. Through performance analysis, we have shown that our grid-based k-NN query processing algorithm outperforms the existing work in terms of both query processing time and accuracy of the result set.

데이터베이스 아웃소싱 환경에서 순서 보존 암호화 기법을 이용한 질의 결과 무결성 검증 기법

장미영(Miyoung Jang),장재우(Jae Woo Chang) 한국정보과학회 2015 정보과학회논문지 Vol.42 No.1

최근 데이터베이스 아웃소싱(Outsourcing) 환경에서 데이터 보호를 위한 암호화 기법 및 질의결과 검증 기법에 대한 관심이 고조되고 있다. 그러나 기존 아웃소싱 데이터 암호화 기법들은 원본 데이터베이스 도메인 정보를 알고 있는 공격자에 의한 순서 매칭 공격 및 카운팅 공격에 취약한 문제점을 지닌다. 기존 질의 결과 무결성 검증 기법은 질의 결과 검증 데이터 전송 오버헤드 문제를 지닌다. 따라서, 본 논문에서는 데이터 보호를 위한 그룹 순서 보존 암호화 인덱스 및 이를 기반으로 한 질의 결과 무결성검증 기법을 제안한다. 제안하는 기법은 순서 보존 암호화 인덱스를 통해 데이터를 암호화 하고, 복호화없이 질의를 수행한다. 또한, 힐버트 커브를 통해 그룹 정보를 은닉함으로써, 질의 수행 과정에서 데이터그룹 정보가 유출되는 것을 방지한다. 마지막으로, 주기함수 기반 그룹 분할 및 그룹 기반 인증을 통해 질의 결과 무결성 검증을 위한 데이터 크기를 감소시킨다. 성능평가를 통해, 제안하는 기법이 기존 버킷 기반 인증 기법에 비해 질의 처리 시간 측면에서 평균 1.6배, 검증 데이터 오버헤드 측면에서 최대 20배의 성능을 개선함을 보인다. Recently, research on database encryption for data protection and query result authentication methods has been performed more actively in the database outsourcing environment. Existing database encryption schemes are vulnerable to order matching and counting attack of intruders who have background knowledge of the original database domain. Existing query result integrity auditing methods suffer from the transmission overhead of verification object. To resolve these problems, we propose a group-order preserving encryption index and a query result authentication method based on the encryption index. Our group-order preserving encryption index groups the original data for data encryption and support query processing without data decryption. We generate group ids by using the Hilbert-curve so that we can protect the group information while processing a query. Finally, our periodic function based data grouping and query result authentication scheme can reduce the data size of the query result verification. Through performance evaluation, we show that our method achieves better performance than an existing bucket-based verification scheme, it is 1.6 times faster in terms of query processing time and produces verification data that is 20 times smaller.

다중매체텍스트를 활용한 글쓰기 지도방법 연구

장미영 ( Miyoung Jang ) 시학과 언어학회 2015 시학과 언어학 Vol.31 No.-

본 연구는 대학생 학습자의 쓰기 지도를 위해 제공되어야 할 매체텍스트 중 전략적으로 내용 생성을 극대화 하고, 사고력을 향상시킬 수 있는 다중매체텍스트 활용방안을 모색하는 것을 목적으로 한다. 대학생들이 대학에서 학습하는 글쓰기 갈래와 주제는 다양하다. 글쓰기 수업 중 학습자가 느끼는 어려움은 글쓰기에 관한 이론의 부족이나 형식을 이해하지 못한 경우 각 형식에 맞는 글쓰기 절차와 서술방법을 실습하는 가운데 원리를 터득할 수 있다. 그러나 내용 생성하기의 경우 주어진 텍스트 분석과 주제에 대한 이해는 물론 본문의 내용 생성 어려움을 호소하는 경우가 많다. 수업 중 제시되는 주제나 갈래에 맞는 글쓰기를 효과적으로 수행하기 위해서는 학생이 알고 있는 배경지식과 다양한 관점의 정보가 추가되어야 한다.본 연구는 글쓰기 교육에서 다중매체텍스트를 활용할 경우 유효한 정보와 다양한 관점의 지식을 학습자에게 제공할 수 있고, 직접적으로 내용생성 뿐만 아니라 학습자가 타당한 판단을 내리는데 도움이 된다는 전제에서 출발하였다. 수업과정에서 교수,학습 매체의 활용은 학습자에게 글쓰기에 대한 흥미를 고양하고, 교수자의 교육 목표를 직접적으로 전달 할 수 있는 효과적인 교수법 중 하나이다. 그러므로 다중매체텍스트의 활용은 텍스트 사이의 상호텍스트성을 통해 주제를 좀 더 폭넓고 깊이 있게 이해할 수 있는 토대를 제공하게 된다. 한 가지 주제에 대한 다양한 텍스트의 제공은 지식, 정보전달의 목적을 넘어 교수자와 학습자, 학습자와 학습자, 학습자와 매체 사이에서 빈번히 이루어지는 의사소통과정을 포함하게 된다. 학습자는 수업의 객체가 아닌 주체로서 능동적으로 참여하게 되고 교수자와 학습자 사이의 상호작용은 타인을 이해하고 공감하는 경험을 제공하게 된다.다중매체텍스트를 활용한 글쓰기 교육은 글쓰기 수업 시간은 물론 대학생이 느끼는글쓰기 관련 문제점을 개선하고 학습자의 사회에 대한 이해의 폭과 깊이를 확대할 것으로 기대한다. The purpose of this study is to examine intertextuality model,which maximizes textual resources and activates ability of thinking,as an instruction for college students to write texts. Whereas college students have been offered variable writing subjects and theories,they have problems in creating texts. It is necessary for students to be provided new knowledge in order to connect prior knowledge on a topic. In this study, intertextuality is introduced as an approach which is beneficial to provide students with useful information and knowledge as well as allow students to construct text. In the class,the effects of teaching-learning media is various, and also method and scope of utilization is being used differently according to objection. In this regard, intertextuality is not only provides knowledge and information but also binds instructors with learners,learners with media and among learners as a process of communication. It helps learners to engage in writing class as an agent, interact with instructors which influences the way learners perceive the world around them.As a result, it is expected that intertextuality approach in writing both improves problems in writing class and offers learners an opportunity to broaden understanding in the community.

맵리듀스를 이용한 효율적인 k-NN 조인 질의처리 알고리즘

윤들녁 ( Deulnyeok Yun ),장미영 ( Miyoung Jang ),장재우 ( Jaewoo Chang ) 한국정보처리학회 2014 한국정보처리학회 학술대회논문집 Vol.21 No.2

대용량 데이터를 분석하기 위한 맵리듀스 기반 k-NN 조인 질의처리 알고리즘은 최근 데이터 마이닝 및 분석을 기반으로 하는 응용 분야에서 매우 중요하게 활용되고 있다. 그러나,대표적인 연구인 보로노이 기반 k-NN 조인 질의처리 알고리즘은 보로노이 인덱스 구축 비용이 매우 크기 때문에 대용량 데이터에 적합하지 못하다. 아울러 보로노이 셀 정보를 저장하기 위해 사용하는 R-트리는 맵리듀스 환경의 분산 병렬 처리에 적합하지 않다. 따라서,본 논문에서는 새로운 그리드 인덱스 기반의 k-NN 조인질의 처리 알고리즘을 제안한다. 첫째,높은 인덱스 구축 비용 문제를 해결하기 위해,데이터 분포를 고려한 동적 그리드 인덱스 생성 기법을 제안한다. 둘째,맵리듀스 환경에서 효율적으로 k-NN 조인 질의를 수행하기 위해,인접셀 정보를 시그니처로 활용하는 후보영역 탐색 및 필터링 알고리즘을 제안한다. 마지막으로 성능 평가를 통해 제안하는 기법이 질의 처리 시간 측면에서 기존 기법에 비해 최대 3배 높은 질의 처리 성능을 나타냄을 보인다.

암호화 데이터를 위한 힐버트 커브 기반 다차원 색인 키 생성 및 질의처리 알고리즘

김태훈(Taehoon Kim),장미영(Miyoung Jang),장재우(Jae-Woo Chang) 한국멀티미디어학회 2014 멀티미디어학회논문지 Vol.17 No.10

데이터베이스 아웃소싱 환경에서 암호화된 데이터를 위한 힐버트 커브 기반 질의 결과 무결성 검증 기법

윤들녁 ( Youn Deulnyeok ),장미영 ( Miyoung Jang ),장재우 ( Jae-woo Chang ) 한국정보처리학회 2013 한국정보처리학회 학술대회논문집 Vol.20 No.2

최근 클라우드 컴퓨팅에 대한 관심이 고조됨에 따라, 이를 활용한 데이터베이스 아웃소싱(Outsourcing)에 대한 연구가 활발히 진행되고 있다. 그러나 아웃소싱 된 데이터베이스는 사용자 개인 정보, 증권, 또는 의료 정보 등 민감한 정보를 포함하기 때문에 서비스 제공자로부터 수행한 질의 결과 데이터가 데이터 소유자로부터 생성된 데이터이며, 정확한 질의 결과를 포함하는지 확인하기 위한 질의 결과 무결성 검증 기법의 필요성이 대두되었다. 기존 질의 결과 무결성 검증 기법은 질의 결과에 포함되는 무결성 검증 데이터의 크기가 증가하여 검증 데이터 전송 오버헤드 증가 및 데이터 노출 위험 증가 문제를 지닌다. 따라서, 본 논문에서는 데이터 보호를 지원하는 암호화 데이터 기반 질의 결과 무결성 검증 기법을 제안한다. 제안하는 질의 결과 무결성 검증 기법은 암호화된 데이터 그룹을 주기 함수를 이용하여 재분할하고, 최종 데이터 그룹 id를 힐버트 커브를 통해 변환한다. 따라서, 검증 데이터 오버헤드를 감소시켜 효율적인 질의 처리를 지원하며, 그룹 id 변경을 통해 검증 데이터 유출 위험을 방지한다. 성능평가를 통해, 제안하는 기법이 기존 기법에 비해 질의 처리 시간 측면에서 평균 2배, 검증 데이터 오버헤드 측면에서 최대 20배의 성능을 개선함을 보인다.

분산 컴퓨팅 환경에서 효율적인 유사 조인 질의 처리를 위한 행렬 기반 필터링 및 부하 분산 알고리즘

양현식(Hyeon-Sik Yang),장미영(Miyoung Jang),장재우(Jae-Woo Chang) 한국콘텐츠학회 2016 한국콘텐츠학회논문지 Vol.16 No.7

하둡 맵리듀스와 같은 분산 컴퓨팅 플랫폼이 개발됨에 따라, 기존 단일 컴퓨터 상에서 수행되는 질의 처리 기법을 분산 컴퓨팅 환경에서 효율적으로 수행하는 것이 필요하다. 특히, 주어진 두 데이터 집합에서 유사도가 높은 모든 데이터 쌍을 탐색하는 유사 조인 질의를 분산 컴퓨팅 환경에서 수행하려는 연구가 있어 왔다. 그러나 분산 병렬 환경에서의 기존 유사 조인 질의처리 기법은 데이터 전송 비용만을 고려하기 때문에 클러스터 간에 비균등 연산 부하 분산의 문제점이 존재한다. 본 논문에서는 분산 컴퓨팅 환경에서 효율적인 유사 조인 처리를 위한 행렬 기반 부하 분산 알고리즘을 제안한다. 제안하는 알고리즘은 클러스터의 균등 부하 분산을 위해 행렬을 이용하여 예상되는 연산 부하를 측정하고 이에 따라 파티션을 생성한다. 아울러, 클러스터에서 질의 처리에 사용되지 않는 데이터를 필터링함으로서 연산 부하를 감소시킨다. 마지막으로 성능 평가를 통해 제안하는 알고리즘이 기존 기법에 비해 질의 처리 성능 측면에서 우수함을 보인다. As distributed computing platforms like Hadoop MapReduce have been developed, it is necessary to perform the conventional query processing techniques, which have been executed in a single computing machine, in distributed computing environments efficiently. Especially, studies on similarity join query processing in distributed computing environments have been done where similarity join means retrieving all data pairs with high similarity between given two data sets. But the existing similarity join query processing schemes for distributed computing environments have a problem of skewed computing load balance between clusters because they consider only the data transmission cost. In this paper, we propose Matrix-based Load-balancing Algorithm for efficient similarity join query processing in distributed computing environment. In order to uniform load balancing of clusters, the proposed algorithm estimates expected computing cost by using matrix and generates partitions based on the estimated cost. In addition, it can reduce computing loads by filtering out data which are not used in query processing in clusters. Finally, it is shown from our performance evaluation that the proposed algorithm is better on query processing performance than the existing one.

흉부 단순촬영 영상을 이용한 척추측만증 조기 진단 모델 개발

이승아(Seung-Ah Lee),최선(Seon Choe),장미영(Miyoung Jang),이동규(Dongkyu Lee),양수진(Sujin Yang),이선호(Sun-Ho Lee),최현수(Hyun-soo Choi),이준구(June-Goo Lee) 한국정보과학회 2022 한국정보과학회 학술발표논문집 Vol.2022 No.06