데이터 중심 저장 환경에서 소실 데이터 보정 기법을 이용한 인-네트워크 병합 질의 처리

박준호(Jun Ho Park),이효준(Hyo Joon Lee),성동욱(Dong Ook Seong),유재수(Jae Soo Yoo) 한국정보과학회 2010 정보과학회논문지 : 데이타베이스 Vol.37 No.6

센서 네트워크에서 발생하는 데이터를 저장하고, 효율적으로 질의를 처리하는 기법에 대한 많은 연구가 이루어지고 있다. 대표적인 연구로 데이터 중심 저장 기법이 있다. 데이터 중심 저장 기법의 경우 질의를 효과적으로 처리하기 위해 수집한 데이터 값에 따라 저장 될 센서 노드를 지정하고, 질의 처리를 위해 질의에 해당하는 데이터를 저장하는 노드에서만 데이터를 수집한다. 하지만 노드의 결함이 발생하면 결함 노드에 저장 되어 있는 전체 데이터가 소실 됨에 따라 질의 결과 정확도가 저하 되는 문제점이 발생한다. 이러한 문제를 해결하기 위해, 본 논문에서는 데이터 중심 저장 기법에서 노드 결함에 따른 데이터 소실이 발생하여도 높은 정확도를 보이는 인-네트워크 병합 질의 처리 기법을 제안한다. 데이터 소실이 발생 하였을 경우 선형 회귀 분석 기법을 이용하여 소실 된 영역에 해당하는 보정 모델을 생성하고, 이를 통해 가상의 데이터를 포함한 질의 결과를 반환한다. 제안하는 기법의 우수성을 보이기 위해 시뮬레이션을 통해 소실 데이터 보정 기법을 적용한 KDDCS(E-KDDCS) 기법과 기존의 데이터 중심 저장 기법과 성능을 비교하였다. 그 결과 기존 기법에 비해 질의 결과 정확도가 향상되었고, 질의 처리 시 에너지 소모를 감소시켰다. In Wireless Sensor Networks (WSNs), various Data-Centric Storages (DCS) schemes have been proposed to store the collected data and to efficiently process a query. A DCS scheme assigns distributed data regions to sensor nodes and stores the collected data to the sensor which is responsible for the data region to process the query efficiently. However, since the whole data stored in a node will be lost when a fault of the node occurs, the accuracy of the query processing becomes low. In this paper, we propose an in-network aggregation query processing method that assures the high accuracy of query result in the case of data loss due to the faults of the nodes in the DCS scheme. When a data loss occurs, the proposed method creates a compensation model for an area of data loss using the linear regression technique and returns the result of the query including the virtual data. It guarantees the query result with high accuracy in spite of the faults of the nodes. To show the superiority of our proposed method, we compare E-KDDCS (KDDCS with the proposed method) with existing DCS schemes without the data-loss correction method. In the result, our proposed method increases accuracy and reduces query processing costs over the existing schemes.

위치 기반 서비스에서 정보 보호를 지원하는 그리드 기반 근사 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.

그리드 인덱스 기반 뷰 선택 기법을 이용한 효율적인 Top-k 질의처리 알고리즘

홍승태(Seungtae Hong),윤들녁(Deulnyeok Youn),장재우(Jae Woo Chang) 한국정보과학회 2015 정보과학회 컴퓨팅의 실제 논문지 Vol.21 No.1

최근 대용량 데이터의 분석을 위한 top-k 질의처리 알고리즘에 대한 관심이 고조되고 있다. 그러나 기존 top-k 질의처리 알고리즘은 효율적인 인덱스 구조를 제공하지 않기 때문에, 높은 탐색 비용을 야기하며, 아울러 다양한 질의 유형을 지원하지 못하는 문제점이 존재한다. 이러한 문제점을 해결하기 위해, 본 논문에서는 그리드 인덱스 기반 뷰 선택 기법을 이용한 top-k 질의처리 알고리즘을 제안한다. 제안하는 기법은 그리드 인덱스 기반의 뷰 선택 기법을 통해 주어진 질의 영역에 대하여 최소한의 그리드 셀만을 탐색함으로써 질의처리 시간을 감소시킨다. 마지막으로, 성능 평가를 통해 제안하는 top-k 질의처리 알고리즘이 기존 알고리즘에 비해 질의처리 시간 및 질의 결과 정확도 측면에서 우수함을 나타낸다. Research on top-k query processing algorithms for analyzing big data have been spotlighted recently. However, because existing top-k query processing algorithms do not provide an efficient index structure, they incur high query processing costs and cannot support various types of queries. To solve these problems, we propose a top-k query processing algorithm using a view selection method based on a grid index. The proposed algorithm reduces the query processing time by retrieving the minimum number of grid cells for the query range, by using a grid index-based view selection method. Finally, we show from our performance analysis that the proposed scheme outperforms an existing scheme, in terms of both query processing time and query result accuracy.

