A Logical Model and Data Placement Strategies for MEMS Storage Devices

KIM, Yi-Reun,WHANG, Kyu-Young,KIM, Min-Soo,SONG, Il-Yeol The Institute of Electronics, Information and Comm 2009 IEICE transactions on information and systems Vol.92 No.11

<P>MEMS storage devices are new non-volatile secondary storages that have outstanding advantages over magnetic disks. MEMS storage devices, however, are much different from magnetic disks in the structure and access characteristics in the following ways. They have thousands of heads called <I>probe tips</I> and provide the following two major access facilities: (1) <I>flexibility</I>: freely selecting a set of probe tips for accessing data, (2) <I>parallelism</I>: simultaneously reading and writing data with the set of probe tips selected. Due to these characteristics, it is nontrivial to find data placements that fully utilize the capability of MEMS storage devices. In this paper, we propose a simple logical model called the <I>Region-Sector</I> (<I>RS</I>) model that abstracts major characteristics affecting data retrieval performance, such as flexibility and parallelism, from the physical MEMS storage model. We also suggest heuristic data placement strategies based on the RS model. To show the usability of the RS model, we derive new data placements for relational data and two-dimensional spatial data by using these strategies. Experimental results show that the proposed data placements improve the data retrieval performance by up to 4.7times for relational data and by up to 18.7times for two-dimensional spatial data of approximately 320Mbytes compared with those of existing data placements. Further, these improvements are expected to be more marked as the database size grows.</P>

COSMOS / MT : 객체 저장 시스템 COSMOS 를 위한 멀티프로세스 / 멀티쓰레드 모델의 설계 및 구현

김이른(Yi-Reun Kim),이영구(Young-Koo Lee),장지웅(Ji-Woong Chang),황규영(Kyu-Young Whang) 한국정보과학회 2001 한국정보과학회 학술발표논문집 Vol.28 No.1B

다수 사용자를 지원하는 프로그램에서 쓰레드의 중요성이 증가함에 따라 데이타베이스 관리 시스템의 하부구조인 객체 저장 시스템들도 쓰레드를 이용하도록 확장되고 있다. 기존의 프로세스/쓰레드 모델은 멀티프로세스/단일쓰레드 모델, 단일프로세스/멀티쓰레드 모델, 그리고 멀티프로세스/멀티쓰레드 모델로 분류할 수 있다. 이 중 멀티프로세스/멀티쓰레드 모델은 다른 모델들을 포괄할 수 있는 일반적인 형태의 구조이다. 본 논문에서는 멀티프로세스/단일쓰레드 모델로 개발된 객체 저장 시스템 COSMOS 를 멀티프로세스/멀티쓰레드 모델로 확장한 COSMOS/MT 를 설계하고 구현한다. 먼저 COSMOS 의 트랜잭션 컨텍스트를 분석하여 공유 트랜잭션 컨택스트와 비공유 트랜잭션 컨택스트로 분류한 후, 각 트랜잭션 컨텍스트의 유지방법을 제안한다. 그리고, 구현한 모델의 유용성을 보이기 위하여 TPC-A 벤치마크에 대해 성능 평가를 수행한다. 실험결과 1000 개의 클라이언트를 서비스하는 경우 COSMOS/MT 가 COSMOS 에 비하여 처리율이 최고 5배까지 향상됨을 보인다. 마지막으로, 멀티프로세스/멀티쓰래드 모델의 성능을 결정하는 중요 요소인 프로세스 당 쓰레드 개수에 따른 성능 변화에 대하여 고찰하고, 실험을 통하여 프로세스당 쓰레드 개수에 따른 시스템의 성능 변화를 보인다.

커뮤니티 제한 검색을 위한 웹 크롤링 및 PageRank 계산

김계정(Gye-Jeong Kim),김민수(Min-Soo Kim),김이른(Yi-Reun Kim),황규영(Kyu-Young Whang) 한국정보과학회 2005 한국정보과학회 학술발표논문집 Vol.32 No.1

