수치지도를 위한 피처 기반 공간자료 관리 시스템 설계

지정희,김승관,류근호,김명준,Chi, Jeong-Hee,Kim, Seung-Kwan,Ryu, Keun-Ho,Kim, Myung-Jun 한국공간정보시스템학회 2005 한국공간정보시스템학회 논문지 Vol.7 No.3

각종 공간자료는 지리정보시스템을 통해 공간과 관련된 의사결정에 활용된다. 공간자료는 데이터양이 방대하고 제작 및 갱신에 많은 비용과 시간이 소요되어 별도의 공간자료 관리시스템을 이용하여 유지하고 관리해야 한다. 기존의 수치지도를 위한 공간자료 관리시스템은 공간자료를 도엽(Tile)이라는 일정한 단위로 구분하여 관리하였다. 그러나 도엽기반 공간 정보 관리시스템은 구현은 용이하나, 도엽 내에 포함된 지형지물을 직접 공간자료로 저장하거나 관리할 수 없는 문제점을 가지고 있다. 따라서 이 논문에서는 지형지물 단위로 공간사료를 저장하고, 관리하며 변동 사항에 대한 신속한 수정이 가능한 수치지도를 위한 피처기반 공간자료 관리시스템을 제시한다. 제시되는 피처기반 공간자료 관리시스템은 피처 단위의 데이터 구축, 관리, 제공 및 갱신 기능을 지원하며, 기존 도엽기반 공간자료 관리시스템에서 지원하지 못했던 단일 원점좌표 전환, UFID 생성, 지형지물 통합, 지형지물 분할 및 메타데이터 입력을 가능하게 하였다. 제시된 수치지도를 위한 피처기반 공간자료 관리시스템은 공간자료의 유지, 관리를 용이하게 할 수 있으며 가공과 활용에 있어서도 효율성을 높일 수 있다. Various spatial data are utilized, through geographic information system, for the process to make a decision related to space. Generally, spatial data is large in quantity and it costs high and takes quite a long time for producing and maintaining it. An existing spatial data management system, tile-based one, for digital map manages spatial data being separated by a uniform data unit called tile. These systems can be implemented easily but have many problems such as they can directly store and manage feature included in tile. Therefore, in this paper, we suggest a feature-based spatial data management system for digital map. The proposed system is able to store and manage spatial data in the unit of feature directly. Hence this system is able to immediately update any change in the data and to supply users with the updated data without any delay. The proposed system can not only support a function of data input, management, supplying and update but also support unity origin coordinate conversion, UFID creation, feature unifying, feature dividing and metadata input which is not supported by the existing tile-based system. The proposed system can easily manage spatial data and can increase efficiency in processing and application.

일반화된 누적밀도 히스토그램을 이용한 공간 선택율 추정

지정희,김상호,류근호,Chi, Jeong-Hee,Kim, Sang-Ho,Ryu, Keun-Ho 한국정보처리학회 2004 정보처리학회논문지D Vol.11 No.4

