데이타 웨어하우스에서 데이타 큐브를 위한 효율적인 점진적 관리 기법

이기용(Ki Yong Lee),박창섭(Chang-Sup Park),김명호(Myoung Ho Kim) 한국정보과학회 2006 정보과학회논문지 : 데이타베이스 Vol.33 No.2

데이타 큐브는 차원 애트리뷰트의 모든 가능한 조합에 대해 데이타를 집단화하는 연산자이다. 차원 애트리뷰트의 수가 n일 때, 데이타 큐브는 2ⁿ개의 group-by를 계산한다. 데이타 큐브에 포함된 각각의 group-by를 큐보이드(cuboid)라 부른다. 데이타 큐브는 흔히 미리 계산되어 형태 뷰(materialized view)의 형태로 데이타 웨어하우스에 저장된다. 이러한 데이타 큐브는 소스 릴레이션이 변경되면 이를 반영하기 위해 갱신되어야 한다. 데이타 큐브의 점진적 관리는 데이타 큐브의 변경될 내용만을 계산하여 이를 데이타 큐브에 반영하는 방법을 의미한다. 2n개의 큐보이드로 이루어진 큐브의 변경될 내용을 계산하기 위하여, 기존의 방법들은 데이타 큐브와 동일한 개수의 큐보이드를 가지는 변경 큐브를 계산한다. 따라서, 차원 애트리뷰트의 수가 증가할수록 변경 큐브를 계산하는 비용이 매우 커지게 된다. 변경 큐브에 포함된 각 큐보이드들을 변경 큐보이드(delta cuboid)라 부른다. 본 논문에서는 2ⁿ개의 변경 큐보이드 대신 <SUB>n</SUB>C<SUB>[n/2]</SUB>개의 변경 큐보이드만을 사용하여 데이타 큐브를 갱신하는 방법을 제안한다. 이에 따라 제안하는 방법은 변경 큐브를 계산하는 비용을 크게 줄일 수 있다. 성능 평가 결과는 제안하는 방법이 기존의 방법에 비해 더 좋은 성능을 가지고 있음을 보여준다. The data cube is an aggregation operator that computes group-bys for all possible combination of dimension attributes. When the number of the dimension attributes is n, a data cube computes 2ⁿ group-bys. Each group-by in a data cube is called a cuboid. Data cubes are often precomputed and stored as materialized views in data warehouses. These data cubes need to be updated when source relation change. The incremental maintenance of a data cube is to compute and propagate only its changes. To compute the change of a data cube of 2ⁿ cuboids, previous works compute a delta cube that has the same number of cuboids as the original data cube. Thus, as the number of dimension attributes increases, the cost of computing a delta cube increases significantly. Each cuboid in a delta cube is called a delta cuboid. In this paper, we propose an incremental cube maintenance method that can maintain a data cube by using only <SUB>n</SUB>C<SUB>[n/2]</SUB> delta cuboids. As a result, the cost of computing a delta cube is substantially reduced. Through various experiments, we show the performance advantages of our method over previous methods.

콘텐트 노드의 유사성 제어를 통한 그래프 구조 데이터 검색의 다양성 향상

박창섭(Chang-Sup Park) 한국콘텐츠학회 2020 한국콘텐츠학회논문지 Vol.20 No.3

최근 소셜 네트워크, 시맨틱 웹 등 여러 분야에서 그래프 구조 데이터가 널리 사용됨에 따라 대량의 그래프데이터에 대한 효과적이고 효율적인 검색 방법의 필요성이 커지고 있다. 기존 키워드 기반 검색 방법들은 대부분 주어진 질의에 대한 연관도만을 고려하여 결과를 구한다. 그러나 이런 방법은 질의 연관도는 높지만 콘텐트 노드들을 공유하는 유사한 결과들이 함께 선택될 가능성이 높다. 이런 문제점을 개선하기 위해 본 논문에서는 키워드 질의에 대한 답 트리에 포함된 콘텐트 노드들의 유사성을 제어하여 콘텐트 노드가 다양한 답 트리들을 구하는 top-k 검색 방법을 제안한다. 다양한 답 트리 집합의 기준을 정의하고, 다양한 top-k 결과 집합을 구하기 위한 두 가지 방법으로 점진적 나열 알고리즘과 A* 탐색 기법을 이용한 휴리스틱 탐색 알고리즘을 설계한다. 또 휴리스틱 탐색의 성능을 높이기 위한 개선 방법을 제시한다. 실 데이터를 이용한 성능 실험 결과를 통해, 본 논문에서 제안한 휴리스틱 탐색 방법이 질의 연관성뿐만 아니라 콘텐트 노드들의 상이도가 높은 다양한 답 트리들을 효율적으로 구할 수 있음을 보인다. Recently, as graph-structured data is widely used in various fields such as social networks and semantic Webs, needs for an effective and efficient search on a large amount of graph data have been increasing. Previous keyword-based search methods often find results by considering only the relevance to a given query. However, they are likely to produce semantically similar results by selecting answers which have high query relevance but share the same content nodes. To improve the diversity of search results, we propose a top-k search method that finds a set of subtrees which are not only relevant but also diverse in terms of the content nodes by controlling their similarity. We define a criterion for a set of diverse answer trees and design two kinds of diversified top-k search algorithms which are based on incremental enumeration and A* heuristic search, respectively. We also suggest an improvement on the A* search algorithm to enhance its performance. We show by experiments using real data sets that the proposed heuristic search method can find relevant answers with diverse content nodes efficiently.

