상호 협동적 잠금 규약을 이용한 B link-트리 동시성 제어 기법

임성채,이윤준,김명호(Sung-Chae Lim),Yoon Joon Lee,Myoung Ho Kim 한국정보과학회 1997 정보과학회논문지(B) Vol.24 No.2

B-트리의 동시성을 높이기 위한 연구중에서 B^(link)-트리를 이용한 동시성 제어 기법이 많은 관심을 받아왔다. B^(link)-트리를 이용하는 기법은 다른 알고리즘과 비교하여 제공하는 동시성의 정도가 매우 높은 특성을 보이는 반면 키 삭제자의 트리 재구성 동작이 지원되지 않았던 문제가 있었다. 본 논문에서는 기존 B^(link)-트리를 이용한 알고리즘이 갖는 정도의 동시성을 보장하는 동시에 삭제자의 트리 재구성 동작을 허용하는 새로운 B^(link)-트리 동시성 제어 기법을 소개한다. 논문에서는 효과적인 B^(link)-트리 동시성 제어를 위해 상호 협동적인 잠금규약과 트리 재구성을 위한 노드 갱신 규칙을 이용한다. 제안되는 기법에서는 트리 재구성 작업이 다른 프로세스의 탐색 연산과 함께 진행될 수 있으며 알고리즘 수행중에 교착상태가 발생하지 않는다. For the purpose of improving B-tree concurrency, a number of algorithms have been proposed Among the previous works, the algorithms based on B^(link)-tree draw much attention, While such B^(link)-tree algorithms, in general, guarantee higher concurrency than others that do not use B^(link)-tree, they do not provide an efficient mechanism to reconstruct underflowed nodes. In this paper we present a new concurrency control method based on B^(link)-tree that provides high concurrency and an efficient reconstruction mechanism. A new locking protocol, called cooperative locking protocol, and a node modification rule for tree reconstruction are main contributions. In the proposed method, the tree reconstruction operations can concurrently proceed with search operations and any concurrent operations never result in deadlock.

효율적 범위 검색을 위한 플래시 메모리 기반 B+-트리

임성채(Sung-Chae Lim),박창섭(Chang-Sup Park) 한국콘텐츠학회 2013 한국콘텐츠학회논문지 Vol.13 No.9

지난 수십 년간 B+-트리는 디스크 기반 데이터베이스를 위한 색인 구조로 가장 널리 사용되고 있다. 디스크 기반 B+-트리에서의 노드 갱신은 해당 노드가 저장된 디스크 페이지를 제자리 갱신함으로써 간단히 수행되며, 이런 제자리 갱신 비용은 크지 않다. 반면에 B+-트리를 플래시 메모리에 저장하여 사용할 때는 플래시 메모리의 과도한 제자리 갱신 비용 문제로 인해 기존 디스크 기반 B+-트리 알고리즘을 그대로 사용하기 어렵다. 이런 이유로 기존 플래시 메모리 기반 B+-트리 연구에서는 실시간으로 발생하는 갱신 연산 정보를 추가적인 임시 공간에 저장하는 방식을 사용하였다. 이런 방식은 B+-트리의 제자리 갱신 횟수를 쉽게 줄일 수 있다는 장점이 있지만 저장 공간의 추가 사용과 키 검색 시간을 지연시킬 수 있다는 문제가 있다. 특히 단말노드 계층의 링크 연결을 사용한 범위 검색을 효과적으로 수행할 수 없다는 문제를 가지고 있다. 이런 문제점을 해결하기 위해 본 논문에서는 단말노드들과 이들의 부모노드를 p-node 블록이라는 하나의 플래시 메모리 블록에 저장할 수 있는 알고리즘을 제안한다. During the past decades, the B+-tree has been most widely used as an index file structure for disk-resident databases. For the disk based B+-tree, a node update can be cheaply performed just by modifying its associated disk page in place. However, in case that the B+-tree is stored on flash memory, the traditional algorithms of the B+-tree come to be useless due to the prohibitive cost of in-place updates on flash memory. For this reason, the earlier schemes for flash memory B+-trees usually take an approach that saves B+-tree changes from real-time updates into extra temporary storage. Although that approach can easily prevent frequent in-place updates in the B+-tree, it can suffer from a waste of storage space and prolonged search times. Particularly, it is not allowable to process range searches on the leaf node level. To resolve such problems, we devise a new scheme in which the leaf nodes and their parent node are stored together in a single flash block, called the p-node block.