최근 웹 검색 분야에서는 검색 질을 높이기 위한 기법들이 많이 연구되어 왔으며, 대표적인 연구로는 제한 검색, focused crawling, 웹 클러스터링 등이 있다. 그러나 제한 검색은 범위를 의미적으로 관련된 사이트들로 제한할 수 없으며, focused crawling은 질의 시점에 크롤링하기 때문에 질의 처리 시간이 오래 걸리고, 웹 클러스터링은 많은 웹 페이지들을 대상으로 클러스터링하기 위한 오버헤드가 크다. 본 논문에서는 검색 범위를 특정 커뮤니티로 제한하여 검색 하는 커뮤니티 제한 검색과 커뮤니티를 구하는 방법으로 cluster crawler를 제안하여 이러한 문제점을 해결한다. 또한, 커뮤니티를 이용하여 PageRank를 2단계로 계산하는 방법을 제안한다. 제안된 방법은 첫 번째 과정에서 커뮤니티 단위로 지역적으로 PageRank를 계산한 후, 두 번째 과정에서 이를 바탕으로 전역적으로 PageRank를 계산한다. 제안된 방법은 Wang에 의해 제안된 방법에 비해 PageRank 근사치의 오차를 59%정도로 줄일 수 있다.

간호대학생의 알코올 및 카페인 섭취량, 학습몰입, 수면간의 관계

백예지(Baek Ye Ji),김선경(Kim Sun Kyung),김소현(Kim So Hyun),김한비(Kim Han Bi),조예린(Cho Ye Lin),이승아 (Lee Seung A),장은경(Jang Eun Kyung),권이나(Kwon Yi Na),이지우(Lee Ji Woo),김바른(Kim Ba Reun),박해원(Park Hae Won) 한국콘텐츠학회 2018 한국콘텐츠학회 종합학술대회 논문집 Vol.2018 No.5

< 전시-P-38 > Fractionation of lignin from Salix gracilistyla Miq. using ionic liquid (1-ethyl-3-methylimidazolium acetate)

( Song-yi Han ),( Chan-woo Park ),( Pu-reun-na-rae Seo ),( Won-jae Youe ),( Nam-hun Kim ),( Seung-hwan Lee ) 한국목재공학회 2018 한국목재공학회 학술발표논문집 Vol.2018 No.2

공유 디스크 기반의 다중 서버 DBMS를 위한 효율적인 버퍼 일관성 관리

고현선(Hyun-Sun Ko),김이른(Yi-Reun Kim),이민재(Min-Jae Lee),황규영(Kyu-Young Whang) 한국정보과학회 2009 정보과학회논문지 : 데이타베이스 Vol.36 No.5

In a multiple-server DBMS using the share-disk model, when a server process updates data, the updated ones are not immediately reflected to the buffers of the other server processes. Thus, the other server processes may read invalid data. In this paper, we propose a novel method to solve this problem. In this method the server process stores the identifiers and timestamps of the pages that have been updated during a transaction into the coherency volume when the transaction commits. Then, the server process invalidates its buffers of the pages updated by the other server processes by accessing the coherency volume when the lock is acquired, and, subsequently, read the up-to-date versions of the pages from disk. This method needs only a very small coherency volume and shows a good performance because the amount of data that need to be accessed is very small. 공유디스크 모델을 사용하는 다중 서버 DBMS에서는 서버 프로세스들이 서로 독립된 메모리를 가지므로, 특정 서버 프로세스가 데이터베이스를 수정하더라도 다른 서버 프로세스들의 버퍼에는 수정된 내용이 반영되지 않는다. 따라서, 다른 서버 프로세스들이 수정되기 전 내용에 대하여 데이터 처리 요청을 수행하면 문제가 발생한다. 본 논문에서는 큰 단위의 로크(여기서는 볼륨 로크)를 사용하는 DBMS에서 이러한 문제를 해결하기 위한 새로운 방법을 제안한다. 이 방법에서는 서버 프로세스가 트랜잭션을 커밋할 때 수정한 페이지의 식별자와 타임스탬프를 일관성 볼륨에 저장하고, 이 정보를 통하여 다른 서버 프로세스가 로크를 획득하는 시점에 일관성 볼륨에서 다른 프로세스가 먼저 수정하였는지 여부를 확인하여 해당 페이지를 버퍼에서 무효화시켜 디스크에서 최신의 버전을 새로 읽어 들인다. 이 방법은 매우 작은 크기의 일관성 볼륨만을 사용하고, 액세스하는 데이터의 양이 적어서 성능이 매우 빠르다.

오디세우스 대용량 검색 엔진을 위한 병렬 웹 크롤러의 구현

신은정(Eun-Jeong Shin),김이른(Yi-Reun Kim),허준석(Jun-Seok Heo),황규영(Kyu-Young Whang) 한국정보과학회 2008 정보과학회 컴퓨팅의 실제 논문지 Vol.14 No.6

