이동체의 색인을 위한 시간 기반 R-트리의 설계 및 구현

전봉기(Bong Gi Jun),홍봉희(Bong Hee Hong) 한국정보과학회 2003 정보과학회논문지 : 데이타베이스 Vol.30 No.3

위치 기반 서비스는 이동체의 위치에 따라 종속적인 결과를 얻는 위치 기반 질의를 필요로 하게 하였다. 연속적으로 이동하는 이동체의 위치를 추적하는 것은 위치 기반 서비스에서는 중요한 응용 중의 하나이다. 효과적인 질의 처리를 위해 이동체 데이터베이스는 연속적으로 위치를 변경하는 이동체의 이동을 관리하는 3차원 색인을 필요로 한다. 2차원 R-tree의 확장으로 시간 도메인을 포함하는 3DR-tree와 같은 이동체 색인은 노드 간의 높은 중복과 사장 공간으로 인하여 낮은 공간 활용도와 검색 성능이 저하되는 문제점이 있다. 이 논문에서 제시하는 TR-tree는 R-tree 기반의 색인으로서, 시간 도메인의 성장을 고려하여 시간 축 분할 시 비균등 분할 정책을 사용하여 공간 활용도를 높였다. 노드간의 중복과 사장 공간을 최소화 하기 위하여 강제 합병 정책을 사용하여 중복이 심한 노드를 강제 합병 시킨다. 또한 오버플로우 노드의 분할 시에 노드간의 중복을 심하게 하는 원인이 되는 긴 선분을 절단 정책을 사용하여 2개의 선분으로 절단하여 분할 노드 간의 중복을 제거한다. 실험 평가 결과에서 TR-tree는 3DR-tree와 TB-tree 보다 성능이 우수하였으며, 특히 R-tree와 R*-tree보다 색인의 크기가 작다. Location-Based Services(LBS) give rise to location-based queries of which results depend on the locations of moving objects. One of important applications of LBS is to examine tracks of continuously moving objects. Moving objects databases need to provide 3-dimensional indexing for efficiently processing range queries on the movement of continuously changing positions. An extension of the 2-dimensional R-tree to include time dimension shows low space utilization and poor search performance, because of high overlap of index nodes and their dead space. To solve these problems, we propose a new R-tree based indexing technique, namely TR-tree. To increase storage utilization, we assign more entries to the past node by using the unbalanced splitting policy. If two nodes are highly overlapped, these nodes are forcibly merged. It is the forced merging policy that reduces the dead space and the overlap of nodes. Since big line segments can also affect the overlap of index nodes to be increased, big line segments should be clipped by the clipping policy when splitting overfull nodes. The TR-tree outperforms the 3DR-tree and TB-tree in all experiments. Particularly, the storage utilization of the TR-tree is higher than the R-tree and R*-tree.

효율적인 비동기 전송을 지원하기 위한 RTLS 미들웨어의 확장

박재관,홍봉희,이승철,Park, Jae-Kwan,Hong, Bong-Hee,Lee, Seung-Chul 대한공간정보학회 2009 한국공간정보시스템학회 논문지 Vol.11 No.2

