공간 연속질의 처리에서 영역 기반의 저장 구조를 이용한 효율적인 디스크 접근 방법

정원일(Chung, Weon-Il) 한국산학기술학회 2011 한국산학기술학회논문지 Vol.12 No.5

유비쿼터스 응용은 실시간으로 입력되는 데이터 스트림과 저장된 공간 데이터를 동시에 처리하는 이중적인 공간 연속 질의 처리 기술이 요구된다. 이러한 공간 연속 질의 처리에서는 대용량 공간 데이터에 대한 디스크 접근 비용을 최소화가 요구되나 기존 공간색인 기법은 논리적 인접성을 공간 데이터의 물리적인 인접성을 보장할 수 없으 므로 공간 데이터 탐색에 있어 비용이 증가한다. 또한 데이터 인접성 보장을 위한 공간 순서화 기법의 경우에도 빈번 하게 접근되는 질의 공간 영역에 대한 클러스터링을 고려하지 않고 있다. 본 논문에서는 이중적인 공간 연속질의 처 리에서 공간 데이터의 효율적인 접근을 위한 영역 기반 저장 구조를 제안한다. 제안 기법에서는 영역을 기반으로 데 이터를 인접하게 저장하고 사용자 질의를 영역 기반으로 그룹 처리함으로써 질의 처리 비용을 감소시킬 수 있다. Ubiquitous applications require hybrid continuous query processing which processes both on-line data stream and spatial data in the disk. In the hybrid continuous spatial query processing, disk access costs for the high-volume spatial data should be minimized. However, previous indexing methods cannot reduce the disk seek time, because it is difficult that the data are stored in contiguity with others. Also, existing methods for the space-filling curve considering data cluster have the problem which does not cluster available data for queries. Therefore, we propose the region storage structure for efficient data access in hybrid continues spatial query processing. This paper shows that there is an obvious improvement of query processing costs through the contiguous data storing method and the group processing for user queries based on the region storage structure.

분산 공간 데이터 스트림 처리에서 질의 영역의 겹침을 고려한 공간 연산 배치 기법

정원일(Chung, Weon-Il) 한국산학기술학회 2012 한국산학기술학회논문지 Vol.13 No.6

위치를 기반으로 하는 서비스가 다양해짐에 따라 고가용성과 고확장성을 제공하기 위한 분산 데이터 스트림 처리 기법에 대한 연구가 널리 수행되고 있다. 기존 연구는 분산된 노드들에서 부하의 균형을 유지하기 위해 공간 데 이터 스트림의 지리적인 특성을 고려하지 않고 있어 공간적으로 인접한 연산을 수행함에 있어 전체 시스템의 부하를 증가시키고 있다. 본 논문에서는 분산 환경의 공간 데이터 스트림을 처리하기 위해 공간 영역의 겹침을 고려한 연산 배치 기법을 제안한다. 제안 기법에서는 인접한 공간 영역을 대상으로 하는 연산을 효율적으로 분리하기 위해 질의 영역이 겹치는 부분의 연산을 우선적으로 동일 노드에 분배하여 중복 영역에 대한 공유의 최대화를 보장한다. According to increasing of various location-based services, distributed data stream processing techniques have been widely studied to provide high scalability and availability. In previous researches, in order to balance the load of distributed nodes, the geographic characteristics of spatial data stream are not considered. For this reason, distributed operations for adjacent spatial regions increases the overall system load. We propose a operation allocation scheme considering the characteristics of spatial operations to effectively processing spatial data stream in distributed computing environments. The proposed method presents the efficient share maximizing approach that preferentially distributes spatial operations sharing the common query regions to the same node in order to separate the adjacent spatial operations on overlapped regions.

분산 공간 데이터 스트림 시스템에서 연산 처리율 기반의 적응적 업스트림 백업 기법

정원일(Chung, Weon-Il) 한국산학기술학회 2013 한국산학기술학회논문지 Vol.14 No.10