웹의 크기가 폭발적으로 증가함에 따라 인터넷에서 정보를 얻는 수단으로서 검색 엔진의 중요성이 부각되고 있다. 검색 엔진은 사용자에게 최신의 정보를 검색 결과로서 제공하기 위해 웹 페이지를 주기적으로 수집하고 이를 데이타베이스에 저장한다. 웹 크롤러는 이러한 목적으로 웹 페이지를 수집하는 프로그램이다. 대부분의 검색 엔진은 제한된 시간 내에 많은 수의 웹 페이지를 수집하기 위해 다수의 머신을 사용하는 병렬 웹 크롤러를 이용한다. 그러나, 병렬 웹 크롤러의 아키텍처와 세부 구현 방법이 잘 알려져 있지 않기 때문에 실제로 병렬 웹 크롤러를 구현하는 데에 어려움이 많다. 본 논문에서는 병렬 웹 크롤러(parallel web crawler)의 아키텍처와 세부 구현 방법을 제시한다. 병렬웹 크롤러는 다수의 머신에서 웹 페이지를 병렬적으로 수집하기 위해 조정자(coordinator) 대리자(agent) 구조의 2-티어(tier) 모델을 사용한다. 조정자/대리자 모델은 각 머신에서 웹 페이지를 수집하기 위한 다수의 대리자들과 이 대리자들을 관리하기 위한 하나의 조정자로 구성된다. 병렬 웹 크롤러는 웹 페이지를 수집하기 위한 크롤링(crawling) 모듈, 수집한 웹 페이지를 데이타베이스 로딩 포맷으로 변환하기 위한 컨버팅(converting) 모듈, 수집된 웹 페이지의 중요도를 계산하기 위한 랭킹(ranking) 모듈로 구성된다. 본 논문에서는 병렬 웹 크롤러의 각 모듈들을 설명하고, 세부 구현 방법을 설명한다. 마지막으로, 실험을 통해 병렬 웹 크롤러의 성능을 평가하였다. 실험 결과, 제안된 병렬 웹 크롤러가 수집해야할 웹 페이지 개수와 머신 개수에 따라 확장 가능함을 보였다. As the size of the web is growing explosively, search engines are becoming increasingly important as the primary means to retrieve information from the Internet. A search engine periodically downloads web pages and stores them in the database to provide readers with up-to-date search results. The web crawler is a program that downloads and stores web pages for this purpose. A large-scale search engines uses a parallel web crawler to retrieve the collection of web pages maximizing the download rate. However, the service architecture or experimental analysis of parallel web crawlers has not been fully discussed in the literature. In this paper, we propose an architecture of the parallel web crawler and discuss implementation issues in detail. The proposed parallel web crawler is based on the coordinator/agent model using multiple machines to download web pages in parallel. The coordinator/agent model consists of multiple agent machines to collect web pages and a single coordinator machine to manage them. The parallel web crawler consists of three components: a crawling module for collecting web pages, a converting module for transforming the web pages into a database-friendly format, a ranking module for rating web pages based on their relative importance. We explain each component of the parallel web crawler and implementation methods in detail. Finally, we conduct extensive experiments to analyze the effectiveness of the parallel web crawler. The experimental results clarify the merit of our architecture in that the proposed parallel web crawler is scalable to the number of web pages to crawl and the number of machines used.

Query Expansion Using Augmented Terms in an Extended Boolean Model

Tuan-Quang Nguyen,Jun-Seok Heo,Jun-Hoon Lee,Yi-Reun Kim,Kyu-Young Whang 한국정보과학회 2008 Journal of Computing Science and Engineering Vol.2 No.1

We propose a new query expansion method in the extended Boolean model that improves precision without degrading recall. For improving precision, our method promotes the ranks of documents having more query terms since users typically prefer such documents. The proposed method consists of the following three steps: (1) expanding the query by adding new terms related to each term of the query, (2) further expanding the query by adding augmented terms, which are conjunctions of the terms, (3) assigning a weight on each term so that augmented terms have higher weights than the other terms. We conduct extensive experiments to show the effectiveness of the proposed method. The experimental results show that the proposed method improves precision by up to 102% for the TREC-6 data compared with the existing query expansion method using a thesaurus proposed by Kwon et al. [Kwon et al. 1994].

Query Expansion Using Augmented Terms in an Extended Boolean Model

Nguyen, Tuan-Quang,Heo, Jun-Seok,Lee, Jung-Hoon,Kim, Yi-Reun,Whang, Kyu-Young Korean Institute of Information Scientists and Eng 2008 Journal of Computing Science and Engineering Vol.2 No.1

