다중 공간 조인의 병렬 처리

류우석(WooSeok Ryu),홍봉희(BongHee Hong) 한국정보과학회 2000 정보과학회논문지 : 데이타베이스 Vol.27 No.2

GIS에서 사용하는 다중 공간 조인은 두 개 이상의 공간 조인이 중첩된 표현이다. 이는 공간 조인에 비해 보다 많은 수행 시간을 필요로 하는데 이를 빠르게 처리하기 위한 병렬화 알고리즘에 대한 연구가 없었다. 이 논문에서는 다중 공간 조인을 다중 공간 여과와 다중 공간 정제로 나누어서 병렬화한다. 그리고, 정제 단계에서 효율적인 정제 수행을 위해 2단계 실행 방법을 제시하는데, 첫번째가 다중 공간 여과의 결과인 후보 객체 테이블에서 발생하는 객체 및 연산의 중복을 제거하기 위한 그래프 생성이고, 두번째가 그래프의 분할에 의한 병렬 정제이다. 그래프에 의한 정제가 그렇지 않은 방법에 비해 매우 높은 성능 향상을 보였으며 병렬 정제를 위한 태스크 생성 방법은 객체를 정점으로 표현하는 그래프에서의 중복 최소화 분할방법이 가장 좋은 성능을 나타내었다. Multi-way spatial join is a nested expression of two or more spatial joins. It costs much to process multi-way spatial join, but there have not still reported the scheme of parallel processing of multi-way spatial join. In this paper, parallel processing of multi-way spatial join consists of parallel multi-way spatial filter and parallel spatial refinement. Parallel spatial refinement is executed by the following two steps. The first is the generation of a graph used for reducing duplication of both spatial objects and spatial operations from pairs candidate object table that are the results of multi-way spatial filter. The second is the parallel spatial refinement using that graph. Refinement using the graph is proved to be more efficient than the others. In task creation for parallel refinement, minimum duplication partitioning of the Spatial_Object_On_Node graph shows best performance.

RFID 태그 메모리 접근의 일관성을 위한 태그 연산의 동시성 제어

류우석(Wooseok Ryu),홍봉희(Bonghee Hong) 한국정보과학회 2010 정보과학회논문지 : 데이타베이스 Vol.37 No.3

본 논문에서는 RFID 전자태그에 부착된 메모리의 정보를 접근할 때 발생하는 태그 연산 실행의 불완전성에 따른 태그 데이터의 불일치 문제를 분석하고, 이를 해결하기 위한 프로토콜을 제안한다. 수동형 RFID 태그는 통신의 불확실성과 단절성으로 인해 태그 메모리 접근연산의 완전한 실행을 보장하지 못하므로, 불완전하게 실행된 연산으로 인해 태그 데이터의 비일관성을 초래하는 문제가 발생한다. 본 논문에서는 태그 접근의 일관성을 유지하면서 불완전 연산의 실행을 완료시키기 위한 동시성 제어 프로토콜을 제안한다. 이 프로토콜은 불완전 실행된 연산의 대상태그를 연속질의로 정의하고 태그의 인식을 모니터링 함으로써 다른 연산들에 의한 불확실 데이타의 접근을 차단하고, 재수행을 통해 불완전하게 실행된 연산의 수행을 완료시킨다. 또한, 증명을 통해 제안한 프로토콜의 정확성, 일관성을 입증하였으며, 실험을 통해 본 프로토콜이 기존의 일관성 유지기법보다 좋은 성능을 나타냄을 보였다. This paper analyzes the tag data inconsistency problem caused by incomplete execution of the tag access operation to the RFID tag’s memory and proposes a protocol to control consistent tag data accesses with finalizing the incomplete operation. Passive RFID tag cannot guarantee complete execution of the tag access operations because of uncertainty and unexpected disconnectionof RF communications. This leads to the tag data inconsistency problem. To handle this, we proposea concurrency control protocol which defines incomplete tag operations as continuous queries and monitors the tags’ re-observation continuously. The protocol finalizes the incomplete operation when the tag is re-observed while it blocks inconsistent data accesses from other operations. We justify the proposed protocol by analyzing the completeness and consistency. The experiments show that the protocol shows better performance than the traditional lock-based concurrency control protocol.