Multiple-count problem is occurred when rectangle objects span across several buckets. The CD histogram is a technique which selves this problem by keeping four sub-histograms corresponding to the four points of rectangle. Although It provides exact results with constant response time, there is still a considerable issue. Since it is based on a query window which aligns with a given grid, a number of errors nay be occurred when it is applied to real applications. In this paper, we propose selectivity estimation techniques using the generalized cumulative density histogram based on two probabilistic models : \circled1 probabilistic model which considers the query window area ratio, \circled2 probabilistic model which considers intersection area between a given grid and objects. Our method has the capability of eliminating an impact of the restriction on query window which the existing cumulative density histogram has. We experimented with real datasets to evaluate the proposed methods. Experimental results show that the proposed technique is superior to the existing selectivity estimation techniques. Furthermore, selectivity estimation technique based on probabilistic model considering the intersection area is very accurate(less than 5% errors) at 20% query window. The proposed techniques can be used to accurately quantify the selectivity of the spatial range query on rectangle objects. 누적밀도 히스토그램은 사각형 객체의 네 점에 대응하는 4개의 서브 히스토그램을 유지함으로써 사각형 객체가 여러 버켓에 걸쳐질 경우 발생하는 다중 계산 문제를 해결하고 있다. 이 기법은 빠른 추정시간과 정확한 결과를 제공하고 있지만, 질의 윈도우가 그리드 셀의 경계와 일치해야 한다는 제약사항을 기반으로 수행하므로, 실제 응용에 적용시 많은 에러를 초래하게 된다. 따라서, 이 논문에서는 기존 누적밀도 히스토그램에서 질의 윈도우의 제약사항에 관한 영향을 줄이기 위해, 두가지 확률모델을 기반으로 일반화된 누적밀도 히스토그램을 사용한 선택율 추정 기법을 제안하였다. 제안된 두가지 확률 모델은 \circled1질의 영역 비율을 고려한 확률모델과, \circled2교차 영역 정보를 고려한 확률모델이다. 우리는 실제 데이터 셋을 사용하여 제안된 기법을 실험하였다 실험 결과는 이 논문에서 제안된 기법이 기존의 다른 선택율 추정 기법보다 성능이 뛰어남을 보여주고 있다 더구나, 교차 영역 정보를 기반으로 하는 확률모델의 경우 20% 질의 윈도우에서 5% 미만의 낮은 에러율을 보였다. 이 논문에서 제안된 기법은 사각형 객체의 공간 범위 질의의 선택율을 정확하게 추정하는데 사용될 수 있다.

압축된 공간 히스토그램을 이용한 선택율 추정 기법

지정희,이진열,김상호,류근호,Chi, Jeong-Hee,Lee, Jin-Yul,Kim, Sang-Ho,Ryu, Keun-Ho 한국정보처리학회 2004 정보처리학회논문지D Vol.11 No.2

공간 질의에 대한 선택율 추정은 가장 효율적인 실행 계획을 찾는데 이용되는 매우 중요한 과정이다. 공간 도메인이 큰 경우, 기존 연구의 요약정보는 상대적으로 적은 정보로 선택율을 추정하기 때문에 좋은 선택율을 유지하기 어렵다. 따라서, 이 논문에서는 작은 저장공간에 공간요약정보를 압축하는 새로운 기법인 MW 히스토그램을 제안한다. 이 히스토그램은 MinSkew 분할 알고리즘과 웨이블릿 변환이 결합되어 적은 저장공간에서도 타당한 선택율과 압축효과를 얻을 수 있고, 동적 갱신에 대해 효율적으로 대처할 수 있는 구조를 가진다. 실험 결과를 통하여, 버켓 수가 0.3M/6인 MW 히스토그램이 5%-20% 질의에서 평균적으로 좋은 성능을 보이고 있어, MW 히스토그램이 적은 저장공간에서 더 좋은 선택율을 얻을 수 있음을 확인시켜주었다. Selectivity estimation for spatial query is very important process used in finding the most efficient execution plan. Many works have been performed to estimate accurate selectivity. Although they deal with some problems such as false-count, multi-count, they can not get such effects in little memory space. Therefore, we propose a new technique called MW Histogram which is able to compress summary data and get reasonable results and has a flexible structure to react dynamic update. Our method is based on two techniques : (a) MinSkew partitioning algorithm which deal with skewed spatial datasets efficiently (b) Wavelet transformation which compression effect is proven. The experimental results showed that the MW Histogram which the buckets and wavelet coefficients ratio is 0.3 is lower relative error than MinSkew Histogram about 5%-20% queries, demonstrates that MW histogram gets a good selectivity in little memory.

이동객체의 궤적에 대한 연속 최근접 질의 처리

지정희(Jeong Hee Chi),최보윤(Bo Yoon Choi),김상호(Sang Ho Kim),류근호(Keun Ho Ryu) 한국정보과학회 2004 정보과학회논문지 : 데이타베이스 Vol.31 No.5

