이동객체의 궤적처리를 위한 트리기반 색인기법의 성능분석

심춘보,신용원 한국지리정보학회 2004 한국지리정보학회지 Vol.7 No.4

본 연구에서는 GIS 응용에서 이동객체의 궤적을 인덱싱하기 위해 기존에 제안되었던 TB(Trajectory-Bundle)-트리의 성능을 개선시킬 수 있는 연결테이블(LinkTable:L-Table) 기반의 확장된 TB-트리(L-Table TB-Tree:LTB-Tree)를 제안하고 아울러 제안하는 색인기법의 성능평가를 위해 다음과 같은 사항을 고려한다. 첫째, 기존의 R*-트리, IB-트리, 그리고 제안하는 LTB-트리를 성능평가 대상으로 선정한다. 둘째, 실험 데이타 집합으로는 랜덤 데이타 집합 및 실제 데이타 집합을 이용한다. 셋째, 시스템의 가용 메모리의 제약을 고려해 메모리 버퍼 크기에 따른 성능평가를 수행한다. 넷째, 다양한 데이타 분포도를 가지고 있는 실험 데이타를 이용하여 성능평가를 수행한다. 마지막으로 삽입성능 및 검색성능(궤적질의 및 영역질의)을 평가한다. 성능평가를 분석한 결과, 제안하는 색인기법이 기존의 색인기법들에 비해 삽입과 궤적질의의 검색 측면에서 더 우수함을 보인다. In this study, we propose Linktable based on extended TB-Tree (LTB-Tree) which can improve the performance of existing TB (Trajectory-Bundle) -tree proposed for indexing the trajectory of moving objects in GIS Applications. In addition, in order to evaluate proposed indexing scheme, we to ke into account as follows. At first, we select existing R^*-tree, TB-tree, and LTB-tree as the subject of performance evaluation. Secondly, we make use of random data set and real data set as experimental data. Thirdly, we evaluate the performance with respect to the variation of size of memory buffer by considering the restriction of available memory of a given system. Fourth, we test them by using the experimental data set with a variation of data distribution. Finally, we think over insertion and retrieval performance of trajectory query and range query as experimental measures. The experimental results show that the proposed indexing scheme, LTB-tree, gains better performance than traditional other schemes with respect to the insertion and retrieval of trajectory query.

상황인식 처리를 위한 미들웨어 및 컨텍스트 서버를 이용한 응용시스템의 구현

심춘보(Choon-Bo Shim),태봉섭(Bong-Sub Tae),장재우(Jae-Woo Chang),김정기(Jeong-Ki Kim),박승민(Seung-Min Park) 한국정보과학회 2006 정보과학회 컴퓨팅의 실제 논문지 Vol.12 No.1

상황인식 처리기술은 사용자의 컨텍스트에 근거하여 사용자와 장치간의 상호 운용성을 지원해 줌으로써, 사용자로 하여금 정보 획득 및 실행을 보다 용이하게 하도록 해주는 기술이다. 이는 유비쿼터스 컴퓨팅 환경에서 가장 중요한 핵심 기술중의 하나이다. 따라서 본 논문에서는 유비쿼터스 컴퓨팅에서 상황인식 처리를 위한 미들웨어 및 컨텍스트 서버를 제안하고, 이를 이용한 응용시스템을 구현한다. 본 연구에서 제안하는 미들웨어는 블루투스 무선 통신 기술을 이용하여 이동성을 지닌 이동 노드를 발견하고 컨텍스트 서버로부터 해당 컨텍스트에 적합한 실행 모듈을 실행하는 기능을 담당한다. 한편, 제안하는 컨텍스트 서버는 사용자의 현재 상태, 물리적 환경, 컴퓨팅 시스템의 리소스 등의 상황 정보를 효율적으로 데이타베이스 서버에 저장하는 관리자의 역할을 수행한다. 마지막으로 본 연구에서 구현된 응용시스템은 상황정보에 근거하여 음악 재생 서비스를 제공하는 응용 시스템으로써, 아울러 본 연구에서 구축된 미들웨어 및 컨텍스트 서버의 유용성을 보이고 있다. Context-awareness is a technology to facilitate information acquisition and execution by supporting interoperability between users and devices based on users' context. It is one of the most important technologies in ubiquitous computing. In this paper, we propose a middleware and a context server for dealing with context-awareness in ubiquitous computing and implement an application system using them. The middleware proposed in our work plays an important role in recognizing a moving node with mobility by using a Bluetooth wireless communication technology as well as in executing an appropriate execution module according to the context acquired from a context server. In addition, the proposed context server functions as a manager that efficiently stores into a database server context information, such as user's current status, physical environment, and resources of a computing system. Finally, our application system implemented in our work one which provides a music playing service based on context information, and it verifies the usefulness of both the middleware and the context server developed in our work.