We propose a new query expansion method in the extended Boolean model that improves precision without degrading recall. For improving precision, our method promotes the ranks of documents having more query terms since users typically prefer such documents. The proposed method consists of the following three steps: (1) expanding the query by adding new terms related to each term of the query, (2) further expanding the query by adding augmented terms, which are conjunctions of the terms, (3) assigning a weight on each term so that augmented terms have higher weights than the other terms. We conduct extensive experiments to show the effectiveness of the proposed method. The experimental results show that the proposed method improves precision by up to 102% for the TREC-6 data compared with the existing query expansion method using a thesaurus proposed by Kwon et al.

오디세우스/Parallel-OOSQL : 오디세우스 정보검색용 밀결합 DBMS를 사용한 병렬 정보 검색 엔진

류재준(Jae-Joon Ryu),황규영(Kyu-Young Whang),이재길(Jae-Gil Lee),권혁윤(Hyuk-Yoon Kwon),김이른(Yi-Reun Kim),허준석(Jun-Suk Heo),이기훈(Ki-Hoon Lee) 한국정보과학회 2008 정보과학회 컴퓨팅의 실제 논문지 Vol.14 No.4

최근 들어 인터넷의 성장으로 인하여 문서의 양이 기하급수적으로 증가함에 따라, 대용량의 문서를 빠르게 검색 할 수 있는 병렬 정보 검색 엔진에 대한 중요성이 더욱 대두되고 있다. 병렬 정보 검색엔진을 구현하기 위하여서는 역 색인을 분할하고, 분할된 역 색인을 통하여 병렬적으로 검색하는 것이 필요하다. 역 색인을 분할하는 기존 방법으로는 1) 문서 식별자 분할 방법과 2) 키워드 식별자 분할 방법이 있다. 그러나 각 분할 방법은 다음과 같은 단점들을 가지고 있다. 문서 식별자 분할 방법은 문서의 추가가 용이하고 처리량(throughput)이 높은 반면에 top-k 질의 처리 성능이 좋지 않다. 그리고 키워드 식별자 분할 방법은 top-k 질의 처리 성능이 좋은 반면에 문서의 추가가 어렵고 처리량이 낮다. 본 논문에서는 이러한 단점들을 해결하기 위하여 혼합 분할 방법을 제안하고 이를 정보 검색 기능과 밀결합된 DBMS인 오디세우스에 실현한 병렬 정보 검색 엔진을 설계하고 구현한다. 먼저, 제안된 병렬 정보 검색 엔진인 오디세우스/Parallel-OOSQL의 아키텍쳐를 설명한다. 그리고 체계적인 실험을 통하여 제안된 시스템의 유용성을 보인다. 실험 결과, 문서 식별자 분할 방법은 질의 처리 시간이 역 색인 분할의 블록의 개수에 근사적으로 역 비례함을 보였으며, 키워드 식별자 분할 방법은 top-k 질의 처리에 좋은 성능을 보였다. 본 논문에서 제안된 병렬 정보 검색 엔진은 세 가지 분할 방법을 모두 제공하기 때문에 응용 환경에 따라 분할방법을 커스터마이즈함으로써 항상 좋은 성능을 낼 수 있다. 오디세우스/Parallel-OOSQL 병렬 정보 검색엔진은 각 슬레이브 노드 당 1억 건의 웹 문서를, 시스템 전체로는 수십억 건의 웹 문서를 인덱스하여 저장하고 질의를 처리할 수 있다. As the amount of electronic documents increases rapidly with the growth of the Internet, a parallel search engine capable of handling a large number of documents are becoming ever important. To implement a parallel search engine, we need to partition the inverted index and search through the partitioned index in parallel. There are two methods of partitioning theinverted index: 1) document identifier based partitioning and 2) keyword-identifier based partitioning. However, each method alone has the following drawbacks. The former is convenient in inserting documents and has high throughput, but has poor performance for top-k query processing. The latter has good performance for top-k query processing, but is inconvenient in inserting documents and has low throughput. In this paper, we propose a hybrid partitioning method to compensate for the drawback of each method. We design and implement a parallel search engine that supports the hybrid partitioning method using the Odysseus DBMS tightly coupled with information retrieval capability. We first introduce the architecture of the parallel search engine-Odysseus/Parallel-OOSQL. We then show the effectiveness of the proposed system through systematic experiments. The experimental results show that the query processing time of the document-identifier based partitioning method is approximately inversely proportional to the number of blocks in the partition of the inverted index. The results also show that the keyword-identifier based partitioning method has good performance in top-k query processing. The proposed parallel search engine can be optimized for performance by customizing the methods of partitioning the inverted index according to the application environment. The Odysseus/Parallel-OOSQL parallel search engine is capable of indexing, storing, and querying 100 million web documents per node or tens of billions of web documents for the entire system.