최근, 많은 기업에서 실시간 자산 관리를 위해 RTLS 시스템을 구축하고 있다. RFID와 달리, RTLS 태그는 이동 과정과 한정되지 않고 임의의 위치에서 지속적으로, 자동적으로 인식된다. 그러나, RTLS 미들웨어의 표준 API는 2가지 한계점이 있다. 미들웨어가 애플리케이션으로 불필요한 데이터를 포함하는 대용량의 데이터를 전달해야 한다는 것과 미들웨어에서 애플리케이션으로 질의 결과를 전달하는 방식에서 동기 방식만을 지원한다는 문제가 그것이다. 이 논문에서는 이러한 문제를 해결하기 위해, 다양한 질의에 대해 애플리케이션으로 전달되는 데이터 량을 줄이기 위한 질의 타입별 정제 조건을 명세할 수 있는 SessionSpec을 정의하고 실시간 이벤트 처리를 위한 비동기 방식 지원 방법을 제안한다. 또한, 이러한 방법을 적용한 RTLS 미들웨어를 설계하고 구현하여 그 결과를 확인하였다. Recently many global enterprises build RTLS system for their environments. RTLS is used to detect object at real tim e. Unlike RFID, RTLS tags are read automatically and continuously, independent of the process that moves the tags. The proposed functionality of standard API has two problems. When middleware provides data to application, it sends a huge amount of data that may be useless. When only an application requests for data, the middleware replies result data in synchronous mode. This paper proposes a method to reduce an amount of data transferring from middleware to application and an addition communication mode to support real-time event processing in the middleware. Also, we designed and implemented an RTLS middleware applying the proposed methods.

객체 지향 지식베이스를 위한 그래픽 사용자 인터페이스의 설계 및 구현

전봉기(Bong-gi Jun),홍봉희(Bong-hee Hong) 한국정보과학회 1994 정보과학회논문지 Vol.21 No.2

이 논문은 객체 지향 지식베이스의 복잡한 객체 구조와 규칙 종속 관계를 아이콘 베이스 지식 브라우징으로 보여주는 그래픽 사용자 인터페이스의 설계 및 구현 내용을 제시한다. 이 논문에서 지식 객체 브라우징을 지원하기 위해서 인스턴스 객체들 간의 복잡한 관련성을 브라우징하기 위한 인스턴스 집합 아이콘, 활동 링크, 변형된 동기화 브라우징 방법을 새로 제시한다. 그리고 사용자가 규칙의 의미와 규칙들 간의 종속 관계를 노드와 링크로 보여주는 아이콘 베이스 규칙 브라우징 방법을 제시한다. 또한, 이 논문에서는 아이콘 베이스 지식 브라우징의 X11 구현을 위해 저장 객체 층과 윈도우 객체 층으로 구성되는 2단계 층 구조를 제시하고 2단계 층 간의 매핑 알고리즘을 제시하였다. This paper presents the issues of designing and implementing an icon-based graphic user interface for representing object-oriented knowledge as a network of nodes connected by arcs. The icon-based browser supports the visual representation of complex relationships among instance objects by using instance set icons, active links, modified synchronized-browsing method. This paper also presents a new rule browsing method for representing the dependency of rules and the meaning of a new rule. This paper presents a 2 layer architecture, which consists of internal object structure layer and window object layer, for implementing the icon-based graphic user interface. The mapping algorithms between the 2 layer objects are realized by using the Motif X11 window.

TPR 트리에서 경계사각형 재구성 기법의 설계 및 구현

김동현,홍봉희,Kim, Dong-Hyun,Hong, Bong-Hee 한국공간정보학회 2004 개방형지리정보시스템학회 논문지 = Journal of the Korea Open Geogr Vol.6 No.2

TPR-tree의 각 노드는 이동체를 색인하기 위하여 시간 함수를 기반으로 한 경계사각형을 이용한다. 경계사각형의 각 축을 계산하기 위하여 시간함수를 사용하므로 시간이 흐름에 따라 노드의 경계사각형은 확장된다. 따라서 이웃하는 노드간의 중첩(overlap) 영역이 커지기 때문에 영역질의의 성능이 점차적으로 떨어지는 문제가 있다. 이 논문에서는 이동체 삽입과 삭제 시 노드의 경계사각형을 재구성하기 위한 기법들을 제시한다. 이동체를 삽입할 때 노드간의 중첩을 줄이기 위하여 중첩이 심한 두 개의 단말 노드를 강제 합병하고 재분할하는 강제 합병 기법을 사용한다. 그리고 이동체를 삭제할 때 다른 이동체도 재삽입하는 강제 재삽입 기법을 이용한다. 강제 재삽입 기법은 삭제 노드 강제 재삽입 기법과 중첩 노드 강제 재삽입 기법으로 분류된다. 실험 결과에서 중첩 노드 강제 재삽입 기법이 다른 두 기법에 비하여 우수함을 알 수 있다. The TPR-tree exploits bounding rectangles based on the function of time in order to index moving objects. As time passes on, each edge of a BR expands with the fastest velocity vector. Since the expansion of the BR results in a serious overlaps between neighboring nodes, the performance of range query is getting worse. In this paper, we propose schemes to reorganize bounding rectangles of nodes. When inserting a moving object, we exploit a forced merging scheme to merge two overlapped nodes and re-split it. When deleting a moving object, we used forced reinsertion schemes to reinsert other objects of a node into a tree. The forced reinsertion schemes are classified into a deleted node reinsertion scheme and an overlapped nodes reinsertion scheme. The overlapped nodes reinsertion scheme outperforms the forced merging scheme and the deleted node reinsertion scheme in all experiments.