의료 환경을 위한 음성 서비스 기반의 상황인식 지원 시스템의 구현

심춘보(Choon-Bo Shim),신용원(Yong-Won Shin),박병래(Byung-Rae Park) 한국컴퓨터정보학회 2005 韓國컴퓨터情報學會論文誌 Vol.10 No.4

컴퓨팅 환경이 보다 발전함에 따라 병원에서 환자 회진 및 진찰시 PDA나 랩탑 및 타블렛 PC 등과 같은 post PC를 이용한 보다 적용적이고 지능화된 서비스가 요구되어진다. 본 논문에서는 의료 환경을 위한 음성 서비스 기반의 상황인식 지원 시스템을 설계 및 구현한다. 이를 위해, 먼저 블루투스 무선 통신기술을 이용하여 이동성을 지닌 PDA를 소유한 클라이언드를 인식하고, 컨텍스트 서버로부터 환자들을 위한 진단 정보 전송과 같은 해당 클라이언트의 컨텍스트에 적합한 실행 모듈을 실행하는 역할을 담당하는 컨텍스트 미들웨어를 제안한다. 아울러, 사용자의 현재 상태, 물리적 환경, 컴퓨팅 시스템의 리소스 등의 상황 정보를 효율적으로 데이터베이스 서버에 저장하는 관리자의 역할을 수행하는 컨텍스트 서버를 기술한다. 마지막으로, 제안하는 시스템의 유용성을 검증하기 위해, 컨텍스트 미들웨어를 통해 다른 의사들에게 해당 환자의 정보를 통보할 수 있는 음성 재생 서비스를 제공하는 응용 시스템을 개발한다. As computing environments are more rapidly developed, an adaptive and intelligent services using post PC such as PDA, Laptop, and Tablet PC in case of rounding and examining patients are highly demanded. The objective of this study is to design and implement a context-awareness support system based on voice service for medical environments. To achieve it, we propose a context middleware which plays an important role in recognizing a client with PDA by using a Bluetooth wireless communication technology as well as in executing an appropriate execution module, like delivery for diagnosis information of patients, according to the staff's context acquired from a context server. In addition, the context server functions as a manager that efficiently stores context information such as client's current status, physical environment, and device resources into a database server. Finally, for verifying the usefulness of the proposed system, we develop an application system which provides voice playing services for notification of other physicians through our context middleware.

스포츠 비디오 데이터를 위한 내용 기반 비디오 검색 시스템

심춘보(choon-Bo Shim),장재우(Jae-Woo Chang) 한국정보과학회 데이터베이스 소사이어티 2003 데이타베이스 연구 Vol.19 No.3

비디오 데이타베이스에서 이동 객체를 위한 k-워핑 알고리즘 기반 유사 부분궤적 검색

심춘보(Choon-Bo Shim),장재우(Jae-Woo Chang) 한국정보과학회 2003 정보과학회논문지 : 데이타베이스 Vol.30 No.1

