Min-Hash를 이용한 효율적인 대용량 그래프 클러스터링 기법

이석주(Seok-Joo Lee),민준기(Jun-Ki Min) 한국정보과학회 2016 정보과학회논문지 Vol.43 No.3

그래프 클러스터링은 서로 유사한 특성을 갖는 정점들을 동일한 클러스터로 묶는 기법으로 그래프 데이터를 분석하고 그 특성을 파악하는데 폭넓게 사용된다. 최근 소셜 네트워크 서비스와 월드 와이드 웹, 텔레폰 네트워크 등의 다양한 응용분야에서 크기가 큰 대용량 그래프 데이터가 생성되고 있다. 이에 따라서 대용량 그래프 데이터를 효율적으로 처리하는 클러스터링 기법의 중요성이 증가하고 있다. 본 논문에서는 대용량 그래프 데이터의 클러스터들을 효율적으로 생성하는 클러스터링 알고리즘을 제안한다. 우리의 제안 기법은 그래프 내의 클러스터들 간의 유사도를 Min-Hash를 이용하여 효과적으로 추정하고 계산된 유사도에 따라서 클러스터들을 생성한다. 실세계 데이터를 이용한 실험에서 우리는 본 논문에서 제안하는 기법과 기존 그래프 클러스터링 기법들과 비교하여 제안기법의 효율성을 보였다. Graph clustering is widely used to analyze a graph and identify the properties of a graph by generating clusters consisting of similar vertices. Recently, large graph data is generated in diverse applications such as Social Network Services (SNS), the World Wide Web (WWW), and telephone networks. Therefore, the importance of graph clustering algorithms that process large graph data efficiently becomes increased. In this paper, we propose an effective clustering algorithm which generates clusters for large graph data efficiently. Our proposed algorithm effectively estimates similarities between clusters in graph data using Min-Hash and constructs clusters according to the computed similarities. In our experiment with real-world data sets, we demonstrate the efficiency of our proposed algorithm by comparing with existing algorithms.

XML데이터를 위한 효율적인 구조 정보 추출 기법

민준기,Min, Jun-Ki 한국정보처리학회 2007 정보처리학회논문지D Vol.14 No.3

XML 데이터가 웹 상의 데이터 표현 및 교환의 표준으로 각광 받음으로써, XML에 대한 관심이 증대되고 있다. XML 문서의 구조 정보는 몇 가지 중요한 역할을 수행한다. 이러한 중요성에도 불구하고 XML 문서의 구조정보는 필수 요소가 아니다. 따라서, 이러한 구조 정보를 추출하기 위한 다양한 연구들이 진행되어 왔다. 본 논문에서, 우리는 XML 문서를 위한 간결하고 정확한 DTD를 추출하는 기법을 제안한다. 특히 XML 문서의 구조 정보를 위한 DTD의 내용 모델을 DTD와 XML Schema의 혼합 내용(mixed contents)의 타당성 제약 조건을 이용하여 제한하고 본 논문에서 제안하는 몇 가지 경험적 규칙들을 적용함으로써, 우리는 간결성과 효율적을 이룩하였다. 실제 DTD를 이용한 실험을 통하여 본 논문에서 제안하는 기법이 기존의 접근 방법들에 비하여 뛰어남을 보였다. There has been an increasing interest in n since it is spotlighted as the standard for data representation and exchange in the Web. The structural information for XML documents serves several important purposes. In spite of its importance, the schema is not mandatory for XML documents. Thus, much research to extract structural information for XML document has been conducted. In this paper, we present a technique for efficient extraction of concise and accurate DTD for XML documents. By restriction of DTD content model using the mixed content model of DTD and XML Schema as well as applying some heuristic rules proposed in this paper, we achieve the efficiency and conciseness. The result of an experiment with real life DTDs shows that our approach is superior to existing approaches.

영역 할당 기법을 이용한 효율적인 경로 테이블 기법

민준기,Min Jun-Ki 한국정보처리학회 2006 정보처리학회논문지D Vol.13 No.2