복합 웹 서비스의 분산 처리 구조

박창섭 ( Chang-sup Park ),이상수 ( Sang-soo Lee ) 한국정보처리학회 2004 한국정보처리학회 학술대회논문집 Vol.11 No.1

웹 서비스는 이질적인 응용 시스템들 사이의 연동 및 통합을 위한 표준화된 수단을 제공한다. 본 논문에서는 기존 웹 서비스들을 이용하여 정의되는 복합 웹 서비스를 효율적으로 실행하기 위한 방안으로서 사용자 에이전트를 이용한 분산 처리 시스템 구조 및 처리 방법을 제안한다. 본 시스템은 웹 서비스들의 통신 QoS 및 복합 웹 서비스의 부하 등을 고려하여 복합 웹 서비스의 호출 및 통합 작업을 사용자 에이전트에게 동적으로 위임하여 분산 처리함으로써 복합 웹 서비스의 성능 및 가용성을 향상시킨다.

시맨틱 RDF 데이터에 대한 효과적인 키워드 검색

박창섭(Chang-Sup Park) 한국콘텐츠학회 2017 한국콘텐츠학회논문지 Vol.17 No.11

최근 지식 베이스, 시맨틱 웹 등 여러 응용 분야에서 시맨틱 데이터의 활용이 증가함에 따라 대규모 RDF 데이터에 대한 효과적인 검색 방법의 필요성이 커지고 있다. 기존의 개별 루트 시맨틱에 기반한 키워드 검색 방법들은 서로 다른 루트 노드를 갖는 결과 트리들의 집합만을 검색함에 따라, 의미적으로 유사하거나 연관성이 낮은 결과 트리들이 함께 검색되고, 동일한 루트 노드를 공유하되 의미적으로 다르고 질의 연관도가 높은 결과들은 함께 검색될 수 없는 문제점이 있다. 이를 개선하기 위해 본 논문에서는 결과 트리들의 루트 노드의 중복을 제한적으로 허용하여 질의 연관도가 높으면서 다양한 결과들을 함께 검색하는 방법을 제안한다. 이를 위해 결과 트리 집합의 루트 중복도 척도를 정의하고, 주어진 키워드 질의와 최대 루트 중복도에 따라 제한적인 루트 중복성을 가지면서 연관도가 높은 top-k 결과 트리들을 효율적으로 구하기 위한 검색 알고리즘을 제시한다. 실 데이터를 이용한 성능 실험 결과, 제안한 방법이 기존 방법보다 콘텐트 노드들의 중복이 적은 다양한 결과 트리들을 검색할 뿐만 아니라 결과 트리들의 루트 노드의 중복을 허용함으로써 질의 연관도가 더 높은 결과들을 생성할 수 있음을 보였다. As a semantic data is widely used in various applications such as Knowledge Bases and Semantic Web, needs for effective search over a large amount of RDF data have been increasing. Previous keyword search methods based on distinct root semantics only retrieve a set of answer trees having different root nodes. Thus, they often find answer trees with similar meanings or low query relevance together while those with the same root node cannot be retrieved together even if they have different meanings and high query relevance. We propose a new method to find diverse and relevant answers to the query by permitting duplication of root nodes among them. We present an efficient query processing algorithm using path indexes to find top-k answers given a maximum amount of root duplication a set of answer trees can have. We show by experiments using a real dataset that the proposed approach can produce effective answer trees which are less redundant in their content nodes and more relevant to the query than the previous method.

그래프 데이터에 대한 비-중복적 키워드 검색 방법