위치 기반 질의 처리를 위한 궤적 보존 색인의 설계 및 구현

임덕성,홍봉희,Lim, Duk-Sung,Hong, Bong-Hee 한국공간정보학회 2008 한국공간정보시스템학회 논문지 Vol.10 No.3

위치 기반 서비스(Location-Based Service)는 무선 통신에 기반 한 서비스로서 최근 그 중요성이 증대되고 있다. 차량, 선박과 같이 시간에 따라 위치를 변경하는 이동 객체(moving object)의 이동 경로는 궤적(trajectory)으로 표현된다. 이동 객체의 궤적 모니터링을 위한 데이터베이스에서는 이동객체의 위치를 추적할 뿐만 아니라 이동 경로를 감시하기 위한 궤적 질의를 효율적으로 지원해야 하므로 이동 객체의 궤적 정보를 효과적으로 관리하고, 빠른 검색을 제공하는 이동 객체 색인 방법이 필요하다. 이 논문에서는 먼저 기존 궤적 색인 구조에서 사장 영역 문제를 정의한다. 궤적 색인의 사장 영역은 궤적 보존 속성으로 인해 공간적 지역성을 고려되지 않기 때문에 발생한다. 이를 해결하기 위해 이 논문에서는 사장 영역 및 비단말 노드간의 중첩을 줄이기 위해 엔트리 재배치 기법을 제시하고, 제안된 색인과 기존 알고리즘을 사용하는 색인과의 성능비교를 통하여 제시한 색인의 우수성을 입증한다. With the rapid development of wireless communication and mobile equipment, many applications for location-based services have been emerging. Moving objects such as vehicles and ships change their positions over time. Moving objects have their moving path, called the trajectory, because they move continuously. To monitor the trajectory of moving objects in a large scale database system, an efficient Indexing scheme to processed queries related to trajectories is required. In this paper, we focus on the issues of minimizing the dead space of index structures. The Minimum Bounding Boxes (MBBs) of non-leaf nodes in trajectory-preserving indexing schemes have large amounts of dead space since trajectory preservation is achieved at the sacrifice of the spatial locality of trajectories. In this thesis, we propose entry relocating techniques to reduce dead space and overlaps in non-leaf nodes. we present performance studies that compare the proposed index schemes with the TB-tree and the R*-tree under a varying set of spatio-temporal queries.

RFID 스트리밍 데이터 처리를 위한 연속 질의의 변환 기법

박재관,홍봉희,반재훈,Park, Jae-Kwan,Hong, Bong-Hee,Ban, Chae-Hoon 한국정보처리학회 2007 정보처리학회논문지D Vol.14 No.3