Recently, as growing of interest for LBS(location-based services) techniques, lots of works on moving objects that continuously change their information over time, have been performed briskly. Also, researches for NN(nearest neighbor) query which has often been used in LBS, are progressed variously. However, the results of conventional NN query processing techniques may be invalidated as the query and data objects move. Therefore, they are usually meaningless in moving object management system such as LBS. To solve these problems, in this paper we propose a new nearest neighbor query processing technique, called CTNN, which is possible to meet accurate and continuous query processing for moving objects. Our techniques include an Approximate CTNN(ACTNN) technique, which has quick response time, and an Exact CTNN(ECTNN) technique, which makes it possible to search nearest neighbor objects accurately. In order to evaluate the proposed techniques, we experimented with various datasets. Experimental results showed that the ECTNN technique has high accuracy, but has a little low performnce for response time. Also the ACTNN techinque has low accuracy comparing with the ECTNN, but has quick response time. The proposed techniques can be applied to navigation system, traffic control system, distribution information system, etc., and specially are most suitable when both data and query are moving objects and when we already know their trajectory. 최근 위치 기반 서비스 기술에 관한 관심이 증가하면서, 시간에 따라 연속적으로 변하는 이동 객체에 관한 많은 연구들이 활발하게 수행되고 있다. 또한 이 시스템들이 자주 사용되는 질의 처리 기법 중 하나인 최근접(nearest neighbor, NN) 질의에 대한 연구도 다양하게 수행되고 있다. 그러나, 기존의 최근접 질의 처리 기법들은 질의와 객체가 이동하면 그들이 결과가 유효하지 않게 되므로, LBS를 위한 이동객체 관리 시스템에는 적합하지 않을 수 있다. 이러한 문제들을 해결하기 위해서 이동객체에 대한 정확하고 연속적인 질의 처리가 가능한 새로운 최근접 질의 처리 기법을 제안하였으며, 이를 연속 궤적 최근접(continuous trajectory NN, CTNN) 질의라 부른다. 이 논문에서는 빠른 응답 시간을 얻기 위한 근사 연속 궤적 최근접(approximate CTNN, ACTNN) 질의 처리 기법과 정확한 최근접 탐색을 가능하게 하는 정확 연속 궤적 최근접(exact CTNN, ECTNN) 질의 처리 기법을 제안하였다. 우리는 여러 데이타 셋을 기반으로 실험을 하였으며, 실험결과는 제안된 ECTNN 기법의 경우 정확도는 상당히 높은 반면, 응답시간은 약간 낮은 성능을 보였다. 또한 ACTNN 기법의 경우 정확도는 ECTNN 기법에 비해 낮은 반면, 응답시간은 높은 성능을 보였다. 제안된 기법들은 항해 시스템, 교통 통제 시스템, 물류정보 시스템 등 각종 위치 기반 서비스에 다양하게 사용될 수 있고, 특히 질의 객체와 데이타 객체가 모두 이동 점 객체이면서 이들의 궤적 정보를 미리 파악할 수 있는 경우에 가장 적합하다.

누적밀도 웨이블릿 히스토그램을 이용한 공간 선택율 추정

지정희(Jeong Hee Chi),정재혁(Jae Hyuk Jeong),류근호(Keun Ho Ryu) 한국정보과학회 2005 정보과학회논문지 : 데이타베이스 Vol.32 No.5

