Extracting multiple layers from data having graph structures

作     者：ITOKAWA Yuko UCHIDA Tomoyuki NAKAMURA Yasuaki 

作者机构：Faculty of Human and Social Environment Hiroshima International UniversityKurose 724 0695 JapanFaculty of Information Sciences Hiroshima City UniversityHiroshima 731 3194 JapanFaculty of Information Sciences Hiroshima City UniversityHiroshima 731 3194 Japan 

出 版 物：《重庆邮电学院学报（自然科学版）》 (Journal of Chongqing University of Posts and Telecommunications(Natural Sciences Edition))

年 卷 期：2004年第16卷第5期

页      面：149-155页

学科分类：081603[工学-地图制图学与地理信息工程] 081802[工学-地球探测与信息技术] 07[理学] 08[工学] 080203[工学-机械设计及理论] 070503[理学-地图学与地理信息系统] 0818[工学-地质资源与地质工程] 0705[理学-地理学] 0816[工学-测绘科学与技术] 0802[工学-机械工程] 

主　　题：图表结构 最小多层结构 几何图象数据 GIS 

摘      要：Much data such as geometric image data and drawings have graph structures. Such data are called graph structured data. In order to manage efficiently such graph structured data, we need to analyze and abstract graph structures of such data. The purpose of this paper is to find knowledge representations which indicate plural abstractions of graph structured data. Firstly, we introduce a term graph as a graph pattern having structural variables, and a substitution over term graphs which is graph rewriting system. Next, for a graph G, we define a multiple layer ( g,(θ 1,…,θ k )) of G as a pair of a term graph g and a list of k substitutions θ 1,…,θ k such that G can be obtained from g by applying substitutions θ 1,…,θ k to g. In the same way, for a set S of graphs, we also define a multiple layer for S as a pair ( D,Θ ) of a set D of term graphs and a list Θ of substitutions. Secondly, for a graph G and a set S of graphs, we present effective algorithms for extracting minimal multiple layers of G and S which give us stratifying abstractions of G and S, respectively. Finally, we report experimental results obtained by applying our algorithms to both artificial data and drawings of power plants which are real world data.