분산 공간 데이터 스트림 처리에서는 분산 노드의 활용도를 높이고 고장이 발생한 경우 신속하게 시스템을 복구하기 위해 하위 노드에서 처리된 튜플에 대해 상위 노드로 데이터를 백업한다. 그러나 데이터의 유입량이 증가하 고 노드의 연산 결과를 다수의 하위 노드들과 공유할 때 튜플 처리가 지연되면 상위 노드의 삭제 지연으로 인해 백 업 데이터의 손실을 야기할 수 있다. 본 논문에서는 노드들의 데이터 유입량과 하위 노드의 연산 처리율을 분석하고 적응적 업스트림 백업 방법을 적용하여 노드의 평균 부하율을 감소시키고, 노드 연산 결과의 공유에 따른 데이터 손 실을 최소화하는 방법을 제안한다. 그리고 실험에서는 제안 기법을 통해 데이터 손실을 방지하고, 노드 모니터링에 소요되는 CPU 사용률을 평균 20% 감소시키는 결과를 나타낸다. In distributed spatial data stream processing, processed tuples of downstream nodes are replicated to the upstream node in order to increase the utilization of distributed nodes and to recover the whole system for the case of system failure. However, while the data input rate increases and multiple downstream nodes share the operation result of the upstream node, the data which stores to output queues as a backup can be lost since the deletion operation delay may be occurred by the delay of the tuple processing of upstream node. In this paper, the adaptive upstream backup scheme based on operation throughput in distributed spatial data stream system is proposed. This method can cut down the average load rate of nodes by efficient spatial operation migration as it processes spatial temporal data stream, and it can minimize the data loss by fluid change of backup mode. The experiments show the proposed approach can prevent data loss and can decrease, on average, 20% of CPU utilization by node monitoring.

유비쿼터스 응용 서비스를 위한 공간 데이터 스트림 처리 플랫폼

정원일(Chung, Weon-Il),김환구(Kim, Hwan-Koo) 한국산학기술학회 2010 한국산학기술학회논문지 Vol.11 No.3

지리정보를 기반으로 하는 센서들은 첨단 정보통신 인프라 구축을 통해 종합적인 정보기술 서비스를 제공하 는 미래형 신도시 개발 프로젝트인 u-City 사업 등과 같은 유비쿼터스 환경에서의 응용 서비스를 실현하기 위한 핵심 기술로 대두되고 있다. 이러한 센서들은 지리적으로 광역의 분산된 형태로 설치 운영되므로 센서로부터 수집되는 데 이터들은 대량의 실시간 연속 데이터로 구성된다. 이에 본 연구에서는 다양한 u-GIS 서비스의 효율적인 구축을 위해 지리정보를 갖는 센서들로부터 실시간으로 입력되는 대량의 공간 데이터 스트림을 효과적으로 처리할 수 있는 플랫 폼을 제안한다. 또한, 제안 공간 데이터 스트림 처리 플랫폼을 이용하여 미아방지서비스 구축하여 제안 기술이 유비 쿼터스 응용 서비스 구축에 효과적으로 활용될 수 있음을 보인다. Sensors related to the geographic information are gathering strength as core technologies for various ubiquitous services like u-City project for the new town of the future to provide total information services by the high IT infrastructure. These sensors generate the very large real-time streaming data because these are set up and controlled with wide areas of the geographical distribution. On this, we propose an efficient spatial data stream processing system to support various u-GIS services based on geographic sensors.

공간 데이터 스트림 질의 정확도 향상을 위한 다단계 부하제한 기법

정원일(Chung, Weon-Il) 한국산학기술학회 2015 한국산학기술학회논문지 Vol.16 No.12

