시공간 데이타베이스에서 영역 합 질의를 위한 색인 기법

조형주(Hyung-Ju Cho),최용진(Yong-Jin Choi),민준기(Jun-Ki Min),정진완(Chin-Wan Chung) 한국정보과학회 2005 정보과학회논문지 : 데이타베이스 Vol.32 No.2

시공간 데이타베이스는 최근에 많은 주목을 받았지만, 영역 합 질의에 대한 연구는 그 중요성에 비하여 많이 부족하다. 영역 합 질의를 처리하기 위하여, 많은 양의 데이타에 대한 직접적인 접근은 엄청난 계산 비용을 야기하기 때문에, 최근에 기존 색인 기법을 활용한 materialization 방법이 제안되었다. 간단하면서 효과적인 방법은 시공간 조건을 가지는 윈도우 질의를 효율적인 처리하는 MVR-tree에 materialization 방법을 적용하는 것이다. 그러나, MVR-tree는 노드들 사이의 존재하는 원형 경로 때문에, 중간 노드에 미리 계산된 합을 유지하는 것이 불가능하다. 다른 색인 구조들에 기초한 집합적 구조(aggregate structures)는 만족스러운 질의 성능을 제공하지 못 한다. 본 논문에서는 적응적 분할 기법을 사용하는 새로운 색인 기법(Adaptive Partitioned Aggregate R-Tree, APART)과 다양한 환경에서 영역 합 질의를 효율적으로 처리하는 질의 처리 알고리즘을 제안한다. 실험 결과는 APART의 성능이 다양한 상황에서 기존의 집합적 색인 기법들보다 2배 이상 우월하다는 것을 보여준다. Although spatio-temporal databases have received considerable attention recently, there has been little work on processing range sum queries on the historical records of moving objects despite their importance. Since to answer range sum queries, the direct access to a huge amount of data incurs prohibitive computation cost, materialization techniques based on existing index structures are recently suggested. A simple but effective solution is to apply the materialization technique to the MVR-tree known as the most efficient structure for window queries with spatio-temporal conditions. However, the MVR-tree has a difficulty in maintaining pre-aggregated results inside its internal nodes due to cyclic paths between nodes. Aggregate structures based on other index structures such as the HR-tree and the 3DR-tree do not provide satisfactory query performance. In this paper, we propose a new indexing technique called the Adaptive Partitioned Aggregate R-Tree (APART) and query processing algorithms to efficiently process range sum queries in many situations. Experimental results show that the performance of the APART is typically above 2 times better than existing aggregate structures in a wide range of scenarios.

UML 클래스 다이어그램 기반의 효율적인 C++코드 생성기의 설계와 구현

조형주(Hyung-Ju Cho),정진완(Chin-Wan Chung),김형주(Hyoung-Joo Kim) 한국정보과학회 2000 정보과학회 컴퓨팅의 실제 논문지 Vol.6 No.4

UML은 OMG에 의해서 표준 객체지향 모델링 언어로 승인 받았다. 그러나, UML을 지원하는 몇몇의 CASE 도구들이 생성한 C++ 코드는 1대 n 관계나 aggregation 관계의 의미를 정확히 반영하지 못하고 있다. 또한, 상용 CASE 도구들이 하나의 UML 클래스 다이어그램에서 너무 많은 프로그래밍 언어를 지원하기 때문에, 그들은 C++언어가 가지는 특징을 효율적으로 지원하지 못하고 있다. 제안된 C++코드 생성기는 1대 n의 관계, aggregation 관계, 코드 패턴(code pattern), 디자인 패턴(design pattern)을 지원한다. 본 논문에서는 UML 클래스 다이어그램 기반의 효율적인 C++ 코드 생성기의 설계와 구현에 대하여 기술한다. The Unified Modeling Language(UML) became the standard object oriented modeling langauge approved by Object Management Group(OMG). However, C++ codes which are generated by some CASE tools supporting UML do not reflect the correct semantics of one-to-many relationship and aggregation relationship. Additionally, since the commercial CASE tools support too many programming languages on one UML class diagram, they do not support efficiently the characteristics of C++ language. Our C++ code generator supports one-to-many relationship, aggregation relationship, code patterns and design patterns. In this paper, we describe design and implementation of the efficient C++ code generator based on UML class diagram.