박창섭(Chang-Sup Park) 한국콘텐츠학회 2016 한국콘텐츠학회논문지 Vol.16 No.6

최근 소셜 네트워크, 시맨틱 웹, 바이오 인포매틱스 등 여러 응용 분야에서 그래프 구조를 갖는 대용량 데이터들에 활용됨에 따라 이런 데이터들에 대한 키워드 기반 검색 방법이 많은 관심을 받고 있다. 본 논문에서는 그래프 구조 데이터에 대한 키워드 질의에 대해 질의와 연관성이 높으면서 구조적인 중복성을 갖지 않는 top-k 결과 집합을 효율적으로 검색하는 방법을 제안한다. 키워드 질의에 대한 비-중복적인 결과 트리 구조와 그것의 연관도 척도를 정의하고, 그래프 내에 포함된 유용한 경로 정보들에 대한 효과적인 인덱싱 방법을 제안한다. 그리고 기 생성된 인덱스를 활용하여 주어진 키워드 질의에 대해 비-중복적이면서 연관도가 큰 top-k 결과 집합을 생성하는 효율적인 질의 처리 알고리즘을 제시한다. 실 데이터를 이용한 실험을 통해 제안한 방법의 효과와 성능을 기존 방법과 비교 분석한다. As a large amount of graph-structured data is widely used in various applications such as social networks, semantic web, and bio-informatics, keyword-based search over graph data has been getting a lot of attention. In this paper, we propose an efficient method for keyword search over graph data to find a set of top-k answers that are relevant as well as non-redundant in structure. We define a non-redundant answer structure for a keyword query and a relevance measure for the answer. We suggest a new indexing scheme on the relevant paths between nodes and keyword terms in the graph, and also propose a query processing algorithm to find top-k non-redundant answers efficiently by exploiting the pre-calculated indexes. We present effectiveness and efficiency of the proposed approach compared to the previous method by conducting an experiment using a real dataset.

반도체 공정에서 발생하는 혼합분진의 폭발 위험성평가

박창섭(Chang-Sup Park),김찬오(Chan-O Kim) 대한전기학회 2018 전기학회논문지 Vol.67 No.3

The use of metals such as aluminum and titanium and the related industrial facilities have been continuously increasing to meet the requirements of the improvement of high-tech products due to the development of industry, and explosion of metal dust. Semiconductor process Metal dust is essential, but research is insufficient. The purpose of this study is to identify risk by analyzing the quantitative risk such as maximum explosion pressure and minimum explosion concentration applied international test standard in order to select the semiconductor process facilities handling dust and to predict possible risk of accidents.

의미적 연관성을 이용한 멀티미디어 정보 검색

박창섭 ( Park Chang-sup ) 한국인터넷정보학회 2007 인터넷정보학회논문지 Vol.8 No.5

최근 웹 기술의 발달과 유무선 네트워크 성능의 향상, 그리고 다양한 멀티미디어 서비스가 등장함에 따라 텍스트 문서나 이미지에 대한 검색뿐만 아니라 동영상을 포함한 멀티미디어 검색에 대한 요구가 크게 증가하고 있다. 그러나 기존의 멀티미디어 검색 방법은 멀티미디어 콘텐츠에 포함된 의미 개념들의 연관성을 효과적으로 이용하지 못하고 콘텐츠에 대한 메타데이터의 검색에 의존함에 따라 제한적인 검색 결과만을 제공한다. 본 논문에서는 도메인 온톨로지를 활용하여 멀티미디어 콘텐츠의 의미적 연관성에 기반을 둔 멀티미디어 검색 방법 및 시스템 구조를 제안한다. 사용자 검색어를 직접적으로 포함하지 않지만 의미적으로 연관성이 있는 개념들을 온톨로지에서 검색하고 이들에 대한 랭킹을 결정하기 위한 클래스 연관도 척도를 정의하고, 이를 효율적으로 계산하기 위한 알고리즘을 제시한다. 또 프로토타입 시스템 구현 및 실험을 통해 제안한 검색 방법 및 시스템의 효과를 보인다. As the Web technologies and wired/wireless network are improved and various new multimedia services are introduced recently, need for searching multimedia including video data has been much increasing. The previous approaches for multimedia retrieval, however, do not make use of the relationships among semantic concepts contained in multimedia contents in an efficient way and provide only restricted search results. This paper proposes a multimedia retrieval system exploiting semantic relevancy of multimedia contents based on a domain ontology. We show the effectiveness of the proposed system by experiments on a prototype system we have developed. The proposed multimedia retrieval system can extend a given search keyword based on the relationships among the semantic concepts in the ontology and can find a wide range of multimedia contents having semantic relevancy to the input keyword. It also presents the results categorized by the semantic meaning and relevancy to the keyword derived from the ontology. Independency of domain ontology with respect to metadata on the multimedia contents is preserved in the proposed system architecture.