6 개의 목표 주파수에서 특정 워크 비를 가지는 진동 에너지 하베스터

류우석(Wooseok Ryu),최용제(Yong Je Choi) 한국소음진동공학회 2020 한국소음진동공학회 학술대회논문집 Vol.2020 No.6

[우수논문] RFID 미들웨어 평가를 위한 테스트 데이터셋의 품질 지표

류우석(Wooseok Ryu),권준호(Joonho Kwon),홍봉희(Bonghee Hong) 한국정보과학회 2012 한국정보과학회 학술발표논문집 Vol.39 No.1B

RFID 미들웨어의 평가를 위한 방법으로서, 테스트 데이터셋을 이용한 시뮬레이션은 일반적으로 사용되는 평가 방법이다. 태그 식별자에 따라 순차생성된 가상 데이터셋이나 랜덤 생성된 데이터셋의 경우 미들웨어의 단순 처리량을 평가하기에는 유용하나 미들웨어의 정확성이나 실행 가능성를 평가하기에는 한계가 있다. 테스트 데이터셋은 실제 리더에서 생성된 데이터셋과 매우 유사하여야 함에도 불구하고, 테스트 데이터셋의 품질 기준이 정의되어 있지 않음에 따라 테스트 데이터셋이 얼마만큼 실제 데이터셋과 유사한 지를 평가하기가 어려운 문제가 있다. 이를 위해 본 논문에서는 RFID 미들웨어의 평가에 사용되는 테스트 데이터셋의 품질을 평가하기 위한 품질 지표를 제안한다. 제안하는 품질 지표는 실제 RFID 리더에 태그가 통과할 때 생성되는 데이터 셋을 기반으로 하여 정의하였으며, RFID 무선 인식의 고유의 특성, 즉 중복성과 불확실성을 수치화해서 표현하는 특징이 있다. 또한 제안한 품질 지표를 실제 RFID 리더를 통해 생성한 데이터셋에 적용하여 비교 검토함으로써 품질 지표의 유용성을 입증한다.

다양한 물류정보소자를 위한 통합형 RFID 미들웨어 아키텍처

류우석(Wooseok Ryu),안성우(Sungwoo Ahn),김기홍(Gihong Kim),추병조(Byungjo Chu),이준호(Junho Lee),정동규(Donggyu Jung),서배훈(Baehoon Seo),홍봉희(Bonghee Hong) 한국통신학회 2008 한국통신학회 학술대회논문집 Vol.2008 No.7

병렬 다중 공간 조인 알고리즘의 구현 및 성능평가

류우석(Ryu Wooseok),김진덕(Kim Jindeog),홍봉희(Hong Bonghee) 한국정보과학회 1998 한국정보과학회 학술발표논문집 Vol.25 No.2Ⅰ

지리 정보 시스템에서 다중 공간 조인과 같은 많은 기하 계산을 필요로 하는 질의를 처리하기 위해서는 질의에 대한 병렬화 작업을 통해 실행 시간을 최소화 하는 것이 필수적이다. 다중 공간 조인은 정제에서 많은 시간을 소비하므로 여과와 정제를 분리하여 각각을 수행하는 것이 정제 시간을 단축하게 되고 따라서 좋은 성능을 나타낼 수 있다. 그러므로 다중 공간 조인을 병렬화 하기 위해서는 다중 공간 여과와 정제 각각에 대해 병렬 실행 계획을 세우는 것이 중요하다. 이 논문에서는 우선적으로 병렬 공간 여과를 수행하기 위한 두가지 알고리즘, 즉 bush tree을 사용한 다중 공간 여과와 pipelining을 사용한 다중 공간 여과의 병렬화를 비교한다. 그리고, 다중 공간 여과의 결과로서 생성되는 중간 결과 테이블에서 데이터의 중복에 따른 정제 성능의 저하가 발생되는데, 이를 효율적으로 제거하기 위한 두가지 그래프 생성 알고리즘을 제안하고 이를 비교한다. 그리고, 생성된 그래프에서 병렬 정제를 수행하기 위한 여러 가지 분할 알고리즘을 제안하고 이를 비교 평가한다. 이런 일련의 작업을 통해 우수한 성능의 병렬 다중 공간 조인 방법을 제안하고 성능 평가를 통해 최적의 병렬 수행 방법을 도출한다.