XML은 인터넷 상에서 데이터 표현 및 교환의 표준으로 떠오르고 있어서 XML 데이터의 양이 급속히 증가하고 있다. 따라서, XML 데이터에 대한 효율적인 저장 및 검색이 필요하다 관계형 데이터베이스를 이용하는 XRel과 같은 XML 저장 관리 기법에서는 단순히 모든 레이블 경로들을 저장함으로써, 다양한 형태의 경로 표현식을 효율적으로 처리하지 못한다. 본 논문에서는 관계형 데이터베이스를 이용하여 XRel에서 제안된 경로 테이블 기법 보다 효율적인 데이터 저장 및 검색 기법을 제시한다. 본 논문에서 제안하는 기법은 XML 경로 인덱스를 관계형 데이터베이스에 저장하고 레이블 경로를 경로 식별자로 대치함으로써 다양한 형태의 XML 질의들을 기존의 방식에 비하여 보다 효율적으로 처리할 수 있도록 하였다. 또한 제안된 방식은 관계형 데이터베이스 엔진의 수정을 요구하지 않으며, 기존의 방식에 비하여 보다 적은 디스크 공간을 소비한다. 우리의 실험 결과는 제안된 기법이 기존의 기법에 비하여 좋은 질의 성능을 나타냄을 보인다. Since XML is emerging as the de facto standard for exchanging and representation of data on the web, the amount of XML data has rapidly increased. Thus, the need for effective store and retrieval of U data has arisen. Since the existing techniques such as XRel which is an XML storage and management technique using RDBMS simply record the existing all label paths, diverse classes of label path expressions could not be efficiently supported. In this paper, we present a technique which supports storage and retrieval for XML data using RDBMS efficiently compared with the existing approaches. Since the proposed technique keeps the XML path index on the relational database and replace label paths with path identifiers, diverse XML queries can be evaluated compared with existing approaches. Also, the proposed technique does not require the modification of the relational database engine and consumes the disk space less. Our experimental result demonstrates the better query performance compared with existing techniques.

WT-Heuristics: 스트림 데이터 환경에서의 효율적인 필터 연산자 순서화 기법

민준기,Min, Jun-Ki 한국정보처리학회 2008 정보처리학회논문지D Vol.15 No.2

Due to the proliferation of the Internet and intranet, a new application domain called stream data processing has emerged. Stream data is real-timely and continuously generated. In this paper, we focus on the processing of stream data whose characteristics vary unpredictably by over time. Particularly, we suggest a method which generates an efficient operator execution order called WT-Heuristics. WT-Heuristics efficiently determines the operator execution order since it considers only two adjacent operators in the operator execution order. Also, our method changes the execution order with respect to the change of data characteristics with minimum overheads. 인터넷과 인트라넷의 확산에 따라, 스트림 데이터 처리 (stream data processing) 와 같은 새로운 분야가 등장하게 되었다. 스트림 데이터는 실시간적이고 연속적으로 생성된다. 본 논문에서는 시간에 따라서 예측할 수 없게 특성이 바뀌는 데이터 스트림에 대한 처리에 대하여 다룬다. 특별히, 본 논문에서는 스트림 데이터에 대한 질의문을 구성하는 연산자들 간의 효율적인 수행 순서 생성 기법인 WT-Heuristics를 제안한다. WT-Heuristics 기법은 연산 실행 순서에서 인접한 두 연산자들의 연산 순서만을 고려함으로써 효율적으로 연산자 순서를 결정할 수 있다. 또한 본 논문에서 제안하는 방법은 시스템의 부담을 적게 주면서도 데이터의 변화에 따라 수행 순서를 변화시킨다.

QUISIS: Interval Skip List를 활용한 질의 색인 기법

민준기,Min, Jun-Ki 한국정보처리학회 2008 정보처리학회논문지D Vol.15 No.3