RFID 미들웨어 시스템은 애플리케이션의 질의를 처리하기 위해서 다수의 RFID 판독기에 의해 지속적으로 인식되는 RFID 스트리밍 데이터를 수집 및 정제한다. 이러한 질의들은 미들웨어에서 일정기간 동안 수행되기 때문에 연속 질의라고 불린다. 미들웨어의 성능을 개선하기 위해서는, 이러한 연속 질의를 효과적으로 처리하기 위한 색인이 필수적이다. 최근, 데이터가 아닌 질의를 기반으로 색인을 구축하는 질의 색인 기법들이 제안되었으며 이러한 기법들은 이동체 위치 스트리밍 데이터 혹은 센서 스트리밍 데이터에 대하여 연속 질의를 처리하는 환경에서 향상된 성능을 보여준다. EPCglobal은 RFID 애플리케이션을 위한 표준 질의 인터페이스인 Event Cycle Specification (ECSpec)을 제안하였다. ECSpec 기반의 연속 질의는 질의의 조건을 대상 도메인 공간에 표현하면 다수의 세그먼트로 표현되는 특징이 있다. 이러한 RFID 질의 색인의 데이터에 대하여 기존의 질의 색인을 사용하면 다수의 데이터를 삽입해야 하기 때문에 색인을 구축 및 유지하기 위한 비용이 커지게 된다. 이러한 문제를 해결하기 위해서, 이 논문에서는 다수의 세그먼트를 새로운 변환공간으로 표현하고 이것을 결집하여 단일 데이터로써 표현하는 결집 변환(Aggregate Transformation) 기법을 제안한다. 또한, 기존 질의 색인과 변환 기법을 적용한 색인의 성능을 비교한다. RFID middleware systems collect and filter the RFID streaming data gathered continuously by numerous readers in order to process requests from applications. These requests are called continuous queries because they are kept on executing during certain periods. To enhance the performance of the middleware, it is required to build an index to process the continuous queries efficiently. Several approaches of building an index on not data records but queries, called Query Index, are proposed and widely used for evaluating continuous queries over streaming data. The EPCglobal proposed an Event Cycle Specification (ECSpec) model, which is a standard query interface for RFID applications. Continuous queries based on ECSpec consist of a large number of segments for representing the query conditions. The problem with using any of the existing query indexes on these continuous queries is that it takes a long time to build the index because it is necessary to insert a large number of segments into the index. To solve this problem, we propose an Aggregate Transformation that converts a group of segments into a compressed data which is representative of the segments. We compare the performance of a transformed index with the existing query indexes.

이동체 데이터베이스를 위한 해쉬 기반의 공간 색인

전봉기(Bong-Gi Jun),홍봉희(Bong-Hee Hong) 한국정보과학회 2001 한국정보과학회 학술발표논문집 Vol.28 No.2Ⅰ

이동 객체는 현실 세계의 차량과 같이 시간에 따라 움직이는 모든 객체를 말한다. 이동체 데이터베이스는 이동 객체가 연속적으로 위치 정보가 변하기 때문에 기존의 데이터베이스 기법과 차이가 있다. 이동 객체의 위치 변경은 빈번한 갱신 연산을 수행해야 하는 문제점이 있고, 이동체의 움직임을 모두 저장할 수 없으므로 이동 객체의 움직임을 이산적 표현 방법을 사용하여 이동 객체의 현재와 미래 위치를 계산해야 한다. 이동 객체의 빈번한 위치 변경은 색인 처리 비용이 증가를 초래한다. 이 논문에서는 빈번한 갱신으로 발생하는 색인의 과부하를 최소화하는 해쉬 기반의 공간 색인 구조를 사용한 이동 객체의 위치 변경 처리 기법을 제안한다. 또한 이동 객체의 이산적 표현을 위한 자료 구조를 제시하며, 이동 객체의 밀집화 문세를 해결하기 위하여 오버플로우 처리 방법을 기존의 해슁 오버플로우 처리 방법을 응용하여 3가지 방법으로 제안한다. 버퍼질의를 이용하여 이동 객체의 영역 질의 방법을 제안한다.

X 윈도우 시스템을 이용한 부품 배치 프로그램의 개발