두 강체로 이루어진 대칭 진동 시스템 진동 모드의 기하적 해석

류우석(Wooseok Ryu),최용제(Yong Je Choi) 한국소음진동공학회 2018 한국소음진동공학회 학술대회논문집 Vol.2018 No.10

RFID 태그의 이력 추적을 위한 시간 간격 색인 : SLR-트리

류우석(Wooseok Ryu),안성우(Sungwoo Ahn),홍봉희(Bonghee Hong),반재훈(Chaehoon Ban),이세호(Seho Lee) 한국정보과학회 2007 정보과학회논문지 : 데이타베이스 Vol.34 No.1

The trajectory of a tag in RFID system is represented as a interval that connects two spatiotemporal locations captured when the tag enters and leaves the vicinity of a reader. Whole trajectories of a tag are represented as a set of unconnected interval because the location of the tag which left the vicinity of a reader is unknown until it enters the vicinity of another reader. The problems are that trajectories of a tag are not connected. It takes a long time to find trajectories of a tag because it leads to searching the whole index. To solve this problem, we propose a technique that links two intervals of the tag and an index scheme called SLR-tree. We also propose a sharing technique of link information between two intervals which enhances space utilization of nodes, and propose a split policy that preserves shared-link information. And finally, we evaluate the performance of the proposed index and prove that the index processes history queries efficiently. RFID 시스템에서의 태그의 궤적은 태그가 리더의 인식영역에 들어왔을 때와 벗어날 때의 시공간 위치를 선분으로 연결하여 표현한다. 그러나 태그가 리더의 인식영역을 벗어난 후 다음 리더의 인식 영역에 들어올 때까지는 태그의 위치를 파악할 수 없으므로 태그의 궤적은 연결되어 있지 않고 단절된 간격의 집합으로 표현된다. 그러므로 태그의 이력을 검색하기 위해서는 전체 색인을 검색해야 하는 문제가 발생한다. 이 논문에서는 높은 궤적 검색 비용문제를 해결하기 위해 전자태그의 간격을 연결하기 위한 기법을 제시하고 이 기법을 적용한 색인인 SLR-tree를 제안한다. 또한, 연결 정보의 추가로 인한 노드의 공간 활용도의 저하를 최소화하기 위하여 두 간격간의 연결정보를 공유하기 위한 기법을 제안하고 노드의 분할 시 공유정보를 유지하기 위한 분할 정책을 제안한다. 마지막으로 제안된 색인에 대한 성능을 비교평가 함으로써 이력검색 성능의 우수성을 입증한다.

능동형 센서 태그를 위한 미들웨어 플랫폼의 설계 및 구현

류우석(Wooseok Ryu),김현우(Hyunwoo Kim),홍봉희(Bonghee Hong) 한국정보과학회 2011 정보과학회논문지 : 데이타베이스 Vol.38 No.4