인터넷과 인트라넷의 확산에 따라, 스트림 데이터 처리(stream data processing)와 같은 새로운 분야가 등장하게 되었다. 스트림 데이터는 실시간적이고 연속적으로 생성된다. 스트림 데이터 환경에서는 복수 개의 질의들이 미리 등록되고 후에 도착되는 데이터는 등록된 질의들에 의하여 평가된다. 따라서 질의 성능을 향상시키기 위하여, 스트림 데이터 처리 시스템을 위한 다양한 연속성 질의 색인 방법들이 제안되었다. 본 논문에서는 스트림 데이터를 위한 질의 색인에 대하여 다룬다. 일반적으로, 스트림 질의는 간격 조건식을 포함하고 있다. 따라서, 간격 조건식을 이용하여, 질의들을 색인화할 수 있다. 이 논문에서, 탐색 속도를 향상시키기 위하여, Interval Skip List를 수정한 효율적인 질의 색인 방법, QUISIS를 제안한다. QUISIS는 최근 데이터 값이 근 미래에 도착하는 값과 비슷하다는 지역성을 활용한다. 성능 평가를 통하여, 본 논문에서 제안하는 기법의 효율성을 보인다. Due to the proliferation of the Internet and intranet, new application domains such as stream data processing have emerged. Stream data is real-timely and continuously generated. In stream data environments, a lot of queries are registered, and then, the arrived data item is evaluated by registered queries. Thus, to accelerate the query performance, diverse continuous query index schemes have been proposed for stream data processing systems. In this paper, we focus on the query index technique for stream data. In general, a stream query contains the range condition. Thus, by using range conditions, the queries can be indexed. In this paper, we propose an efficient query index scheme, called QUISIS, using a modified Interval Skip Lists to accelerate search time. QUISIS utilizes a locality where a value which will arrive in near future is similar to the current value. Through the experimental study, we show the efficiency of our proposed method.

분산 트랜잭션 워크플로우 모니터링 시스템의 설계 및 구현

민준기,김광훈,정중수,Min Jun-Ki,Kim Kwang-Hoon,Chung Joong-Soo 한국정보처리학회 2006 정보처리학회논문지D Vol.13 No.1

본 논문에서는 분산 트랜잭션 워크플로우 모니터링 시스템의 설계 및 구현에 관하여 기술한다. 워크플로우 인스턴스들의 실행 상태 관리를 주요 목적으로 하는 전통적인 워크플로우 시스템의 모니터링 기능은 워크플로우의 초대형화와 트랜잭션화를 특징으로 하는 분산형 트랜잭션 워크플로우 시스템에서는 워크플로우의 처리 상태 관리뿐만 아니라 구조적인 정보의 수집, 통계 정보 제공, 사용자들의 처리 상태 정보 등과 같은 다양한 부가적인 정보 처리 및 관리 기능을 제공하는 분산형 모니터링 서비스를 필요로 한다. 본 논문에서는 이러한 분산형 트랜잭션 워크플로우 시스템에서 필수적으로 요구되는 새로운 워크플로우 모니터링의 특징을 확장 정의하고, 이를 지원하는 점 기반의 분산 트랜잭션 워크플로우 모니터링 시스템의 상세 설계 및 이의 구현 방안을 소개한다. This paper describes the design and implementation details of a distributed transactional workflow monitoring system. There have been prevalent research and development trends in the workflow literature - workflow systems tend to be completely distributed architectures to support very large-scale workflow applications on object-oriented and internet-based infrastructures. That is, the active (object), distributed (architecture), system-oriented (transaction), and large-scale (application) workflow systems are the key targets in terms of the research and development aspects. While the passive, centralized, human-oriented, and small/medium scale workflow systems are the typical instances of the traditional workflow systems. Unlike in the traditional (the client-server architecture) workflow systems, the workflow monitoring features should not be easily supported in the recent (the fully distributed architecture) workflow systems. At the same time, they need a set of additional monitoring features, such as gathering and displaying statistical (or overload status) information of the workflow architectural components dispersed on the internet. We, in this paper, introduce the additional workflow monitoring features that are necessarily required for the recent workflow systems, and show how to embed those features into a web-based distributed workflow system.