데이터 중심 저장 환경에서 높은 정확도를 갖는 소실 데이터 보정 기법

박준호,유석종,성동욱,유재수 한국정보과학회 2011 데이타베이스 연구 Vol.27 No.1

In wireless sensor networks (WSNs), various data‐centric storage (DCS) schemes have been proposed to store the collected data and to efficiently process a query. The DCS scheme assigns divided data regions to sensor nodes and stores the collected data to the sensor which is responsible for the data region to process the query efficiently. However, since the whole data stored in a node will be lost when the fault of a node occurs, the accuracy of the query processing becomes low. To solve such a problem, we propose a new data correction method for high accuracy in DCS schemes with faults. The proposed method assures the high accuracy of the query result in the case of data losses due to the faults of the nodes in the DCS scheme. When a data loss occurs, the proposed method generates a compensation model against the area of the data loss data distribution patterns and data variation rate of the data. It returns the query results including virtual data by using the compensation model. Therefore, it guarantees the query result with high accuracy in spite of the faults of the nodes. To show the superiority of our proposed method, we compare the proposed method with the conventional data‐loss correction method. In the result, the proposed method shows about 19% accuracy rates on average in the various data sets. 최근 무선 센서 네트워크 환경에서 감지되는 데이터를 네트워크상에 효과적으로 저장하고 처리하기 위한 다양한 기법들이 제안되었다. 대표적인 연구로 데이터중심 저장 기법이 있다. 데이터 중심 저장 기법의 경우 질의 처리에는 효과적이지만, 노드의 결함이 발생하면 결함 노드에 저장 되어 있는 전체 데이터가 소실 됨에따라 질의 결과 정확도가 저하 되는 문제점이 발생한다. 최근 이와 같은 데이터 소실 문제를 해결하기 위해 선형 회귀 분석 기법을 기반으로 보정 모델을 생성하는E‐KDDCS가 제안되었다. 하지만 E‐KDDCS의 경우, 선형 회귀 분석 기법을 이용하여 데이터의 분포 패턴이나 변화율을 고려하지 않는 단순한 보정 모델을 생성하기 때문에, 결과적으로 낮은 정확도의 질의 결과를 보인다. 본 논문에서 데이터중심 저장 기법에서의 정확도 높은 소실 데이터 보정 기법을 제안한다. 제안하는 기법은 데이터 존재 영역의 데이터의 분포 패턴 및 변화율을 고려하여 보정 모델을 생성함으로써, 기존의 기법에 비해 높은 정확도를 가지는 가상 데이터를생성하는 것이 가능하다. 제안하는 기법의 우수성을 보이기 위해 시뮬레이션을통해 기존의 소실 데이터 보정(EKDDCS) 기법과 제안하는 기법과의 성능을 비교하였다. 그 결과 기존 기법에 비해 평균 19% 이상의 질의 결과 정확도의 향상을 보였다.

A Multi-Layer Grid Method for Processing Skyline Queries in Distributed Environments

이하(He Li),장수민(Su Min Jang),유재수(Jae Soo Yoo) 한국정보과학회 2011 정보과학회논문지 : 데이타베이스 Vol.38 No.1