본 논문은 RFID 미들웨어의 국제 표준에서 능동형 센서 태그의 처리시 발생하는 문제점을 분석하고, 이를 극복하기 위한 확장 플랫폼을 제안한다. Application Level Events(ALE) 명세서는 RFID 미들웨어에 대한 표준 인터페이스들을 정의하고 있으며 RFID 데이터에 대한 정제(Filtering)와 수집(Collection) 메커니즘을 기술하고 있다. 그러나, 이 표준 명세서는 수동형 태그와 달리 내부 배터리를 사용하는 능동형 태그 지원에 대한 고려가 되어있지 않아서 반복적 데이터 수집으로 인한 능동형 태그의 내부 배터리 고갈 문제를 야기하며, 경보(Alert) 이벤트와 같은 비동기 통신을 지원하지 못하는 문제가 발생한다. 이를 위해 본 논문은 국제 표준 명세서의 분석을 통해 능동형 센서 태그를 지원하기 위한 요구사항을 정의하고, 이를 위한 확장 인터페이스(API)를 제안한다. 제안하는 확장 인터페이스는 능동형 센서 태그의 비동기적인 경보 이벤트들을 처리하기 위한 Notification API, 그리고, 능동형 센서 태그의 반복적인 데이터 수집을 억제하기 위한 기존 표준 명세의 확장으로 구성된다. 본 논문은 기존 RFID 미들웨어의 국제표준에 근거한 확장 플랫폼을 제안함으로써, 수동형 태그를 지원하는 표준 미들웨어에 더하여 능동형 센서 태그의 처리를 통해 다양한 태그의 효율적인 처리 수행의 개선에 기여함을 확인하였다. This paper discusses the problem of handling active RFID tags under standard RFID middleware and proposes an extended platform for supporting active tags. The Application Level Events specification provides standard APIs for the RFID middleware. The basic roles of the specification are filtering and collection for the RFID data. However, it does not consider characteristics of active sensor tags such that repeated requests to the active tags will exhaust the internal battery of the tags. Moreover, the specification does not support the asynchronous communication, such as alert event which is a unique feature of the active sensor tags. This paper proposes an extended RFID middleware platform to support handling of the active sensor tags. To do this, we present new APIs for handling active tags based on Application Level Events 1.1 specification. The designed Notification API and ANSpec provide the way to get notification messages asynchronously from the active tags. We also provide extended APIs which enables discreet query to the active tags for reducing repeat reports. The implementation shows that the extended middleware platform generates alert event for the active tags. The main contributions of this paper are to define an extended APIs and develop a middleware platform for handing active tags as well as supporting passive tags.

RFID 미들웨어 테스트를 위한 RFID 데이터셋의 품질 평가 지표

류우석(Wooseok Ryu),홍봉희(Bonghee Hong),권준호(Joonho Kwon) 한국정보과학회 2012 정보과학회논문지 : 소프트웨어 및 응용 Vol.39 No.11

RFID 미들웨어의 성능 평가시 실제 장비를 이용하는 것은 고비용이 요구됨에 따라, 테스트 데이터셋을 이용한 시뮬레이션 테스팅이 널리 사용되고 있다. 이때, 부하 테스트에서 벗어나 미들웨어의 정확성을 검증하기 위해서는 테스트에 사용되는 데이터셋이 실제 리더에서 생성된 데이터셋과 유사하여야 한다. 하지만, 데이터셋을 서로 비교하거나 또는 데이터셋의 특성을 파악하기 위한 기준이 제시되어 있지 않음으로 인해 테스트 데이터셋의 품질을 객관적으로 평가하기가 매우 어렵다. 이를 위해 본 논문에서는 RFID 데이터셋인 물리 이벤트 데이터셋, 논리 이벤트 데이터셋 각각에 대해 품질을 평가하기 위한 다양한 품질 지표를 제안한다. 제안하는 품질 지표들은 중복성, 불확실성과 같은 실제 RFID 데이터셋의 특징을 분석하고 이들을 수치화함으로써 객관적인 비교 평가가 가능한 특징이 있다. 그리고, 실제 RFID 데이터셋과 가상 데이터셋을 대상으로 제안한 품질 지표를 이용하여 비교 평가하는 실험을 통해 품질 지표의 효용성과 유용성을 입증한다. Simulation-based testing with test datasets is a general approach to evaluate RFID middleware since testing with RFID devices requires huge cost. To evaluate correctness of RFID middleware in addition to performance of the middleware, the test dataset should be compatible with the real dataset which is obtained from real devices. Comparing two datasets or identifying features of a dataset is a difficult job because guidelines for measuring quality of the dataset are not given yet. To handle this, this paper proposes several quality metrics for two kinds of RFID dataset: physical event dataset and logical event dataset. Proposed metrics provide numerical measurements based on various characteristics of RFID dataset such as redundancy and uncertainty. Using them, it is possible to specify features of an RFID dataset as well as to compare two datasets. The experiments with real and virtual test dataset show usability and effectiveness of quality metrics.