낮은 삽입손실을 갖는 새로운 대역통과 필터를 이용한 주파수 3체배기 설계

민준기,조승용,김현진,김용환,이경학,김대희,윤호석,홍의석,Min, Jun-Ki,Cho, Seung-Yong,Kim, Hyun-Jin,Kim, Yong-Hwan,Lee, Kyoung-Hak,Kim, Dae-Hee,Yun, Ho-Seok,Hong, Ui-Seok 한국통신학회 2006 韓國通信學會論文誌 Vol.31 No.10A

본 논문은 APDP(Anti-Parallel Diode Pair)를 이용한 3체배기로서 출력단에 기존의 Coupled line BPF가 아닌 낮은 삽입손실과 작은 회로사이즈를 갖는 새로운 구조의 BPF를 제안하였다. 이 제안된 구조의 BPF는 인터디지털 캐패시터와 나선형 개방 스터브로 구성되어 있다. 제안된 BPF만의 삽입손실은 대역$(16.41{\sim}19.23GHz)$내에서 0.7dB이하의 특성을 나타내었다. 3체배기의 변환손실은 기본주파수 $5.72{\sim}6.28GHz$에서 약$16.6{\sim}18.5dB$(평탄도 ${\pm}1dB$)의 특성을 얻었으며 6GHz에서 기본주파수와 5차 고조파 억압특성은 각각 -32.16dBc와 -44.6dBc의 특성을 보였으며, 위상잡음 감쇠특성은 약 9.5dB@100kHz의 특성을 나타내었다. This paper proposes a novel BPF structure with less insertion loss and small size instead of the existing coupled line BPF for the output of the tripler using APDP (Anti-Parallel Diode Pair). This proposed BPF consists of the interdigital capacitor and spiral open stub. The proposed BPF has the insertion loss of less than 0.7dB within the band $(16.41{\sim}19.23GHz)$. The conversion loss of the tripler is about $16.6{\sim}18.5dB$ $(flatness<{\pm}1dB)$ at $5.72{\sim}6.28GHz$ of fundamental frequency. Its fundamental frequency and the fifth harmonic suppression characteristic at 6GHz are -32.16dBc and -44.6dBc, respectively And its phase noise attenuation characteristic is about 9.5dB at 100kHz.

공간 시간 근접성을 이용한 효율적인 버퍼 관리 기법

민준기,Min, Jun-Ki 한국정보처리학회 2009 정보처리학회논문지D Vol.16 No.2

Efficient buffer management is closely related to system performance. Thus, much research has been performed on various buffer management techniques. However, many of the proposed techniques utilize the temporal locality of access patterns. In spatial database environments, there exists not only the temporal locality but also spatial locality, where the objects in the recently accessed regions will be accessed again in the near future. Thus, in this paper, we present a buffer management technique, called BEAT, which utilizes both the temporal locality and spatial locality in spatial database environments. The experimental results with real-life and synthetic data demonstrate the efficiency of BEAT. 효율적인 버퍼 관리는 시스템의 성능과 밀접한 관련이 있다. 따라서 다양한 버퍼 관리 기법들에 대한 많은 연구가 진행되어 왔다. 그러나 많은 제안된 기법들의 대부분은 시간 근접성만을 고려하고 있다. 공간 데이터베이스와 같은 환경에서는 시간 근접성뿐 만 아니라, 유사한위치에 있는 공간 객체들은 서로 같이 접근 될 가능성이 높다는 공간 근접성도 존재한다. 따라서, 본 논문에서는 공간 데이터베이스 환경에서 시간근접성과 공간 근접성을 같이 효과적으로 고려하는 버퍼 관리 기법인BEAT를 제안한다. 실제 데이터와 가상 데이터를 이용한 실험 결과는 BEAT의 효율성을 보인다.

Sub-Harmonic 혼합기를 이용한 점대점 시스템용 하향 변환기에 관한 연구