스카이라인 질의는 데이터베이스 시스템에서 다중 선호도 분석과 의사 결정을 위한 매우 중요한 연산자로서 주목을 받고 있다. 기존 연구의 대부분은 중앙집중식 데이터집합에 대한 스카이라인 질의들을 처리하는 것에 초점이 맞추어져있다. 하지만, 실제 응용프로그램들의 관련 데이터들은 실질적으로 여러개의 서버들에 분산되어있다. 분산 환경에서 스카이라인 질의 처리는 연결된 서버들부터 많은 데이터를 수집해야 한다. 기존의 분산 환경에서 스카이라인 질의 처리기법들은 두 가지 문제점을 가지고 있다: i) 기존 기법들이 스카이라인 질의에 대한 느린 처리 속도를 갖는다. ii) 네트워크상에서 서버들 간에 전송되는 데이터의 대부분이 불필요한 데이터이다. 본 논문에서는 분산 환경에서 스카이라인 질의를 효율적으로 처리하기 위한 다층 그리드 기법을 제안한다. 제안하는 기법은 다층 그리드 메커니즘을 이용해서 서버들 간에 불필요한 데이터전송을 최소화시킨다. 다양한 데이터들에 이용한 성능평가들은 제안한 기법이 기존 기법들보다 우수함을 보여준다. The skyline query has been received much attention as an important operator in database systems for multi-preference analysis and decision making. Most of the previous works have focused on processing skyline queries on centralized data sets. However, the related data of real applications are practically scattered at several different servers. The skyline query computation in distributed environments is needed to gather a large number of data from the connected servers. The existing methods for a skyline query in distributed environments have two problems: (i) They have slow processing time for a skyline query. (ii) Most of the transferred data among servers in the network are unnecessary. In this paper, we propose a multi-layer grid method for efficiently processing skyline queries in distributed environments (MGSD). The proposed method minimizes the unnecessary transferred data using the grid-mechanism. Experiments based on various data sets show that our proposed method outperforms the existing methods.

계층적 캐시 기법을 이용한 대용량 웹 검색 질의 처리 시스템의 구현

임성채(Lim Sung Chae) 한국정보과학회 2008 정보과학회 컴퓨팅의 실제 논문지 Vol.14 No.7

웹을 이용한 정보 공개 및 검색이 확대됨에 따라 웹 검색 엔진도 지속적인 주목을 받고 있다. 이에 따라 웹 검색 엔진의 다양한 기술적 문제를 해결하고자 하는 연구가 있었음에도 웹 검색 엔진의 질의 처리 시스템에 대한 기술적 내용은 잘 다뤄지지 않았다. 질의 처리 시스템의 경우 소프트웨어 아키텍처나 운영 기법을 고안하기 어렵기 때문에 본 논문에서는 구현된 상용 시스템을 바탕으로 관련 기술을 소개하고자 한다. 구현된 질의 처리 시스템은 6,500 만개 웹 문서를 색인하여 일 500만개 이상의 사용자 질의 요청을 수행하는 큰 규모의 시스템이다. 구현한 시스템은 질의 처리 결과를 재사용하기 위해 계층적 캐시 기법을 적용했으며, 저장된 캐시 데이타는 4계층으로 구성된 데이타 저장소에 분산 저장되는 것이 특징이다. 계층적 캐시 기법을 통해 질의 처리 용량을 400% 정도로 향상 시킬 수 있었으며 이를 통해 서버 구축 비용을 70% 정도 절감할 수 있었다. With the increasing demands of information sharing and searches via the web, the web search engine has drawn much attention. Although many researches have been done to solve technical challenges to build the web search engine, the issue regarding its query processing system is rarely dealt with. Since the software architecture and operational schemes of the query processing system are hard to elaborate, we here present related techniques implemented on a commercial system. The implemented system is a very large-scale system that can process 5-million user queries per day by using index files built on about 65-million web pages. We implement a multi-level cache scheme to save already returned query results for performance considerations, and the multi-level cache is managed in 4-level cache storage areas. Using the multi-level cache, we can improve the system throughput by a factor of 4, thereby reducing around 70% of the server cost.

공간 데이터베이스 아웃소싱을 위한 비트맵 암호화 기법 및 GPU 기반 질의처리 알고리즘

윤민(Min Yoon),조아라(Ahra Cho),장재우(Jae-woo Chang) 한국정보과학회 2014 정보과학회논문지 : 데이타베이스 Vol.41 No.2

