Mining Relatednsess Graphs for Data Integration.

Mining Relatedness Graphs for Data Integration Jeremy T. Engle (jtengle@indiana.edu) Ying Feng (yingfeng@indiana.edu) Robert L. Goldstone (rgoldsto@indiana.edu) Indiana University Bloomington, IN. 47405 USA Abstract In this paper, we present the AbsMatcher system for schema matching which uses a graph based approach. The primary contribution of this paper is the development of new types of relationships for generating graph edges and the effectiveness of integrating schemas using those graphs. AbsMatcher creates a graph of related attributes within a schema, mines similarity between attributes in different schemas, and then combines all information using the ABSURDIST graph matching algorithm. The attribute-to-attribute relationships this paper focuses on are semantic in nature and have few requirements for format or structure. These relationships sources provide a baseline which can be improved upon with relationships specific to formats, such as XML or a relational database. Simulations demonstrate how the use of automatically mined graphs of within-schema relationships, when combined with cross-schema pair-wise similarity, can result in matching accuracy not attainable by either source of information on its own. Keywords: Data integration; graph matching; ABSURDIST; semantic relatedness. Introduction Data integration has application to a wide variety of fields from e-commerce to bioinformatics. One of data integration’s subtopics is the attribute matching problem which finds mappings between attributes in source and target data sets. This paper presents the AbsMatcher framework which concentrates on one-to-one attribute matches as an initial effort, leaving complex n-to-one matches to future work. AbsMatcher finds matching results based on graphs of within-schema attribute relationships and cross-schema comparisons of attribute similarity. The focus of in this paper is the process and relationships used to create a within-schema graph for each data set. The AbsMatcher framework has two distinct phases. The first is a mining phase which produces a graph for each data set where edges relate within-schema attributes and an aggregated matrix of cross-schema attribute similarities measures. We refer to these graphs as internal information, because a graph only contains information relating attributes within the same schema. Information which is aggregated into the cross-schema matrix is referred to as external information because it involves a comparison between attributes in different schemas to determine how semantically similar they are. Secondly, AbsMatcher's matching phase uses the ABSURDIST (Feng, Goldstone, & Menkov, 2004; Goldstone & Rogosky, 2002) algorithm to combine mined information and determine match correspondences using an iteratively converging global optimization algorithm. ABSURDIST was originally developed to translate between conceptual systems in a psychologically plausible manner. Additionally, ABSURDIST has a weighting ratio to determine the balance of influence on the outcome of internal and external information. Though we focus on specific sources of internal and external information in this paper both AbsMatcher and ABSURDIST were designed in a way so that additional sources could easily be added. In a graph based approach to schema matching the matching process uses graph matching to determine mappings between attributes/nodes based on the similarity of their sets of relationships/edges. Edges of graphs are labeled with different relationship types, which represent different forms of information. Relationship types can broadly be divided into structural relationships which are based on how attributes are organized in a data set and semantic relationships which are based on meaning of the information associated with an attribute. An example of a structural relationship is a parent/child relationship between nested attributes from an XML data set. An example of a semantic relationship is a general/specific relationship for the concepts represented by two attributes. These examples highlight that one of the challenges in how to create graphs is that what relationships can be used is tied to the format of a data set and the available (meta)data. Previous systems (Aumueller, Do, Massmann, & Rham, 2005; Giunchiglia & Shvaiko, 2003; Melnik, Garcia- Molina, & Rahm, 2002) address the problem of how to create graphs by only using metadata which can be intuitively translated to graph form. As a result, the graphs created by these translations predominately represent the structural design of a data set. Though structural relationships can be useful, their disadvantage is that factors such as missing metadata, differing metadata formats, or different database designers can remove these structural relationships’ usefulness.