이동 객체(moving objects)의 궤적(trajectories)은 내용 기반 비디오 검색을 위해 비디오의 내용이나 의미를 색인하는 데 있어 매우 중요한 역할을 한다. 따라서 본 논문에서는 비디오 데이터가 지니는 이동 객체의 궤적(moving objects´ trajectories)에 대한 효율적인 검색을 위해 k-워핑(k-warping) 알고리즘에 기반한 유사 부분궤적 검색(similar sub-trajectory retrieval) 기법을 제안한다. 제안하는 방법은 궤적을 구성하는 움직임 요소 모두에 대해서 고정된 값(k)만큼까지의 반복을 허용하는 고정 반복 유사 부분궤적 검색(Fixed-Replication similar Sub-trajectories Retrieval: FRSR)과 움직임 요소 각각에 대해서 서로 다른 값으로 할당하고 그 값만큼까지의 반복을 허용하는 가변 반복 유사 부분궤적 검색(Variable-Replication similar Sub-trajectory Retrieval: VRSR) 방법이다. 제안하는 방법은 이동 객체의 궤적을 모델링하기 위해 주로 사용되는 방향만의 단일 속성(property) 뿐만 아니라, 방향, 거리, 그리고 시간 등을 포함하는 다중 속성(multiple properties)을 지원한다. 마지막으로, 성능 평가를 통해, 제안하는 k-워핑 알고리즘에 기반한 유사 부분궤적 검색 기법이 동등한 재현율을 유지하면서, 기존의 Li의 방법(no-warping)과 Shan의 OCMR방법(infinite-warping)에 비해 정확율 측면에서 좋은 성능을 보인다. Moving objects´ trajectories play an important role in indexing video data on their content and semantics for content-based video retrieval. In this paper, we propose new similar sub-trajectory retrieval schemes based on k-warping algorithm for efficient retrieval on moving objects´ trajectories in video data. The proposed schemes are fixed-replication similar sub-trajectory retrieval(FRSR) and variable-replication similar sub-trajectory retrieval(VRSR). The former can replicate motions with a fixed number for all motions being composed of the trajectory.The latter can replicate motions with a variable number. Our schemes support multiple properties including direction, distance, and time interval as well as a single property of direction, which is mainly used for modeling moving objects´ trajectories. Finally, we show from our experiment that our schemes outperformLi´s scheme(no-warping) and Shan´s scheme(infinite-warping) in terms of precision and recall measures.

위치 기반 서비스에서 이동 객체의 궤적을 위한 TB-트리의 확장

심춘보(Choon-Bo Shim),강홍민(Hong-Min Kang),엄정호(Jung-Ho Um),장재우(Jae-Woo Chang) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.1B

시간의 흐름에 따라 그 위치가 빈번히 변화하는 이동 객체의 특성상 실시간으로 증가하는 이동 객체의 궤적 정보를 효과적으로 관리할 수 있는 효율적인 색인 기법이 요구된다. 따라서 본 논문에서는 이동 객체의 궤적을 색인하기 위해 기존에 제안되었던 TB 트리의 성능을 개선시킬 수 있는 확장된 TB-트리(Extented TB-Tree:ETB-Tree)를 제안한다. 기존의 TB 트리는 이동 객체의 궤적 세그먼트를 삽입할 때마다 선행 세그먼트를 가지고 있는 리프 노드를 찾기 위해 루트 노드부터 리프 노드까지 순회해야만 하기 때문에 불필요한 노드 접근으로 인한 오버헤드가 발생한다. 이를 위해 ETB 트리는 선행 노드를 직접적으로 접근하기 위해 이동 객체의 처음 세그먼트와 마지막 세그먼트가 저장된 리프 노드를 가리키는 포인터 정보와 더불어 디스크에서의 페이지를 가리키는 페이지 번호를 별도의 테이블에 같이 유지한다. 따라서, 저장시 동일한 이동 객체의 선행노드를 빨리 검색할 수 있고, 궤적 질의시 직접적으로 디스크에 접근해 해당 객체의 궤적들을 검색함으로써 검색 성능을 향상시킬 수 있다. 아울러 ETB 트리는 새로운 이동 객체의 궤적 정보가 삽입될 때마다 메모리 상의 트리뿐만 아니라 디스크에 반영함으로써 트리의 일관성을 유지한다.

비디오 데이터에서 움직임 경로의 효율적인 검색을 위한 시그니쳐 - 기반 접근 기법

심춘보(Choon-Bo Shim),장재우(Jae-Woo Chang) 한국정보과학회 2001 한국정보과학회 학술발표논문집 Vol.28 No.2Ⅰ