최근 클라우드 컴퓨팅이 빠르게 발전함에 따라, 공간 데이터베이스 아웃소싱에 대한 관심이 급증하고 있다. 따라서 공간 데이터베이스 아웃소싱에서 위치 데이터 보호를 위한 암호화 기법이 연구되고 있다. 그러나 기존 공간 좌표 변환 기법인 FDH는 위치 데이터의 분포를 고려하지 않고 암호화를 수행하기 때문에, 공격자가 암호화 변환 데이터로부터 원본 데이터 분포를 유추하는 것이 가능하다. 아울러, 트리기반 인덱스를 통해 질의 처리를 수행하기 때문에, 데이터의 양이 많아질수록 질의 처리 성능이 저하되는 문제점이 존재한다. 이를 위해, 본 논문에서는 공간 데이터베이스 아웃소싱에서 위치 데이터 보호를 위한 비트맵 기반 데이터 암호화 기법 및 질의처리 알고리즘을 제안한다. 제안하는 기법에서는 공격자의 원본 데이터 유추 방지를 위해 데이터 분포를 고려한 영역 분할/병합 정책을 이용한 앵커 선정 알고리즘을 사용한다. 아울러, 최적의 질의 처리 성능을 보장하기 위해, GPU를 통한 질의 처리를 수행한다. 한편, 성능 평가를 통해 제안하는 기법이 공격자로의 원본 데이터베이스 노출 확률을 감소시키면서, 빠른 질의 처리를 수행함을 검증한다. With the development of cloud computing, the interest on spatial database outsourcing has been increasing. Therefore, researches for protecting location data privacy in spatial outsourced databases have been actively performed. However, FDH (Flexible Distance-Based Hashing) is easy to access original data because they do not consider data distribution. In addition, since they perform the nearest neighbor query processing by using tree-based indexs, query processing time can be increased depending on tree depth. To solve these problems, we propose a bitmap encryption scheme and a query processing algorithm for spatial database outsourcing. We propose an anchor selection algorithm using a split-and-merge policy based on data distribution to protect privacy of users from attackers. Furthermore, we reduce the communication cost for query processing by performing searching based on GPU. Finally, we show through performance analysis that the proposed scheme shows better query processing performance and guarantees the privacy of users, compared with the existing scheme.

대용량 이동객체의 위치정보 관리를 위한 S-GRID를 이용한 분산 그리드 기법

김영창,김영진,장재우,Kim, Young-Chang,Kim, Young-Jin,Chang, Jae-Woo 한국공간정보시스템학회 2008 한국공간정보시스템학회 논문지 Vol.10 No.4

Recently, advances in mobile devices and wireless communication technologies require research on various location-based services. As a result, many studies on processing k-nearest neighbor query, which is most im portant one in location-based services, have been done. Most of existing studies use pre-computation technique to improve retrieval performance by computing network distance between POIs and nodes beforehand in spatial networks. However, they have a drawback that they can not deal with effectively the update of POIs to be searched. In this paper, we propose a distributed grid scheme using S-GRID to overcome the disadvantage of the existing work as well as to manage the location information of a large number of moving objects in efficient way. In addition, we describe a k-nearest neighbor(k-NN) query processing algorithm for the proposed distributed grid scheme. Finally, we show the efficiency of our distributed grid scheme by making a performance comparison between the k-NN query processing algorithm of our scheme and that of S-GRID. 최근 모바일 기기 및 무선 통신의 발달로 인하여 다양한 위치 기반 서비스에 대한 연구가 증대되고 있으며, 이러한 위치 기반 서비스의 대표적 질의인 k-최근접 질의를 효율적으로 처리하기 위한 연구가 활발히 수행되어 왔다. 기존 연구들은 질의 처리 성능의 향상을 위해, 공간 네트워크 상의 POI와 노드 사이의 거리를 미리 계산하는 pre-computation 기법을 사용한다. 그러나 이러한 pre-computation 기법들은 검색 대상이 되는 POI의 변경을 효과적으로 처리하지 못하는 단점을 갖는다. 본 논문에서는 기존 pre-computation 기법들의 단점을 극복하고, 대용량 이동객체의 위치정보를 효율적으로 관리하기 위하여 S-GRID를 이용한 분산 그리드 기법을 제안한다. 아울러 제안하는 분산 그리드 기법을 위한 k-최근접 질의 처리 알고리즘을 제시한다. 마지막으로, S-GRID 및 분산 그리드 기법의 k-최근접 질의처리 알고리즘의 성능 평가를 통해, 제안하는 기법의 우수성을 입증한다.

도로 네트워크에서 사용자 정보 보호를 지원하는 질의영역에 대한 k-최근접 질의 처리 알고리즘

김형일(Hyeongil Kim),유혜겸(Hyekyeom Yoo),장재우(Jaewoo Chang) 한국정보과학회 2012 정보과학회논문지 : 데이타베이스 Vol.39 No.1