선택율 추정 기법들의 공통적인 목표는 데이타의 요약 정보를 적은 저장 공간에 유지하고, 추정된 값과 질의 결과에 대한 오차를 최소화하는 것이다. 방대한 양의 공간 데이타에 대한 선택율 추정의 경우, 정확한 결과를 얻기 위해서는 공간 데이타의 분포를 반영하는 요약 정보를 필요로 하며, 그러한 요약 정보를 생성하기 위해서는 많은 저장 공간을 필요로 한다. 따라서, 이 논문에서는 적은 저장 공간을 사용하면서, 정확성 높은 선택율을 추정하는 누적밀도 웨이블릿 히스토그램을 제안한다. 이 히스토그램은 기존의 누적밀도 히스토그램에 유지되는 각 서브 히스토그램에 대해 웨이블릿 변환을 적용함으로써, 보다 적은 저장 공간에서 높은 정확도의 선택율을 얻을 수 있다. 우리는 실험결과를 통하여 기존 히스토그램의 저장 공간에 25%~50%만을 사용하여 높은 정확도의 선택율 추정 결과를 보임으로써, 기존의 다른 선택율 추정기법들이 갖는 저장공간에 대한 제약사항을 해결함과 동시에 적은 저장공간을 사용하여 높은 정확도의 선택율 추정이 가능함을 확인 하였다. 이 논문에서 제안된 기법은 공간 데이타베이스에서의 공간 범위 질의에 대한 정확성 높은 선택율을 추정하기 위해 사용될 수 있다. The purpose of selectivity estimation is to maintain the summary data in a very small memory space and to minimize the error of estimated value and query result. In case of estimating selectivity for large spatial data, the existing works need summary information which reflect spatial data distribution well to get the exact result for query. In order to get such summary information, they require a much memory space. Therefore in this paper, we propose a new technique cumulative density wavelet Histogram, called CDW Histogram, which gets a high accurate selectivity in small memory space. The proposed method is to utilize the sub-histograms created by CD histogram. The each sub-histograms are used to generate the wavelet summary information by applying the wavelet transform. This fact gives us good selectivity even if the memory size is very small. The experimental results show that the proposed method simultaneously takes full advantage of their strong points - gets a good selectivity using the previous histogram in (25%~50%) memory space and is superior to the existing selectivity estimation techniques. The proposed technique can be used to accurately quantify the selectivity of the spatial range query in databases which have very restrictive memory.

데이타 분석을 위한 시공간 집계 함수의 확장

지정희(Jeong Hee Chi),신현호(Hyun Ho Shin),김상호(Sang Ho Kim),류근호(Keun Ho Ryu) 한국정보과학회 2005 정보과학회논문지 : 데이타베이스 Vol.32 No.1

시공간 데이타베이스는 실세계에 존재하는 다양한 유형의 객체에 대한 공간 관리와 이력정보를 동시에 제공함으로써 사용자에게 시공간 데이타에 대한 저장 및 질의 수단을 제공한다. 실세계에서 “임의의 질의 윈도우 영역에서 2001년 4월부터 8월까지 농경지당 뿌려진 농약의 평균은 얼마인가?”와 같은 질의를 할 수 있다. 이러한 집계 질의는 시간과 공간에 대한 제약을 가지고 있다. 그러나 기존의 집계에 대한 연구는 시간 또는 공간에만 편중되어 시간과 공간 제약을 모두 가진 시공간 데이타에 직접 적용하기 어려운 문제점이 있다. 따라서 이 논문에서는 시공간 특성을 가진 시공간 데이타 분석을 위한 시공간 집계 함수 stCOUNT, stSUM, stAVG, stMAX, stMIN를 제안한다. 아울러 제안된 시공간 집계함수를 적용한 부동산 관리 시스템을 통해 기존의 시간, 공간 집계함수가 분석하기 어려웠던 시공간 데이타에 대한 분석의 용이함과 응용 시스템에 맞는 질의 표현력의 개선 및 편리성을 제공함을 보였다. 그리고 제안된 시공간 집계함수의 알고리즘의 성능 평가를 통해 알고리즘 성능의 타당성을 입증하였다. Spatiotemporal databases support methods of recording and querying for spatiotemporal data to user by offering both spatial management and historical information on various types of objects in the real world. We can answer to the following query in real world: "What is the average of volume of pesticide sprayed for each farm land from April to August on 2001, within some query window". Such aggregation queries have both temporal and spatial constraint. However, previous works for aggregation are attached only to temporal aggregation or spatial aggregation. So they have problems that are difficult to apply for spatiotemporal data directly which have both spatial and temporal constraint. Therefore, in this paper, we propose spatiotemporal aggregate functions for analysis of spatiotemporal data which have spatiotemporal characteristic, such as stCOUNT, stSUM, stAVG, stMAX, stMIN. We also show that our proposal resulted in the convenience and improvement of query in application systems, and facility of analysis on spatiotemporal data which the previous temporal or spatial aggregate functions are not able to analyze, by applying to the estate management system. Then, we show the validity of our algorithm performance through the evaluation of spatiotemporal aggregate functions.