본 논문에서는 비디오 데이터가 지니는 움직임 객체의 움직임 경로(Moving Objects' Trajectories)를 이용한 사용자 질의에 대해 효율적인 검색을 위한 새로운 시그니쳐-기반 접근 기법을 제안한다. 제안하는 시그니쳐 기반 접근 기법은 데이터 파일을 직접 접근하기 전에 전체 시그니쳐들을 탐색하여 필터링을 수행하기 때문에, 순차 탐색에 비해 디스크 접근 횟수를 감소시켜 검색 성능을 향상시킨다. 마지막으로, 성능 평가를 통해 제안하는 방법이 삽입 시간, 검색 시간, 그리고 부가 저장 공간의 검색 효율(Retrieval Efficiency) 측면에서 성능이 우수함을 보인다.

비디오 데이타에서 움직임 객체의 모델링을 위한 시공간 표현 기법

심춘보(Choon-Bo Shim),장재우(Jae-Woo Chang) 한국정보과학회 2000 정보과학회논문지 : 데이타베이스 Vol.27 No.4

비디오 데이타에서 움직임 객체에 대한 움직임 경로는 내용-기반 검색을 위해 비디오 데이타를 색인하는 데 있어 매우 중요한 역할을 한다. 따라서, 본 논문에서는 비디오 데이타에서 움직임 객체의 움직임 경로를 모델링하기 위한 새로운 시공간 표현 기법을 제안한다. 비디오 데이타를 위한 보다 효율적인 내용-기반 검색을 위해, 제안하는 기법은 시간, 공간 관계성과 더불어 일정 시간 간격 동안 움직인 객체의 이동 거리(moving distance)를 고려한다. 아울러, 제안하는 표현 기법에 기반하여 단일 움직임 객체의 움직임 경로와 다수 움직임 객체들의 움직임 경로를 위한 새로운 유사성 측정 알고리즘을 제시하며, 이들 알고리즘은 검색 결과에 대해서 유사성에 준하여 순위(Ranking)를 부여할 수 있다. 마지막으로, 성능 평가를 통하여 제안된 시공간 표현 기법은 기존의 Li 방법과 Shan의 방법에 비해 동등한 재현율을 유지하며, 정확율 측면에서 약 20%의 성능 향상을 보인다. The trajectory of moving objects in video data plays an important role in video indexing for content-based retrieval. In this paper, we propose a new spatio-temporal representation scheme for modeling moving objects‘ trajectories in video data. In order to support content-based retrieval on video data very well, our representation scheme considers the moving distance of an object during a given time interval as well as its temporal and spatial relations. Based on our representation scheme, we present two similarity measure algorithms for both the trajectory of a single moving object and those of multiple moving objects, which provide ranking for the retrieved video results. Finally, we show from our experiment that our representation scheme achieves about 20% higher precision while it holds about the same recall, compared with its competitors, both Li‘s and Shan's schemes.

비디오 데이터베이스에서 이동 객체의 유사 부분 움직임 궤적을 위한 N-워핑 검색

심춘보(Choon-Bo Shim),장재우(Jae-Woo Chang) 한국정보과학회 2002 한국정보과학회 학술발표논문집 Vol.29 No.1B

본 논문에서는 비디오 데이터가 지니는 이동 객체의 움직임 궤적(moving objects′ trajectories)에 대해 유사 부분 움직임 궤적 검색을 효율적으로 지원하는 N-워핑(N-warping) 알고리즘을 제안한다. 제안하는 알고리즘은 기존의 시계열 데이터베이스에서 유사 서브시퀀스 검색을 위해 사용되었던 타임 워핑 변환 기법(time-warping transformation)을 변형한 알고리즘이다. 또한 제안하는 알고리즘은 움직임 궤적을 모델링하기 위해 사용되는 단일 속성(property)인 각도뿐만 아니라, 거리와 시간과 같은 다중 속성을 지원하며, 사용자 질의에 대해 유사 부분 움직임 궤적 검색을 가능하게 하는 근사 매칭(approximate matching)을 지원한다.

비디오의 움직임 객체를 위한 새로운 시공간 표현 기법의 설계

심춘보(Choon-Bo Shim),김남기(Nam-Gi Kim),장재우(Jae- Woo Chang) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.1B

이미지와는 달리, 비디오 데이터는 객체에 대한 움직임 정보(motion trajectory)를 가지고 있으며, 이러한 움직임 정보는 비디오 데이터만이 가지는 매우 중요한 특징으로 비디오 데이터에 대한 색인과 내용 기반 검색을 수행하는 데 있어 중요한 역할을 한다. 따라서, 본 논문에서는 비디오 데이터베이스에서 효율적인 내용기반 검색을 위해 하나의 객체에 대한 움직임 정보를 나타내는 single motion trajectory와 두 객체에 대한 움직임 정보를 나타내는 multiple motion trajectory를 위한 새로운 시공간 표현 기법을 제안한다. 아울러 움직임 정보에 대한 사용자 질의에 대해 유사성을 측정하여 순위 부여와 Time Interval을 지원하는 새로운 유사성 측정 알고리즘인 SIST와 SIMT를 제안한다.