공간 데이터 스트림 관리 시스템에 실시간으로 입력되는 공간 데이터 스트림은 제한된 주기억장치의 용량을 초과할 수 있으므로 부하를 제한할 필요가 있다. 그러나 기존의 연구에서는 부하 제한을 위해 공간 데이터 스트림을 생성하는 데이 터 소스의 특성이나 입력 변화, 그리고 공간 데이터 이용 정도를 효율적으로 적용하지 못함으로써 질의 처리의 정확도와 성능을 감소시키는 문제를 갖고 있다. 이에 본 연구에서는 공간 데이터 스트림 질의 관리 시스템에서 발생할 수 있는 부하를 제한하고 공간 질의 처리의 성능과 정확도를 높이기 위한 다단계 부하제한 기법을 제안한다. 제안 기법에서는 먼저 데이터를 수집하는 단계에서 데이터의 수량과 입력 빈도 변화를 이용하여 부하를 제한하고, 과부하 발생시 공간 이용도에 따라 질의 참여 확률이 낮은 데이터를 대상으로 추가적인 부하제한을 수행한다. 실험 결과에서 제안 기법은 기존 부하제한 기법에 비해 11% 이상의 부하 제한 발생 빈도를 감소시키면서 입력 데이터 스트림의 증가와 질의 영역에 증가에 따른 질의 처리 결과의 정확도는 0.04% 이상의 우위를 보였다. 또한, 질의 처리 성능에서도 기존 기법에 비해 3% 이상의 향상을 나타냈다. In spatial data stream management systems, it is needed appropriate load shedding algorithm because real-time input spatial data streams could exceed the limitation of main memory. However previous researches, lack regard for input ratio and spatial utilization rates of spatial data streams, or the characteristics of data source which generates data streams with spatial information efficiently, can lead to decrease the performance and accuracy of spatial data stream query. Therefore, multi-level load shedding scheme for spatial data stream management systems is proposed to increase the spatial query performance and accuracy. This proposed scheme limits overloads in relation to the input rate and the characteristics of data source first, and then, if needed, query data representing low query participation probability based on spatial utilizations are dropped relatively. Our experiments show that the proposed method could decrease load shedding frequency for previous researches by more than 11% despite query results accuracy and query performance are superior at 0.04% and 3%.

공간 데이터스트림의 입력 빈도와 데이터 밀집도 기반의 동적 부하제한 기법

정원일(Chung, Weon-Il) 한국산학기술학회 2015 한국산학기술학회논문지 Vol.16 No.3

u-GIS 환경에서는 실시간으로 유입되는 공간 데이터 스트림으로 인해 발생되는 부하를 제한하기 위한 연구가 계속 되고 있다. 그러나 기존의 비공간 데이터 기반의 부하 제한 기법은 공간 데이터의 특성을 고려하지 않아 공간 질의 처리의 정확도를 감소시킨다. 또한, 공간 데이터 기반의 부하 제한 기법도 공간 데이터 스트림의 입력 빈도 변화와 공간 데이터의 밀집도를 반영하지 않아 질의 처리 정확도와 질의 처리 성능이 저하되는 문제가 존재한다. 이에 본 논문에서는 u-GIS 환경에 서 부하 발생 빈도를 최소화하고 연속 질의 처리 성능과 정확도를 향상시키기 위해 공간 데이터의 밀집도와 공간데이터스트 림의 입력 변화량을 이용하여 동적으로 부하를 제한하는 기법을 제안한다. 제안 기법에서는 부하제한 요구시 공간 이용도에 따라 질의에 참여할 확률이 낮은 데이터를 샘플링함으로써 연속 질의 처리 결과의 정확도와 질의 처리 속도를 향상시킬 수 있다. In u-GIS environments, various load shedding techniques have been researched in order to balance loads caused by input spatial data streams. However, typical load shedding methods on aspatial data lack regard for characteristics of spatial data, also previous load shedding approaches on spatial, which still lack regard for spatial data density or dynamic input data stream, give rise to troubles on spatial query processing performance and accuracy. Therefore, dynamic load shedding scheme over spatial data stream is proposed through stored spatial data deviation and load ratio of input data stream in order to improve spatial continuous query accuracy and performance in u-GIS environment. In proposed scheme, input data which are a big probability related to spatial continuous query may be a strong chance to be dropped relatively.

시공간 데이터 스트림 처리를 위한 영역 기반의 연산자 공유 기법

정원일(Chung, Weon-Il),김영기(Kim, Young-Ki) 한국산학기술학회 2010 한국산학기술학회논문지 Vol.11 No.12