이동객체를 위한 현재 질의 선택율 추정 기법

지정희(Jeong-Hee Chi),류근호(Keun-Ho Ryu),정두영(Doo-Young Jeong) 한국컴퓨터정보학회 2006 韓國컴퓨터情報學會論文誌 Vol.11 No.1

선택율 추정은 질의 최적화를 위한 기법중의 하나이다. 이동객체에 대한 기존 선택율 추정 기법은 시간에 따른 이동객체의 위치 변화를 요약 정보에 반영하지 못하며, 또한 기존 공간 요약 정보를 확장하여 이용함으로써 선택율 추정시 많은 에러를 발생시키고 있다. 기존 기법들이 이동객체의 위치 정보 변화를 요약 정보에 반영하기 위해서는 요약 정보를 자주 재생성해야 하며, 그러므로 전체 데이터베이스를 자주 스캔해야 하는 문제점을 갖고 있다. 따라서 이 논문에서는 이동객체의 현재 질의에 대한 선택율 추정 기법을 개발하기 위하여 쿼드 트리 기반의 히스토그램 기법을 제안하였다. 또한 제안된 기법의 구현과 평가를 통해 제안된 기법의 성능을 분석하였다. 이 논문에서 제안된 기법은 차량 추적 시스템, 위치 기반 서비스, 응급 구조 서비스, 그리고 텔레매틱스 서비스 등과 같은 연속적으로 위치를 변경하는 이동객체의 정보를 실시간으로 관리하고 검색하는 응용분야에 활용 가능할 것이다. Selectivity estimation is one of the query optimization techniques. It is difficult for the previous selectivity estimation techniques for moving objects to apply the position change of moving objects to synopsis. Therefore, they result in much error when estimating selectivity for queries, because they are based on the extended spatial synopsis which does not consider the property of the moving objects. In order to reduce the estimation error, the existing techniques should often rebuild the synopsis. Consequently problem occurs, that is, the whole database should be read frequently. In this paper, we proposed a moving object histogram method based on quad tree to develop a selectivity estimation technique for moving object queries. We then analyzed the performance of the proposed method through the implementation and evaluation of the proposed method. Our method can be used in various location management systems such as vehicle location tracking systems, location based services, telematics services, emergency rescue service, etc in which the location information of moving objects changes over time.

BHUI: A New Bitwise Operation-based High Utility Itemset Mining

Jeong-Hee Hwang(황정희),Jeonghee Chi(지정희),Soyoung Park(박소영) 대한전기학회 2019 전기학회논문지 Vol.68 No.11

Pattern mining finding frequent patterns are widely used to search useful information from large scale data. General pattern mining, however, have the problem of not applying the characteristics of the individual items because all items have the same importance. High utility itemset mining that solves this problem retrieves meaningful information by applying a relative weight to each item. In this paper, we propose a new high utility itemset mining algorithm based on bitwise operations. The bitwise operation predetermines the likelihood of joining two itemsets to reduce the join operation. Since the join operation is the most time consuming operation in the high utility itemset mining, the proposed algorithm significantly reduces the mining time. We analyzed the performance of the proposed algorithm with execution time and the number of generated utility itemsets and compared the performance with HUI-Miner. Our experimental results show that the proposed algorithm outperforms HUI-Miner.

CORBA 서비스의 성능 향상을 위한 인터페이스 설계

김상호,지정희,류근호,Kim, Sang-Ho,Chi, Jeong-Hee,Ryu, Keun-Ho 한국정보처리학회 2004 정보처리학회논문지D Vol.11 No.1