A Batch Processing Algorithm for Moving k-Nearest Neighbor Queries in Dynamic Spatial Networks

Hyung-Ju Cho(조형주) 한국컴퓨터정보학회 2021 韓國컴퓨터情報學會論文誌 Vol.26 No.4

위치 기반 서비스(LBS)는 가장 바쁜 시간에 동시에 도착하는 최단 경로 및 k-최근접 이웃 질의를 포함한 다양한 공간 질의를 효과적으로 처리한다. 동시에 도착하는 공간 질의를 빠르게 처리하기 위한 간단한 해결 방법은 LBS 서버를 추가하는 것이다. 이 방법은 서비스 운영 비용을 많이 증가시킨다. 최근에는 공유 가능한 계산을 사용하여 일련의 질의를 한꺼번에 모아서 처리하는 일괄 처리 방법이 제안되었다. 본 연구에서는 교통 상황에 따라 각 도로 구간의 이동 시간이 빈번하게 변하는 동적 공간 네트워크에서 움직이는 k-최근접 이웃 질의를 한꺼번에 처리하는 방법을 연구한다. 순차적 질의 처리를 기반으로 하는 LBS 서버는 중복 계산으로 인해 한꺼번에 요청이 들어오는 움직이는 k-최근접 이웃 질의를 효과적으로 처리하지 못한다. 본 연구의 목표는 움직이는 k-최근접 이웃 질의를 한꺼번에 처리하고 공유 가능한 계산을 재사용하여 알고리즘을 효율성을 개선한다. 실제 지도 데이터를 사용한 실험 평가는 최신 방법보다 제안된 방법이 우수하다는 것을 보여준다. Location-based services (LBSs) are expected to process a large number of spatial queries, such as shortest path and k-nearest neighbor queries that arrive simultaneously at peak periods. Deploying more LBS servers to process these simultaneous spatial queries is a potential solution. However, this significantly increases service operating costs. Recently, batch processing solutions have been proposed to process a set of queries using shareable computation. In this study, we investigate the problem of batch processing moving k-nearest neighbor (MkNN) queries in dynamic spatial networks, where the travel time of each road segment changes frequently based on the traffic conditions. LBS servers based on one-query-at-a-time processing often fail to process simultaneous MkNN queries because of the significant number of redundant computations. We aim to improve the efficiency algorithmically by processing MkNN queries in batches and reusing sharable computations. Extensive evaluation using real-world roadmaps shows the superiority of our solution compared with state-of-the-art methods.

다차원 색인 구조를 위한 효율적인 압축 방법

조형주(Hyung-Ju Cho),정진완(Chin-Wan Chung) 한국정보과학회 2003 정보과학회논문지 : 데이타베이스 Vol.30 No.5

지난 십년 동안, CPU의 발전 속도는 메모리나 디스크의 발전 속도를 훨씬 능가하였다. 이것이 압축 방법을 사용하여 데이타베이스 크기를 줄이거나 질의 비용을 줄일 수 있게 만들었다. 다양한 데이타베이스 연구 분야에서 압축 방법이 사용되고 있지만, 다차원 색인 구조를 압축하는 연구는 거의 없다. 본 논문에서는 다차원 색인 구조를 위한 HEM(Hybrid Encoding Method)이라는 압축 방법을 제안한다. HEM 압축 방법은 다차원 색인 구조의 크기 뿐만 아니라, 질의 비용도 크게 줄일 수 있다. 수학적인 분석과 다양한 실험을 통하여, 우리는 HEM 압축 방법이 기존에 제안되었던 압축 방법보다 색인 크기와 질의 비용 측면에서 우수하다는 것을 보여준다. Over the last decades, improvements in CPU speed have greatly exceeded those in memory and disk speeds by orders of magnitude and this enabled the use of compression techniques to reduce the database size as well as the query cost. Although compression techniques are employed in various database researches, there is little work on compressing multi-dimensional index structures. In this paper, we propose an efficient compression method called the hybrid encoding method (HEM) that is tailored to multi-dimensional indexing structures. The HEM compression significantly reduces the query cost and the size of multi-dimensional index structures. Through mathematical analyses and extensive experiments, we show that the HEM compression outperforms an existing method in terms of the index size and the query cost.