연속매체 재연에 적합한 스케줄링 주기 확장을 허용하는 동적 Sweep 기법

임성채,Lim, Sung-Chae 한국정보처리학회 2005 정보처리학회논문지 A Vol.12 No.5

컴퓨터 성능 및 네트워크 기술의 발전으로 웹 상에서 연속매체(Continuous Media: CM)의 온라인 스트리밍(streaming) 서비스가 일반화 되었다. 이런 서비스를 위해서는 다양한 종류의 CM 스트림을 효과적으로 처리할 수 있어야 하며 이를 위해 Sweep 기법이 연구되었다. 이 기법은 끊김현상 없이 스트리밍 서비스를 할 수 있고 탐색지연 시간을 최적화 할 수 있다는 장점을 가지고 있다. 하지만 서비스 하고 있는 스트림의 스케줄링 주기를 사이클이라고 하는 단일한 크기로 맞춰야 하기 때문에 스케줄링의 유연성이 떨어지며, 이로 인해 발생하는 디스크 대역폭의 낭비가 매우 커질 수 있다는 문제를 가지고 있다. 논문에서는 이런 문제점을 해결하기 위해 CM 스트림의 스케줄링 주기를 동적으로 확장할 수 있는 기법을 연구하며, 이 기법에 적합한 새로운 승인제어 방식을 이용하여 끊김현상을 막는다. 논문에서는 제안된 기법의 성능상의 우수성을 보이기 위해 모의실험이 수행되었으며, 모의실험 결과를 통해 제안된 동적 Sweep 기법이 디스크 이용효율과 스케줄링 유연성의 측면에서 기존 Sweep 기법에 비해 우수한 특성이 있음을 알 수 있다. With fast advances in computing power and network technologies, online streaming services of continuous media (CM) have been popularly implemented on the Web. To implement such services, a variety of CM streams need to be processed efficiently, so that the Sweep scheme was proposed. This scheme has several advantages such as hiccup-free playbacks and seek-time optimization. In this scheme, however, the entire CM streams are scheduled with a single scheduling period, called a cycle. Since only one scheduling period is allowed in this scheme, a significant amount of disk time is usually wasted because of its inflexible disk schedules. To solve this, we propose a new dynamic Sweep scheme. For this, we devise an algorithm that is able to expand scheduling periods of serviced CM streams and propose a new admission control mechanism guaranteeing hiccup-free playbacks. To show performance gains, we execute various simulation experiments. From the experimental results, we can see that the proposed scheme outperforms the Sweep scheme in terms of disk utilization and scheduling flexibility.

6 · 25전쟁 기간 중 미국의 대한 군사정책이 한국해군력에 미친 영향

임성채(Lim, Sung-chae) 국방부 군사편찬연구소 2010 군사 Vol.- No.75

이동 기기에 적합한 소프트웨어 에이전트 기반의 효율적 체크포인팅 기법

임성채,Lim, Sung-Chae 한국정보처리학회 2008 정보처리학회논문지 A Vol.15 No.2

이동 통신 시스템의 발전과 함께 여러 대의 이동 기기에서 동작하는 분산 응용의 필요성이 점차 커지고 있다. 모바일 기기의 고장이나 통신망 단절이 기존 고정 통신망에 비해 자주 발생하는 환경을 고려할 때 모바일 응용을 위한 복구 기법이 매우 중요하며, 중단된 응용의 재시작을위해 체크포인팅이 널리 사용되고 있다. 본 논문에서도 이런 분산 응용의 복구를 위한 효율적 체크포인팅 기법을 제안한다. 제안된 기법에서는 MSS(Mobile Support Station)에서 동작하는 체크포인팅 에이전트라는 소프트웨어 에이전트를 사용한다. 이 에이전트는 R-distance(rollback-distance) 개념을 지원하며, 이를 통해 복귀되는 지역 체크포인트의 최대 개수를 한정할 수 있다. 제안된 방식은 기존의 문제점이었던 도미노 현상이나 체크포인트 유지에 필요한 추가 비용을 크게 줄이면서도 매우 유연한 방식의 체크포인트 생성을 지원할 수 있다. With the advance in mobile communication systems, the need for distributed applications running on multiple mobile devices also grows gradually. As such applications are subject to H/W failures of the mobile device or communication disruptions, compared to the traditional applications in fixed networks, it is crucial to develop any recovery mechanism suitable for them. For this, checkpointing is widely used to restart interrupted applications. In this paper, we devise an efficient checkpointing method that adopts the software agent executed at the mobile support station. The agent, called the checkpointing agent, is aimed at supporting the concept of rollback-distance (R-distance) that bounds the maximum number of roll-backed local checkpoints. By means of the R-distance, our method can prevent undesirable domino effects and heavy checkpoint overhead, while providing high flexibility in checkpoint creation.

