대용량 추론을 위한 분산환경에서의 가정기반진리관리시스템 = Distributed Assumption-Based Truth Maintenance System for Scalable Reasoning

다국어 초록 (Multilingual Abstract)

Assumption-based truth maintenance system (ATMS) is a tool that maintains the reasoning process of inference engine. It also supports non-monotonic reasoning based on dependencydirected backtracking. Bookkeeping all the reasoning processes allows it to quickly check and retract beliefs and efficiently provide solutions for problems with large search space. However, the amount of data has been exponentially grown recently, making it impossible to use a single machine for solving large-scale problems. The maintaining process for solving such problems can lead to high computation cost due to large memory overhead. To overcome this drawback, this paper presents an approach towards incrementally maintaining the reasoning process of inference engine on cluster using Spark.
It maintains data dependencies such as assumption, label, environment and justification on a cluster of machines in parallel and efficiently updates changes in a large amount of inferred datasets. We deployed the proposed ATMS on a cluster with 5 machines, conducted OWL/RDFS reasoning over University benchmark data (LUBM) and evaluated our system in terms of its performance and functionalities such as assertion, explanation and retraction. In our experiments, the proposed system performed the operations in a reasonably short period of time for over 80GB inferred LUBM2000 dataset.

국문 초록 (Abstract)

가정기반진리관리 시스템(ATMS)은 추론 시스템의 추론 과정을 저장하고 비단조추론을 지원할 수 있는 도구이다 또한 의존기반 backtracking을 지원하므로 매우 넓은 공간 탐색 문제를 해결 할 수있는 강력한 도구이다. 모든 추론 과정을 기록하고, 특정한 컨텍스트에서 지능형시스템의 Belief를 매우 빠르게 확인하고 비단조 추론 문제에 대한 해결책을 효율적으로 제공할 수 있게 한다. 그러나 최근 데이터의 양이 방대해지면서 기존의 단일 머신을 사용하는 경우 문제 해결 프로그램의 대용량의 추론과정을 저장하는 것이 불가능하게 되었다. 대용량 데이터에 대한 문제 해결 과정을 기록하는 것은 많은 연산과 메모리 오버헤드를 야기한다. 이러한 단점을 극복하기 위해 본 논문에서는 Apache Spark 환경에서 functional 및 객체지향 방식 기반의 점진적 컨텍스트 추론을 유지할 수 있는 방법을 제안한다.. 이는 가정(Assumption)과 유도과정을 분산 환경에 저장하며, 실체화된 대용량 데이터셋의 변화를 효율적으로 수정가능하게 한다. 또한 ATMS의 Label, Environment를 분산 처리하여 대규모의 추론 과정을 효과적으로관리할 수 있는 방안을 제시하고 있다. 제안하는 시스템의 성능을 측정하기 위해 5개의 노드로 구성된 클러스터에서 LUBM 데이터셋에 대한 OWL/RDFS 추론을 수행하고, 데이터의 추가, 설명, 제거에 대한 실험을 수행하였다. LUBM2000에 대하여 추론을 수행한 결과 80GB데이터가 추론되었고, ATMS에 적용하여 추가, 설명, 제거에 대하여 수초 내에 처리하는 성능을 보였다.

참고문헌 (Reference)

1 김제민, "온톨로지의 비논리적 개념을 유발하는 공리 탐지 기법" 한국정보과학회 39 (39): 464-472, 2012

2 T. Cronin, "Using An Assumption-Based Truth Maintenance System to Switch Context during Data Fusion Processing" 1991

3 M. Zaharia, "Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing" 2-2, 2012

4 F. F. Monai, "Possibilistic Assumption based Truth Maintenance System, Validation in a Data Fusion Application" 83-91, 1992

5 Ren, Y., "Optimizing Ontology Stream Reasoning with Truth Maintenance System" 831-836, 2011

6 Johan de Kleer, "Massively Parallel ATMS" 199-204, 1988

7 T.-H. Ngair, "Focusing ATMS Problem-Solving: Formal Approach" 1992

8 J. Urbani, "DynamiTE: Parallel Materialization of Dynamic RDF Data" 657-672, 2013

9 N. Hai, "Axiom Pinpointing Using an Assumption-Based Truth Maintenance System" 290-300, 2012

10 J. Jones, "An Assumptionbased Truth Maintenance System in Active Aid for UNIX Users" 14 : 229-252, 2000

11 J.C. Madre, "A Logically Complete Reasoning Maintenance System Based on a Logical Constraint Solver" 1 : 294-299, 1991

12 J. D. Kleer, "A General Labeling Algorithm for Assumption-based Truth Maintenance" 188-192, 1988