AI를 활용한 손가락 인식 및 가상 터치 서비스

조아라 ( A-ra Cho ),유승배 ( Seung-bae Yoo ),윤병훈 ( Byeong-hun Yun ),조형주 ( Hyung-ju Cho ),하광림 ( Gwang-rim Ha ) 한국정보처리학회 2023 한국정보처리학회 학술대회논문집 Vol.30 No.2

코로나-19로 인해 비접촉 서비스의 중요성이 더욱 대두되고 있다. 키보드나 마우스와 같은 기존 입력 장치를 대체하기 위해 사람들은 디지털 기기에서 손을 사용하여 자연스럽고 간단한 입력을 할 수 있게 되었다. 본 논문에서는 미디어파이프(MediaPipe)와 LSTM(Long Short-Term Memory) 딥러닝을 활용하여 손 제스처를 학습하고 비접촉 입력 장치로 구현하는 방법을 제시한다. 이러한 기술은 가상현실(VR; Virtual Reality), 증강현실(AR; Augmented Reality), 메타버스, 키오스크 등에서 활용 가능성이 크다.

A Heuristic Approach for Protecting NAND Flash Memory against Laboratory Attacks

Yared Hailu(야레드 하이루),Hyung-Ju Cho(조형주),Tae-Sun Chung(정태선) 한국정보과학회 2012 한국정보과학회 학술발표논문집 Vol.39 No.2C

플래시 메모리 처리 지연 개선을 위한 가비지 컬렉션 중심의 FTL

최승권(Seung-kwon Choe),조형주(Hyung-Ju Cho),정태선(Tae-Sun Chung) 한국정보과학회 2013 정보과학회논문지 : 시스템 및 이론 Vol.40 No.4

플래시 메모리는 빠른 속도와 저 전력 소비, 뛰어난 내구성 그리고 높은 휴대성의 장점을 가지고 있다. 이러한 장점을 가지고 있는 반면, 쓰기 전 지우기(erase before write)를 수행해야 하는 제약을 가지고 있다. 이와 같은 하드웨어적 제약을 극복하고, 호스트로부터 요구되는 데이터의 읽기/쓰기 명령(read/write operation)효율적으로 수행하기 위해서는 플래시 변환 계층(FTL: flash translation layer)이 필요하다. FTL의 합병 연산(merge operation)으로 인해 발생하는 처리 지연(processing delay)은 플래시 메모리의 외부에서 예측하기 어렵다. 따라서 제한된 시간 내에 태스크(task)를 수행해야 하는 실시간 시스템(real-time system)에 대해 일정한 응답 시간(response time)을 보장하기 어렵다. 본 논문에서는 가장 오래된 유효 페이지에 대해 적극적인 합병을 수행하고, 비교적 최근에 갱신이 이루어진 유효 페이지를 재배치하는 가비지 컬렉션 중심의 FTL (GCC-FTL: Garbage Collection-Centric FTL)을 제안한다. 이를 통해 FTL의 합병 연산을 분해하여 최대 처리 시간을 제한할 수 있다. Flash memory has the advantage of high speed and low power consumption, superior durability, and high portability. However, it has a constraint which it has to erase before write operation. In order to overcome the constraint and achieve good performance to the data read/write operation required from host, it needs FTL (Flash Translation Layer). The host cannot expect the processing delay caused by merge operation in FTL. Thus, it cannot assure the stable response time in real time system which should complete a task until the deadline. In this paper, we propose the GCC-FTL (Garbage Collection-Centric FTL) scheme which performs active merge operation to the available oldest pages and reallocate the relatively renewed valid pages.