민준기,김현진,김용환,유형수,윤호석,이근태,홍의석,Min Jun-Ki,Kim Hyun-Jin,Kim Yong-Hwan,Yoo Hyung-Soo,Yun Ho-Seok,Lee Keun-Tae,Hong Ui-Seok 한국통신학회 2005 韓國通信學會論文誌 Vol.30 No.10A

본 논문은 Sub-harmonic 혼합기 구조에서 국부발진기(Local Oscillator) 포트에 넓은 대역에 걸쳐서 변환손실을 최적화 하는 정합회로를 적용하였다. 이러한 Sub-harmonic 혼합기를 이용하여 점대점 시스템용 하향 변환기를 설계 및 제작하였다. 제안된 구조의 Sub-harmonic 혼합기는 국부발진기입력전력이 12 dBm일 때 최적으로 11.8 dB의 변환손실을 얻었으며, 격리특성은 40dB이하의 특성을 나타내었다. 전체 하향 변환기의 특성으로 IF 출력 평탄도는 2dB이하의 특성을 나타내었으며, 전체 잡음지수로는 5.9dB이하의 특성을 얻었다. In this thesis, the matching network at the local oscillator port of the sub-harmonic mixer is optimized for reducing the conversion loss. A downconverter for point to point system applications is designed and fabricated using the such sub-harmonic mixer. The sub-harmonic mixer achieved the conversion loss of 11.8 dB at the 12 dBm input power of the local oscillator and the isolation of less than -40 dB. The downconverter achieved the IF output power flatness of 2 dB and the total noise figure of 5.9 dB.

Hydroxychloroquine이 T 세포의 Fas Ligand 대사에 미치는 영향

민준기 ( Jun Ki Min ),이희진 ( Hee Jin Lee ),이원선 ( Won Sun Lee ),박상희 ( Sang Hee Park ),민소연 ( So Youn Min ),조미라 ( Mi La Cho ),조철수 ( Chul Soo Cho ),김호연 ( Ho Youn Kim ) 대한류마티스학회 2000 대한류마티스학회지 Vol.7 No.2

Objective: Hydroxychloroquine (HCQ) is a drug that has been used to treat autoimmune disorders such as rheumatoid arthritis arid systemic lupus erythematosus. However, the specific mechanism for its pharmacologic action has been largely unknown. It has been reported that dysregulation of lymphocytic apoptosis mediated by Fas ligand (FasL) and Fas is associated with the development of autoimmune diseases and HCQ induces apoptosis in peripheral blood lymphocytes. These reports suggest that HCQ may exert its pharmacologic effects through the modulation of FasL and Fas. Therefore, we are intended to investigate the effects of HCQ on the regulation of FasL and Fas. Methods: Jurkat cells or peripheral blood mononuclear cells (PBMNC) were treated with varying concentrations of HCQ. Semiquantative reverse transcription-polymerase chain reaction, Western blotting, flow cytometry, and ELISA were used for this study. Results: HCQ at nontoxic concentrations(50~150μM) caused a dose dependent increase of FasL mRNA expression and FasL in cell lysates. HCQ inhibited the release of intracellular 40 kDa FasL by Jurkat cells which were pulse-stimulated with PHA (50㎍/㎖). Jurkat cells activated with PHA increased membrane bound FasL (mFasL) expression (24.5±4.3%), however Jurkat cells pretreated with HCQ(150μM) followed by PHA administration did not further increase mFasL expression (26.8±1.6%). Addition of different concentrations of HCQ to the cultured PBMNC stimulated with PHA for 24 hours showed increase of soluble FasL (sFasL). The levels of sFasL treated with HCQ zero, 50, 150 and 300μM for 24hours were 38.6±3.0, 43.4±5.1, 77.0±3.6(P<0.05) and 72.3±8.lpg/㎖(P<0.05) respectively. However, fas metabolism was not affected by HCQ. Conclusion: These results suggest that HCQ may exhibit its pharmacological effects by upregulation of FasL gene expression and increased production sFasL without any influence on the Fas metabolism of T cells.