마감시간을 고려한 유연성 있는 디스크 SCAN 알고리즘

임성채(Sung Chae Lim) 한국정보과학회 2009 한국정보과학회 학술발표논문집 Vol.36 No.2B

동영상이나 디지털 음악파일과 같이 일정 속도 이상으로 디스크 대역폭을 사용하는 응용이나, 시간 긴급성을 요하는 전자상거래 시스템에 대한 요구로 인해, 마감시간을 지키는 디스크 스케줄링 기법의 필요성이 커지고 있다. 본 논문에서는 SCAN 알고리즘에 기반한 유연한 실시간 디스크 스케줄링 알고리즘을 제안한다. 성능 비교를 위해 현재 사용되는 디스크 드라이브의 동작 속도를 모형화했으며, 시스템에 입력되는 디스크 요청들을 모의 실험하였다. 디스크 요청 비율이 증가함에 따라 변화하는 마감시간 위반비율을 측정함으로써 성능 평가를 수행했다. 제안된 알고리즘은 탐색지연시간을 최소화 하면서 마감시간을 지킬 수 있어 다른 알고리즘에 비해 매우 우수한 성능을 보였다.

대용량 데이터 색인에 적합한 역파일의 구현

임성채 ( Sung Chae Lim ) 한국정보처리학회 2008 한국정보처리학회 학술대회논문집 Vol.15 No.2

대용량 문서에 대한 키워드 검색을 위해 역파일(inverted-file) 색인 기법이 널리 쓰이고 있다. 역파일 색인 기법을 구현함에 있어 고려되어야 할 점은 키워드 검색 처리 시에 디스크 사용을 최소로 할 수 있는 방법이다. 크기가 작은 역파일이라면 디스크 I/O 사용도 작고 필요시 역파일을 메모리에 적재하여 둠으로써 디스크 사용을 크게 줄일 수 있다. 하지만, 웹 검색이나 규모가 큰 도서관 시스템에서와 같이 색인 데이터 크기가 매우 큰 경우 역파일을 읽는 디스크 비용이 급격히 증가할 수 있다. 본 논문에서는 매우 큰 크기의 역파일을 사용하는 검색 환경에서 디스크 사용을 최소로 할 수 있는 역파일 구조를 제안한다. 제안된 구조는 질의 처리 과정을 고려해 계층 구조로 설계되며 실제 상용 시스템에 적용되어 안정성 및 성능을 입증했다.

속도 변화가 빈번한 이동 객체의 미래 시점 위치 추정에 적합한 색인 기법

임성채(Sung-Chae Lim) 한국컴퓨터정보학회 2010 韓國컴퓨터情報學會論文誌 Vol.15 No.5