방향성이 있는 동적인 도로에서 실시간 최단 경로 탐색 시스템의 설계와 구현

권오성(Oh-Seong Kwon),조형주(Hyung-Ju Cho) 한국멀티미디어학회 2017 멀티미디어학회논문지 Vol.20 No.4

위치 불확실성을 가진 이동 객체에 대한 k 최근접 질의 에 대한 확률적인 접근 방법

권오성(Oh-Seong Kwon),조형주(Hyung-Ju Cho) 한국정보과학회 2015 한국정보과학회 학술발표논문집 Vol.2015 No.12

Efficient Processing of k-Farthest Neighbor Queries for Road Networks

Taelee Kim(김태이),Hyung-Ju Cho(조형주),Hee Ju Hong(홍희주),Hyogeun Nam(남효근),Hyejun Cho(조혜준),Gyung Yoon Do(도경윤),Pilkyu Jeon(전필규) 한국컴퓨터정보학회 2019 韓國컴퓨터情報學會論文誌 Vol.24 No.10

본 연구에서는 도로 네트워크에서 k-최원접 이웃 검색을 위한 효율적인 FANS(k-FArthest Neighbor Search) 알고리즘을 제안한다. 양의 정수 k, 질의 객체 q, 일련의 데이터 객체 집합 P가 주어지면, k-최원접 이웃 질의는 질의 객체 q에서 가장 멀리 있는 k개의 데이터 객체를 찾는다. 데이터베이스 분야에서 대부분의 연구는 k-최근접 이웃 질의에 중점을 두고 있어서, k-최원접 이웃 질의라는 중요한 근접 질의유형은 별다른 관심을 받지 못했다. 이 논문에서는 도로 네트워크에서 가장 멀리 있는 이웃을 찾는 문제를 다룬다. 도로 네트워크에서 k-최원접 이웃 질의를 처리하는 연구는 거의 없었다. 도로 네트워크에서 k-최원접 이웃 질의를 처리해야 하는 문제는 최단 경로 거리를 계산하는 횟수를 줄이는 것인데, 이는 도로 네트워크와 유클리드 공간의 질의 처리에서 가장 중요한 차이다. 질의 객체와 데이터 객체 사이의 최단 경로 거리에 대한 중복 계산을 줄이기 위하여 공유 계산 전략을 사용한다. 질의 객체에서 데이터 세그먼트까지 최대 거리를 기반으로 효과적으로 후보군을 제거하는 방법은 제시한다. 마지막으로 실제 도로 지도를 사용한 광범위한 실험을 통해 제시된 방법의 효율성과 확장성을 보여준다. While most research focuses on the k-nearest neighbors (kNN) queries in the database community, an important type of proximity queries called k-farthest neighbors (kFN) queries has not received much attention. This paper addresses the problem of finding the k-farthest neighbors in road networks. Given a positive integer k, a query object q, and a set of data points P, a kFN query returns k data objects farthest from the query object q. Little attention has been paid to processing kFN queries in road networks. The challenge of processing kFN queries in road networks is reducing the number of network distance computations, which is the most prominent difference between a road network and a Euclidean space. In this study, we propose an efficient algorithm called FANS for k-FArthest Neighbor Search in road networks. We present a shared computation strategy to avoid redundant computation of the distances between a query object and data objects. We also present effective pruning techniques based on the maximum distance from a query object to data segments. Finally, we demonstrate the efficiency and scalability of our proposed solution with extensive experiments using real-world roadmaps.