유비쿼터스 환경에서 다양한 센서로부터 생성되는 데이터 스트림에 대해 사용자가 요구하는 위치 기반 서비 스를 효과적으로 지원하기 위해 연산자 네트워크와 공유 등을 통한 연속 질의 처리 기법이 활용되고 있다. 위치 정보 기반의 연속 질의 처리는 특정 영역을 중심으로 유사 질의가 집중적으로 발생할 수 있으므로, 본 논문에서는 유사한 조건을 갖는 공간 연산을 공유하기 위해 그리드 영역 분할을 이용한 공간 연산 공유 기법을 제안한다. 제안기법은 공 간 연산을 직접 공유하지 않고 그리드 셀 별로 이동객체를 공유하기 때문에 유사한 조건을 갖는 공간 연산의 공유가 가능하여 공간 연산의 실행 빈도수를 크게 감소시켜 질의 처리 속도의 향상과 함께 메모리 이용률을 향상시킨다. In ubiquitous environments, many continuous query processing techniques make use of operator network and sharing methods on continuous data stream generated from various sensors. Since similar continuous queries with the location information intensively occur in specific regions, we suggest a new operator sharing method based on grid partition for the spatial continuous query processing for location-based applications. Due to the proposed method shares moving objects by the given grid cell without sharing spatial operators individually, our approach can not only share spatial operators including similar conditions, but also increase the query processing performance and the utilization of memory by reducing the frequency of use of spatial operators.

스마트폰에서 보행자 길안내 서비스를 위한 관심지점 기반 도로 네트워크 모델링 연구

정원일(Chung, Weon-Il),김상기(Kim, Sang-Ki) 한국산학기술학회 2011 한국산학기술학회논문지 Vol.12 No.1

최근 GPS 기능을 내장한 스마트폰의 보급이 확대됨에 따라 위치를 기반으로 하는 다양한 응용 서비스들이 제공되고 있다. 기존의 보행자 길안내 서비스는 차량 길안내 서비스를 확장하여 경로 질의를 처리하고 있으나, 인도 에 대한 적절한 경로 안내가 어려울 뿐 아니라 차량을 위한 도로 네트워크 저장구조는 관심지점 위주의 경로 질의 처리에 문제를 야기한다. 또한, 저장 장치의 입출력 빈도수를 증가시켜 스마트 폰의 전력 소모를 가중시키게 된다. 본 논문에서는 보행자 경로의 정확한 표현을 위해 보행자 도로 네트워크 모델을 정의하고 저장 장치의 입출력 빈도 수를 줄이기 위한 관심지점 기반 보행자 도로 네트워크 저장 구조를 제안한다. 제안 기법은 보행자 도로의 특성과 요구사항에 따른 관심지점 기반의 정확한 경로 탐색을 지원한다. 또한, 관심지점을 고려한 데이터 구조를 제공하여 경로 탐색 질의 처리 비용을 감소시켜 스마트폰의 전력 소모를 줄일 수 있다. Recently, the wide spread popularity of smart phones causes the advent of various mobile applications base on the location information. Since previous pedestrian navigations are applied by extending car navigations, these are not only difficult to provide the appropriate route information, but also raise limitations in the efficient query processing by data structures of car road networks. In addition, these increase the power consumption caused by the growth of I/O frequency. In this paper, we propose a pedestrian road network model for the accurate route information and a storage structure for the pedestrian road network based on POI to reduce the I/O frequency. The proposed method enables efficient route searches over POI reflecting the characteristics and requirements of pedestrian roads. Also, a reduction of query processing costs for the route searching by a data structure considered with POI can save the power consumption more than previous approaches.

반도체 공정의 생산성 향상을 위한 실시간 대용량 데이터의 효율적인 저장 기법

정원일(Chung, Weon-Il),김환구(Kim, Hwan-Koo) 한국산학기술학회 2009 한국산학기술학회논문지 Vol.10 No.11