전봉기(Bong-Gi Jun),김종민(Jing-Min Kim),홍봉희(Bong-Hee Hong),김민환(Min-Hwan Kim) 한국정보과학회 1992 한국정보과학회 학술발표논문집 Vol.19 No.2

본 논문은 사용자가 판재위에 부품을 배치하고자 할 때, 이를 대화식으로 처리해 주는 기능과, 실제 산업 현장에서 필요한 요구들을 고려한 부품배치 프로그램의 개발에 관한 연구이다. 사용자가 부품을 관리하게 배치하게 하기 위한 다양한 배치명령 모듈과 직선과 호(arc)로 구성된 부품간의 거리를 체크하는 모듈, 판재의 이용효율을 계산하기 위한 부품의 면적계산 모듈 등을 개발하였다. 부품배치 프로그램은 Sun Sparc 호환 기종에서 Motif X-window를 사용하여 C 언어로 구현하였으며, 최종 결과로써 NC machine에 필요한 판재에서의 부품 위치 데이타를 생성하도록 하였다.

객체 중심 지식베이스를 위한 아이콘 베이스 브라우징 방법

전봉기(Bong-gi Jun),김민환(Min-hwan Kim),홍봉희(Bong-hee Hong) 한국정보과학회 1992 한국정보과학회 학술발표논문집 Vol.19 No.2

다양한 지식 객체 구조, 객체들 간의 복잡한 관련성, 그리고 규칙들 간의 종속 관련성이 지식베이스를 사용하기가 어렵게 하는 큰 장애 요인이었다. 지식베이스를 효율적으로 구축, 유지, 관리하기 위해서는 사용하기 쉽고 지식 구조를 쉽게 이해할 수 있는 그래픽 사용자 인터페이스가 필요하다. 이 논문에서는 지식을 아이콘 노드와 링크로 표현하고 스키마 브라우징 이외에 인스턴스 객체 간의 임의의 관련성을 보여주는 관련성 브라우징과 규칙들 간의 종속 관련성을 보여주는 규칙 브라우징의 X11 윈도우 구현 방법을 제시한다.

이동체의 관성을 이용한 궤적 색인의 병렬화 기법

서영덕,홍봉희,Seo, Young-Duk,Hong, Bong-Hee 한국공간정보학회 2006 한국공간정보시스템학회 논문지 Vol.8 No.1

최근 가장 활발하고 많은 연구가 이루어지는 시스템중의 하나는 교통 제어 시스템이다. 이 시스템을 효과적으로 지원하기 위해서는 이동체를 효과적으로 저장하고, 시간 혹은 시공간 질의를 효과적으로 수행하기 위하여 높은 성능을 가진 이동체 데이터베이스 시스템이 필요하다. 빠른 이동체 데이터베이스 시스템의 성능은 병렬 색인을 이용하여 구축될 수 있다. 이 논문에서는 시공간 인접성과 이동체 특성에 기반한 디클러스터링 정책을 제시한다. 이동체의 진행 방향에 대한 예측을 통하여 색인의 노드에 대한 성장을 예측하고, 이를 토대로 병렬 색인을 구축한다. 실험 결과 제시된 기법은 기존의 다른 정책에 비하여 최대 15%이상의 성능 향상이 있다. 이 결과는 단일 디스크를 사용할 때에 비하여 디스크 당 50%이상의 성능향상 결과이다. One of the most challenging and encouraging applications of state-of-the-art technology is the field of traffic control systems. It combines techniques from the areas of telecommunications and computer science to establish traffic information and various assistance services. The support of the system requires a moving objects database system (MODB) that stores moving objects efficiently and performs spatial or temporal queries with time conditions. In this paper, we propose schemes to distribute an index nodes of trajectory based on spatio-temporal proximity and the characteristics of moving objects. The scheme predicts the extendible MBB of nodes of index through the prediction of moving object, and creates a parallel trajectory index. The experimental evaluation shows that the proposed schemes give us the performance improvement by 15%. This result makes an improvement of performance by 50% per one disk.