IP 기반 방송 서비스를 위한 전자 프로그램 가이드 전송 방안

박창섭 ( Chang-sup Park ) 한국정보처리학회 2005 한국정보처리학회 학술대회논문집 Vol.12 No.1

본 논문에서는 IP 통신망의 특성을 고려하여 IP 망 기반의 방송 서비스를 위한 효율적인 EPG 데이터 전송 방안을 제안한다. EPG 정보를 사용자 요구 특성을 고려하여 여러 그룹으로 분할하고 이에 대해 OOB 채널을 통한 멀티캐스트 전송 방식과 사용자 별 요구 및 응답 처리를 통한 유니캐스트 전송 방식을 혼합 적용한다. 또한 서비스 요구 상황에 따라 두 방식을 동적으로 선택 및 변경함으로써 EPG 시스템의 서버 자원과 네트워크 대역폭을 효율적으로 활용할 수 있다.

SEDRIS 기반 환경 데이터에 대한 XML 스키마 설계 및 변환

박창섭(Chang-Sup Park),이명원(Myeong Won Lee) 한국콘텐츠학회 2023 한국콘텐츠학회논문지 Vol.23 No.12

The SEDRIS provides a standard data model(DRM) which can represent structural and semantic information on various environments such as geography, ocean, and atmosphere, and used in various fields that exploit environmental information. Since a dedicated binary storage format and APIs must be used to store and retrieve SEDRIS data, there are a lot of difficulties in sharing and exploiting them in various platforms and applications. In this paper, we propose XML schema constructs for all components of DRM to represent SEDRIS-based data as XML data, which can increase the usability of environmental data built on the SEDRIS standards. We also design and implement a conversion algorithm that transforms a SEDRIS data stored in an STF file into XML data conforming to the proposed schema. Experiments on various example data sets show that the proposed algorithm can generate a valid XML data for a given SEDRIS data efficiently. Based on the proposed method, environmental data stored in SEDRIS proprietary binary files can be represented by platform-independent and language-neutral XML data, making it easy to generate and share environmental data on various platforms and systems without relying on the dedicated APIs. The environmental data in the proposed XML format can be exploited for data visualization and virtual environment construction by transformation to the other XML-based data models such as X3D.

내포 결과를 이용한 복합 웹 서비스 실행의 비용 기반 최적화

박창섭(Chang-Sup Park) 한국정보과학회 2006 정보과학회논문지 : 데이타베이스 Vol.33 No.7

웹 서비스는 인터넷 상에 분산되어 있는 이질적인 응용들 사이의 연동 및 통합을 위한 표준화된 수단을 제공한다. 본 논문에서는 계층적인 연동 관계가 존재하는 복합 웹 서비스들에 대해 서비스 결과로 전달되는 내포 데이타를 활용하여 웹 서비스들의 호출 및 복귀 작업을 서버 및 통신 비용에 따라 효과적으로 분산 수행함으로써 웹 서비스 시스템의 전체적인 성능을 향상시킬 수 있는 방안을 제시한다. 본 논문에서는 내포 결과를 이용한 적법한 웹 서비스 호출 실행 계획 및 이에 대한 비용 기반 최적화 문제를 정의하고, 최적 호출 실행 계획을 찾기 위한 휴리스틱 탐색 방법과 효율적으로 수행될 수 있는 그리디 알고리즘을 제안한다. 실험 결과, 제안한 그리디 알고리즘은 빠른 시간 내에 최적 해에 가까운 효율적인 호출 실행 계획을 생성하며, 복잡한 웹 서비스 연동 관계에 대해서 우수한 확장성을 보였다. Web service technologies provide a standard means for interoperation and integration of heterogeneous applications distributed over the Internet. For efficient execution of hierarchically interacting composite web services, this paper proposes an approach to distribute web service invocations over peer systems effectively, exploiting intensional XML data embedding external service calls as a result of web services. A cost-based optimization problem on the execution of web services using intensional results was formalized, and a heuristic search method to find an optimal solution and a greedy algorithm to generate an efficient invocation plan quickly were suggested in this paper. Experimental evaluation shows that the proposed greedy algorithm provides near-optimal solutions in an acceptable time even for a large number of Web services.