반도체 산업이 발전함에 따라 생산 효율을 높이기 위해 무인 자동 생산 공정이 요구되고 있다. 이러한 무인 자동화 생산 관리 시스템은 생산성 향상을 위해 생산 공정에서 발생하는 대량의 실시간 데이터 분석 및 관리를 필요 로 한다. 따라서 실시간으로 발생하는 대용량 데이터를 저장하기 위한 저장 관리 시스템이 요구된다. 기존의 저장 관 리 시스템으로 오라클, MY-SQL, MS-SQL 등의 디스크 기반 DBMS가 있다. 하지만 기존의 디스크 기반 DBMS는 반 도체 장비로부터 실시간으로 발생하는 대용량 데이터 처리에 한계가 있다. 본 논문에서는 대용량 데이터를 저비용으 로 실시간 저장하기 위해 블록 단위 삽입 트랜잭션을 이용한 압축-합병 저장 기법을 제안한다. 제안 기법은 블록 단 위 트랜잭션을 이용하여 실시간 데이터를 빠르게 저장하며 데이터를 압축하고 압축된 데이터를 합병하여 저장하기 때문에 보다 적은 디스크 공간을 사용하여 저장할 수 있다. 따라서 반도체 공정에서 빠르게 발생하는 대용량 데이터 를 기존 DBMS보다 빠르게 저장이 가능하고 저장 공간 비용을 감소시킨다. Automatic semiconductor manufacturing systems are demanded to improve the efficiency of the semiconductor production process. These systems include the functionalities such as the analysis and management schemes for very large real-time data in order to enhance the productivities. So, it requires the efficient storage management system to store very large real-time data. Traditional database management systems(e.g. Oracle, MY-SQL, MS-SQL) are based on disk. However, previous DBMS's have the limitation on the low storing performance. In this paper, we propose a compress-merge storing method of very large real-time data using insert transaction of a block unit. The proposed method shows better processing performances compare to conventional DBMS's. Also compress-merge method makes it possible that it can store large real-time data on low storage cost. Therefore, the proposed method can be applied to an efficient storage management system in the semiconductor production process.

공간 슬라이딩 윈도우 집계질의의 정확도 향상을 위한 그리드 해쉬 기반의 부하제한 기법

백성하,이동욱,김경배,정원일,배해영,Baek, Sung-Ha,Lee, Dong-Wook,Kim, Gyoung-Bae,Chung, Weon-Il,Bae, Hae-Young 대한공간정보학회 2009 한국공간정보시스템학회 논문지 Vol.11 No.2

데이터 스트림은 다양한 입력속도로 끊임없이 입력되고 데이터 스트림을 저장하는 메모리상의 저장공간은 유한하기 때문에 때때로 저장공간을 초과하는 데이터가 입력되는 경우가 발생한다. 이 문제를 해결하기 위해 초과되는 데이터의 일부를 버려 메모리 초과를 방지하는 부하제한 기법이 연구되었다. 기존의 부하제한 기법은 데이터의 편차에 따른 최적의 샘플링 비율을 갖는 랜덤 샘플링을 사용한다. 그러나 이 기법은 공간적 특성을 고려하지 않기 때문에 공간 질의에 사용되는 데이터와 사용되지 않는 데이터를 구분하지 않고 샘플링 한다. 그래서 공간 질의가 포함되는 u-GIS 환경에서는 질의 정확도가 감소하는 문제가 발생하였다. 본 논문에서는 공간 질의와 비공간 질의가 동시에 발생하는 u-GIS 환경에서 질의 정확도를 보다 향상 시키는 부하제한 기법을 연구하였다. 이 기법은 동시에 실행되는 공간 질의의 공간적 이용도에 따라 차등적으로 샘플링을 하여, 질의에 이용될 확률이 낮은 데이터를 샘플링을 한다. 제안된 부하제한 기법은 공간질의가 존재하는 경우 질의 정확도를 크게 향상 시켰고, 샘플링 중 공간 필터링 연산을 적용하여 질의처리 속도도 일부 향상 시켰다. As data stream is entered into system continuously and the memory space is limited, the data exceeding the memory size cannot be processed. In order to solve the problem, load shedding methods which drop a part of data to prevent exceeding the storage space have been researched. Generally, a traditional load shedding method uses random sampling with optimized rate according to data deviation. The method samples data not to distinguish those used in spatial query because the method uses only a random sampling with optimized rate according to data deviation. Therefore, the accuracy of query was reduced in u-GIS environment including spatial query. In this paper, we researched a new load shedding method improving accuracy of the query in u-GIS environment which runs spatial query and aspatial query simultaneously. The method uses a new sampling method that samples data having low probability used in query. Therefore proposed method improves spatial query accuracy and query processing speed as applying spatial filtering operation to sampling operator.