SSQUSAR: Apache Spark SQL을 이용한 대용량 정성 공간 추론기
SSQUSAR: A Large-Scale Qualitative Spatial Reasoner Using Apache Spark SQL
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 Apache Spark SQL을 이용하여 임의의 두 공간 객체들 간의 위상 관계와 방향 관계를 나타내는 새로운 정성 공간 지식을 효율적으로 추론해내는 대용량 정성 공간 추론기의 설계와 구현에 대해 소개한다. Apache Spark SQL은 Hadoop 클러스터 컴퓨터 시스템에서 다양한 데이터들 간의 매우 효율적인 조인 연산과 질의 처리 기능을 제공하는 분산 병렬 프로그래밍 환경이다. 본 공간 추론기에서는 정성 공간 추론의 전체 과정을 지식 인코딩, 역 관계 추론, 동일 관계 추론, 이행 관계 추론, 관계 정제, 지식 디코딩 등 크게 총 6개의 작업들로 나누고, 논리적 인과관계와 계산 효율성을 고려하여 작업들 간의 처리 순서를 결정하였다. 지식 인코딩 작업에서는 추론의 전처리 과정으로서 XML/RDF 형태의 입력 지식을 보다 간략한 내부 형태로 변환함으로써, 추론 대상인 지식 베이스의 크기를 축소시켰다. 일반적으로 이행 관계 추론 작업과 관계 정제 작업의 반복은 정성 공간 추론에 필요한 가장 많은 계산 시간과 기억 공간을 소모한다. 이 작업들을 효율화하기 위해 본 공간 추론기에서는 공간 추론에 필요한 최소한의 이접 관계들을 찾아내고, 이들을 기반으로 이행 관계 추론을 위한 조합표를 큰 폭으로 축소하고 관계 정제 작업도 최적화하였다. 대규모 벤치마킹 공간 지식 베이스를 이용한 실험을 통해, 본 논문에서 제안하는 대용량 정성 공간 추론기의 높은 추론 성능과 확장성을 확인하였다.
Abstract
In this paper, we present the design and implementation of a large-scale qualitative spatial reasoner, which can derive new qualitative spatial knowledge representing both topological and directional relationships between two arbitrary spatial objects in efficient way using Aparch Spark SQL. Apache Spark SQL is well known as a distributed parallel programming environment which provides both efficient join operations and query processing functions over a variety of data in Hadoop cluster computer systems. In our spatial reasoner, the overall reasoning process is divided into 6 jobs such as knowledge encoding, inverse reasoning, equal reasoning, transitive reasoning, relation refining, knowledge decoding, and then the execution order over the reasoning jobs is determined in consideration of both logical causal relationships and computational efficiency. The knowledge encoding job reduces the size of knowledge base to reason over by transforming the input knowledge of XML/RDF form into one of more precise form. Repeat of the transitive reasoning job and the relation refining job usually consumes most of computational time and storage for the overall reasoning process. In order to improve the jobs, our reasoner finds out the minimal disjunctive relations for qualitative spatial reasoning, and then, based upon them, it not only reduces the composition table to be used for the transitive reasoning job, but also optimizes the relation refining job. Through experiments using a large-scale benchmarking spatial knowledge base, the proposed reasoner showed high performance and scalability.
참고문헌 (18)
- J. Renz, "Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis", Proceedings of IJCAI (1999)
- D. J. Peuquet, "An Algorithm to Determine the Directional Relationship between Arbirtrarily-Shaped Polygons in the Plane", Pattern Recognition, 20(1), pp.65~74 (1987)
- R. Moratz, "Qualitative Spatial Reasoning about Relative Point Position", Journal of Visual Languages and Computing, 19(1), pp.75~98 (2008)
- B. Gottfried, "Tripartite Line Tracks Qualitative Curvature Information", International Conference on Spatial Information Theory, pp.101~117 (2003), Springer
- Z. Gantner, "GQR-A Fast Reasoner for Binary Qualitative Constraint Calculi", Proceedings of AAAI, 8 (2008)
- S. Batsakis, "SOWL : A Framework for Handling Spatio-Temporal Information in OWL 2. 0", International Workshop on Rules and Rule Markup Languages for the Semantic Web, pp.242~249 (2014), Springer
- M. Stocker, "PelletSpatial : A Hybrid RCC-8 and RDF", OWL Reasoning and Query Engine, 2009, pp.529, 39~48
- G. Christodoulou, "CHOROS: A Reasoning and Query Engine for Qualitative Spatial Information", pp.2011
- 남상하, "방향 및 위상 관계들 간의 교차-일관성 검사를 지원하는 정성적 공간 추론기", 정보과학회 컴퓨팅의 실제 논문지, 20(4), pp.248~252 (2014), 한국정보과학회
- I. Horrocks, "SWRL: A Semantic Web Rule Language Combining OWL and RuleML", W3C Member Submission, ~ (2004)
- J. Dean, "MapReduce: Simplified Data Processing on Large Clusters", Communications of the ACM (2008)
- 남상하, "맵리듀스 프레임워크를 이용한 대용량 공간 추론기의 설계 및 구현", 정보처리학회논문지. 소프트웨어 및 데이터 공학, 3(10), pp.397~406 (2014), 한국정보처리학회[DOI]
- M. Zaharia, "Spark : Cluster Computing with Working Sets", Proceedings of HotCloud 2010 (2010)
- M. Armbrust, "Spark Sql: Relational Data Processing in Spark", Proceedings of the 2015 ACM SIGMOD Intemational Conference on Management of Data, pp.1383~1394 (2015)
- 김종환, "SPQUSAR : Apache Spark를 이용한 대용량의 정성적 공간 추론기", 정보과학회 컴퓨팅의 실제 논문지, 21(12), pp.774~779 (2015), 한국정보과학회
- R. Battle, "Enabling the Geospatial Semantic Web with Parliament and GeoSPARQL", Semantic Web Journal, 3(4), pp.355~370 (2012)
- P. van Beek, "The Design and Experimental Analysis of Algorithms for Temporal Reasoning", Journal of Artificial Inteligence Research, 4(1), pp.1~8 (1996)
- J. Renz, "Efficient Methods for Qualitative Spatial Reasoning", Proceedings of the 13th European Conference on Artificial Inteligence (1998)