정보 기술과 이동 통신망의 발전에 따라 이동 객체의 위치 추적에 필요한 효과적인 색인 기법과 이를 통한 다양한 응용 서비스에 대한 사용자 요구가 커지고 있다. 이에 따라, 이동 객체의 현재 위치 추적과 미래 위치 추정에 사용되는 TPR*-트리와 같은 색인 기법이 관심을 받고 있다. TPR*-트리는 정적인 물체를 색인하기 위해 고안된 R-트리를 기본 구조로 하기 때문에, 갱신 비용이 크다는 단점이 있다. 따라서 이동 객체가 자주 속도나 위치 정보를 갱신하는 경우 트리 유지비용이 빠르게 증가할 수 있다. 특히, 이동 객체가 빠른 속도로 이동하는 경우 넓은 범위에 걸쳐 불필요한 노드 갱신이 발생할 수 있다는 문제점이 있다. 이런 문제점을 피하기 위해 논문에서는 루트노드의 자식노드에 이런 빠른 이동 속도의 객체만을 따로 색인하도록 하여 노드 갱신 비용을 크게 줄이는 방법을 제안한다. 제안된 방법을 통해 노드 갱신 비용을 최소화 하면서도 TPR*-트리의 장점을 유지할 수 있었다. 이런 성능상의 장점을 보이기 위해 시뮬레이션 기법을 사용한 성능 비교를 수행하였다. With the advances in the information technology and mobile communications, we now face increasing demands for various services based on both of position tracking of moving objects and their efficient index scheme. Accordingly, the TPR*-tree, which were proposed for efficiently tracking moving objects and predicting their positions in the future time, has drawn much intention. As the TPR*-tree came from the R-tree that is suitable for indexing static objects, it does not support cheap update costs. Therefore, it seems to be very costly to index moving objects if there are frequent occurrences of node updates caused by continuously changing velocities and positions. If some moving objects with high velocities have node updates, in particular, then the TPR*-tree may suffer from many unnecessary updates in the wide range of tree regions. To avoid such a problem, we propose a method that can keep fast-moving objects in the child nodes of the root node, thereby saving node update costs in the TPR*-tree. To show our performance advantages and retaining TPR*-tree features, we performed some performance experiments using a simulation technique.

링크 분석에 기반한 웹 문서 중요도 평가 알고리즘의 구현

임성채(Sung-Chae Lim) 한국컴퓨터정보학회 2010 한국컴퓨터정보학회 학술발표논문집 Vol.18 No.2

웹 검색에는 기존의 정보검색(Information Retrieval) 시스템에서와 다르게 문서 간 하이퍼링크 정보를 바탕으로 각 웹 문서의 고유 중요도를 추정하는 방식이 자주 이용된다. 링크 분석에 기반한 알고리즘 중 PageRank 알고리즘은 구글의 웹 검색 서비스에 적용된 것으로 알려져 있다. 이런 PageRank 알고리즘에 따라 중요도를 계산하는 경우 색인된 웹 문서수가 증가함에 따라 계산에 필요한 CPU 자원의 사용도 함께 증가하며, 문서 수가 수 억 페이지에 달하면 하나의 서버에서는 계산을 수행할 수 없다는 문제가 있다. 본 논문에서는 이런 문제점을 해소하기 위해 여러 대의 서버를 PageRank 계산 용 클러스터로 사용할 수 있는 방법을 제시한다. 제시된 방법은 고속의 LAN을 이용하여 여러 대의 서버를 연결하고 반복적인 행렬 계산을 병렬로 수행할 수 있어 계산 시간을 단축시킬 수 있다. 이런 서버 클러스터 구현을 위해 멀티 쓰레딩 프로그램이 작성되었으며, PageRank 계산에 사용되는 행렬 데이터를 적은 양의 메모리만으로 표현 가능하도록 하였다.

계층적 캐슁 기법을 이용한 대용량 웹 검색 엔진의 구현

임성채(Sung Chae Lim) 한국정보과학회 2007 한국정보과학회 학술발표논문집 Vol.34 No.1C

논문에서는 6,000만개 웹 페이지의 색인 데이터에 대해 일 600만 질의를 처리하는 대용량 웹 검색 시스템을 위해 구현된 계층적 캐슁 기법을 소개한다. 논문에서 설명된 시스템 구조 및 알고리즘은 실제 상용 웹 검색 엔진에서 구현되고 운영 결과를 통해 그 유용성이 입증된 것들로서, 구현된 시스템과 유사성을 가지는 대용량 데이터 처리 시스템에 적용 가능할 것이다. 본 논문에서는 기존에 많이 소개되지 않았던 웹 검색 엔진의 운영 절차 및 웹 질의 처리 시스템에 대한 기술적 내용이 기술되었으며, 기술된 내용을 통해 웹 검색 엔진에 대해 보다 정확한 이해가 가능해 질 것이다.