효율적 범위 검색을 위한 플래시 메모리 기반 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.

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

임성채 ( 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.

쿨링다운 노드를 사용한 TPR*-트리 효율화 기법

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

GPS 칩을 내장한 다양한 이동 통신 기기의 사용으로 위치 정보를 이용한 응용이 점차 확산될 전망이다. 위치 정보를 기반으로 한 응용 시스템에서는 다수 이동 객체의 위치 정보를 실시간으로 기록하고, 미래 시점의 객체 위치를 추정할 수 있어야 한다. 이런 요구에 따라 효과적인 이동 객체 색인에 고안된 기법이 TPR*-트리이다. 하지만 TPR*-트리는 고정 위치 색인에 최적화된 R-트리에 기본을 두었기 때문에 갱신 비용이 매우 커질 수 있다는 문제가 있다. R-트리에서는 갱신 연산이 빈번하지 않을 수 있지만 TPR*-트리의 경우는 이동 객체가 속도를 변화시킬 때마다 갱신 연산이 요구되기 때문에 상대적으로 매우 큰 갱신 비용이 발생할 수 있다. 이런 문제점을 부분적으로 해결하기 위해 본 논문에서는 쿨링다운 노드를 사용한 TPR*-트리를 제안한다. 제안된 트리는 트리의 상위 계층에 일부 이동 객체를 버퍼링함으로써 갱신 연산을 최소화 할 수 있다. 또한 지나친 사장 영역(dead space)의 확대를 방지함으로써 검색 성능 저하를 효과적으로 줄일 수 있다.

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

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

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

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

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

계층적 캐시 기법을 이용한 대용량 웹 검색 질의 처리 시스템의 구현

임성채(Lim Sung Chae) 한국정보과학회 2008 정보과학회 컴퓨팅의 실제 논문지 Vol.14 No.7

웹을 이용한 정보 공개 및 검색이 확대됨에 따라 웹 검색 엔진도 지속적인 주목을 받고 있다. 이에 따라 웹 검색 엔진의 다양한 기술적 문제를 해결하고자 하는 연구가 있었음에도 웹 검색 엔진의 질의 처리 시스템에 대한 기술적 내용은 잘 다뤄지지 않았다. 질의 처리 시스템의 경우 소프트웨어 아키텍처나 운영 기법을 고안하기 어렵기 때문에 본 논문에서는 구현된 상용 시스템을 바탕으로 관련 기술을 소개하고자 한다. 구현된 질의 처리 시스템은 6,500 만개 웹 문서를 색인하여 일 500만개 이상의 사용자 질의 요청을 수행하는 큰 규모의 시스템이다. 구현한 시스템은 질의 처리 결과를 재사용하기 위해 계층적 캐시 기법을 적용했으며, 저장된 캐시 데이타는 4계층으로 구성된 데이타 저장소에 분산 저장되는 것이 특징이다. 계층적 캐시 기법을 통해 질의 처리 용량을 400% 정도로 향상 시킬 수 있었으며 이를 통해 서버 구축 비용을 70% 정도 절감할 수 있었다. With the increasing demands of information sharing and searches via the web, the web search engine has drawn much attention. Although many researches have been done to solve technical challenges to build the web search engine, the issue regarding its query processing system is rarely dealt with. Since the software architecture and operational schemes of the query processing system are hard to elaborate, we here present related techniques implemented on a commercial system. The implemented system is a very large-scale system that can process 5-million user queries per day by using index files built on about 65-million web pages. We implement a multi-level cache scheme to save already returned query results for performance considerations, and the multi-level cache is managed in 4-level cache storage areas. Using the multi-level cache, we can improve the system throughput by a factor of 4, thereby reducing around 70% of the server cost.

OSI - CCR 서비스의 구현

임성채(Sung-Chae Lim),유호동(Ho-Dong Yoo),김명호(Myoung-Ho Kim) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.2

분산 환경에서 수행되는 트랜잭션은 분산 트랜잭션에 관계한 모든 사이트에 대해 각 사이트의 국부 트랜잭션이 갖는 결과들이 일관성(consistency)을 유지할 수 있어야 한다. 분산 트랜잭션의 일관성을 유지하기 위해선 2단계 종료 규약과 통신장애나 응용 프로그램의 고장에 대비한 회복 기능이 요구되며 이런 요구 사항을 표준적으로 제공하고자 하는 것이 OSI-CCR(Commitment,Concurrency and Recovery) 서비스의 목적이다. 본 논문에서는 분산 트랜잭션 처리 시스템 개발에 유용하게 사용되는 OSI-CCR 서비스의 구현에 관해 기술하려 하며, 특히 CCR 구현에 있어 핵심적인 부분인 CCR 로그 관리 시스템 구현을 위한 사항들을 자세히 기술하도록 한다.

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

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

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

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

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

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