A new research of geographic information system has been focused on an open architecture, interoperability and extensibility in their design. In order to process huge data, multidimensional data and heterogeneous geographic format data, these research move away from monolithic system to open structure system managing application layer and user interface layer. Nowadays, many developers have used CORBA middleware for the OGIS systems. However, CORBA middleware has some problems that support only a point-to-point communication and takes a long time to transfer sever data to client. Thus, in this paper, we propose a method on modifying a point-to-point communication and implement the efficient communication method. The proposed method that transfer data from sever to client in one connection support a group communication and reduce a transfer time delay. 지리정보시스템에 대한 연구는 개방형 구조, 상호운영성과 확장 가능성에 초점을 두고 발전되어 왔다. 이 연구들은 기존에 구축된 하나의 통합시스템의 형태에서 대용량의 데이터, 고차원 구조의 데이터 그리고, 서로 다른 지리 포멧의 데이터를 처리하기 위하여, 응용 프로그램과 사용자 인터페이스를 레이어 별로 구분하여 각기 관리하는 개방형 구조로 시스템이 구현되어야 함을 의미한다. 현재 구현되는 개방형 지리정보시스템을 위한 미들웨어들 중 CORBA 미들웨어는 특정 운영체제를 기반으로 하지 않아 많은 개발자들이 이용하고 있다. 이때, CORBA의 서비스는 점대점 통신만을 지원하고, 다른 미들웨어보다 데이터 제공 시간이 많이 소요되는 문제점을 가지고 있다. 따라서 이 논문에서는 점대점 통신기법의 수정 방법을 제안하고, 구현한다. 제시된 방법은 클라이언트가 서버의 데이터를 한번의 연결로 데이터를 제공함으로써 그룹 통신과 빠른 데이터 제공 속도를 보장할 수 있게 한다.

4차원 시공간 데이터를 위한 OpenGIS 모델의 확장

김상호,지정희,류근호,Kim Sang Ho,Chi Jeong Hee,Ryu Keun Ho 한국정보처리학회 2005 정보처리학회논문지D Vol.12 No.3

Most of data objects in the real world have spatial and temporal information simultaneously. One of the objectives of spatiotemporal databases is to provide a very expressive framework for spatiotemporal database applications. The object oriented spatiotemporal model can manage spatiotemporal data efficiently because the model is able to store the complete history of any objects. Therefore, in order to handle the spatiotemporal data in object oriented fashion, we proposed a low dimensional spatiotemporal model in the object oriented fashion that extended dimensionally two dimensional spatial model of OpenGIS to fit into the real world information and to include temporal information. In order to proof the proposed model, we design a data provider component which consists of the data source, the session, the command, and the rowset component, and implement it. The proposed four dimensional spatiotemporal data model and provider in the object oriented fashion can be used to store, retrieve and manage the object oriented spatiotemporal data. 실세계의 많은 객체들은 시간적 정보와 공간적 정보를 함께 가지고 있고, 이러한 정보를 다루기 위한 시공간 데이터 모델링의 목적 중에 하나는 시공간 객체를 위한 응용프로그램을 지원할 수 있게 하는 것이다. 객체지향 시공간 모델은 객체단위로 시공간 데이터를 관리 할 수 있기 때문에 효율적으로 시공간 데이터를 관리할 수 있어야 한다. 따라서, 이 논문에서는 시공간 데이터 관리를 객체지향 방식으로 지원할 수 있도록 개방형 지리정보 시스템에서 제안한 2차원 공간모델을 실세계 정보에 맞게 차원적으로 확장하고, 시간 정보를 포함하도록 확장한 모델을 제안한다. 그리고, 제안된 모델의 타당성을 검증하기 위해, 모델을 위한 시공간 데이터 제공자 컴포넌트인 data source 컴포넌트, session 컴포넌트, command 컴포넌트와 rowset 컴포넌트를 구현하고 수행 예를 보인다. 제안된 시공간 데이터 모델과 데이터 제공자는 서로 다르게 저장된 시공간 데이터를 객체지향 모델링을 사용하여 저장, 검색 및 관리할 수 있게 한다.