최근 무선 통신 기술의 발달 및 모바일 기기의 발달로 인하여 위치 기반 서비스가 주목을 받고 있다. 그러나 사용자의 정확한 위치정보를 통해 위치 기반 서비스 서버에 질의를 요청하는 것은 심각한 개인 정보 누출의 위협이 될 수 있기 때문에, 사용자 정보 보호를 위해 도로 네트워크를 고려하여 질의영역을 생성하는 연구가 활발히 진행되어 왔다. 따라서 질의영역에 대한 효율적인 질의 처리 방법이 요구된다. 이를 위해, 본 논문에서는 도로 네트워크에서 사용자 정보 보호를 지원하는 질의영역에 대한 k-최근접 질의 처리 알고리즘을 제안한다. 제안하는 기법은 POI(Point Of Interest)를 효율적으로 검색하기 위하여 Island 인덱스를 사용한다. 또한, 본 논문은 질의 처리 성능을 향상시키기 위해 적응적 Island 인덱스를 생성하는 방법을 제안한다. 마지막으로, 성능평가를 통해 제안하는 기법이 기존 기법들에 비해 네트워크 확장 비용 및 서비스 시간 측면에서 우수함을 보인다. Recent development in wireless communication technologies and mobile equipments are making location-based services (LBSs) popular. However, since requesting queries to LBS servers by using users' exact locations could make the privacy of the users in danger, many researches have been studied on generating query region for the user privacy protection, specially in road networks. Therefore, an efficient query processing mechanism for the query region is required. In this paper, we propose a k-nearest neighbor query processing algorithm for a query region supporting user privacy protection in road networks. The proposed scheme uses the Island index to efficiently retrieve POIs. This paper also proposes the method that generate the Adaptive Island index which could improve the performance of the query processing. Finally, we show from our performance analysis that our query processing schemes outperform the existing schemes in terms of network expansion cost and service time.

무선 센서 네트워크를 위한 상황 인지 데이터 중심 저장 기법

김현주,이충희,박준호,성동욱,유재수 한국정보과학회 2011 데이타베이스 연구 Vol.27 No.2

In wireless sensor networks, various data‐centric storage schemes (DCS) are one of representative researches to efficiently store sensor readings and to process a query. The DCS scheme assigns distributed data regions to sensor nodes and stores sensor readings to the sensor node which is responsible for the data region to process the query efficiently. However, the existing DCS schemes have some drawbacks that the sensor nodes have the fixed ranges to store sensor readings. Because the ranges of sensor readings change periodically in real world applications, they have problems that they use storage space unevenly in entire sensors and their network lifetimes are reduced. To solve such a problem, we propose a context aware data‐centric storage scheme to store sensor readings equally in the entire sensor network. To show the superiority of our proposed scheme, we compare it with the existing DCS schemes. Our experimental results show that our proposed scheme improves about 377.7% lifetime over the existing schemes on average. 센서 네트워크에서 데이터 중심 저장 기법은 측정값을 효율적으로 저장하고 질의를 처리하기 위한 대표적인 연구 중 하나이다. 데이터 중심 저장 기법의 경우 질의를 효과적으로 처리하기 위해 수집한 데이터 값에 따라 저장 될 센서 노드를 지정하고, 질의 처리를 위해 질의에 해당하는 데이터를 저장하는 노드에서만 데이터를수집한다. 하지만 기존에 제안된 DCS 기법들은 데이터의 저장 범위를 고정적으로 설정한다. 그러므로 시기별로 상이한 범위의 데이터가 발생되는 실제 응용에서는 저장 공간 활용의 불균등을 초래하여 네트워크 수명을 단축시킨다. 이러한 문제를 해결하기 위해, 본 논문에서는 시간이 지남에 따라 변화 하는 데이터 발생 패턴에상황 적응적인 범위 설정 기법을 적용하여 네트워크 전반에 걸쳐 노드들의 저장 공간을 균등하게 사용하는 상황 인지 데이터 중심 저장 방식을 제안한다. 제안하는 기법의 우수성을 보이기 위해 시뮬레이션을 통해 기존 DCS기법과 성능을 비교평가 하였다. 그 결과, 제안하는 기법은 기존 기법에 비해 네트워크 수명이 평균377.7% 증가하였다.