Merging taxonomies under RCC-5 algebraic articulations

ABSTRACT

Taxonomies are widely used to classify information, and multiple (possibly competing) taxonomies often exist for the same domain. Given a set of correspondences between two taxonomies, it is often necessary to "merge" the taxonomies, thereby creating a unified taxonomy (e.g., that can then be used by data integration and discovery applications). We present an algorithm for merging taxonomies that have been related using articulations given as RCC-5 constraints. Two taxa N and M can be related using (disjunctions of) the five base relations in RCC-5: N a M; N -- M; N -- M; N -- M (partial overlap of N and M); and N ! M (disjointness: N ) M = Ø). RCC-5 is increasingly being adopted by scientists to specify mappings between large species taxonomies. We discuss the properties of the proposed merge algorithm and evaluate our approach using real-world biological taxonomies.

REFERENCES

• 1: A. V. Aho, M. R. Garey, and J. D. Ullman. The transitive reduction of a directed graph. SIAM J. Comput., 1(2):131--137, 1972.
• 2: K. D. Bailey. Typologies and Taxonomies: An Introduction to Classification Techniques. Sage Publications, Inc, 1994.
• 3: B. Bennett. Spatial reasoning with propositional logics. In J. Doyle, E. Sandewall, and P. Torasso, editors, KR'94: Principles of Knowledge Representation and Reasoning, pages 51--62. Morgan Kaufmann, San Francisco, California, 1994.
• 4: W. G. Berendsohn. MoReTax -- Handling Factual Information Linked to Taxonomic Concepts in Biology. Number 39 in Schriftenreihe für Vegetationskunde. Bundesamt für Naturschutz, 2003.
• 5: R. J. Brachman, What IS-A Is and Isn't: An Analysis of Taxonomic Links in Semantic Networks, Computer, v.16 n.10, p.30-36, October 1983 [doi>10.1109/MC.1983.1654194]
• 6: R. Côté, D. Rothwell, and L. Brochu, editors. SNOMED international : the systematized nomenclature of human and veterinary medicine. College of American Pathologists, Northfield, Ill., 3rd edition, 1993.
• 7: W. F. Doolittle. Phylogenetic classification and the universal tree. Science, 284(5423):2124--2128, 1999.
• 8: D. Dou, D. McDermott, and P. Qi. Ontology translation on the semantic web. In International Conference on Ontologies, Databases and Applications, 2004.
• 9: Marc Ehrig, Ontology Alignment: Bridging the Semantic Gap (Semantic Web and Beyond), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 10: J. Euzenat. State of the art on ontology alignment. http://www.starlab.vub.ac.be/publications/kweb-223.pdf, 2004.
• 11: N. M. Franz, R. K. Peet, and A. S. Weakley. On the use of taxonomic concepts in support of biodiversity research and taxonomy. Proceedings of the New Taxonomy Symposium, 2006.
• 12: S. Henikoff, E. A. Greene, S. Pietrokovski, P. Bork, T. K. Attwood, and L. Hood. Gene families: The taxonomy of protein paralogs and chimeras. Science, 278(5338):609--614, 1997.
• 13: Yannis E. Ioannidis , Raghu Ramakrishnan, Efficient Transitive Closure Algorithms, Proceedings of the 14th International Conference on Very Large Data Bases, p.382-394, August 29-September 01, 1988
• 14: P. Jonsson and T. Drakengren. A complete classification of tractability in RCC-5. Journal of Artificial Intelligence Research, 6:211--221, 1997.
• 15: J. J. Jung. Taxonomy alignment for interoperability between heterogeneous digital libraries. In S. Sugimoto, J. Hunter, A. Rauber, and A. Morishima, editors, ICADL, volume 4312 of Lecture Notes in Computer Science, pages 274--282. Springer, 2006.
• 16: J. Kennedy, R. Kukla, and T. Paterson. Scientific names are ambiguous as identifiers for biological taxa: Their context and definition are required for accurate data integration. In 2nd Intl. Workshop on Data Integration in the Life Sciences (DILS), LNCS 3615, pages 80--95, July 2005.
• 17: Jaehong Kim , Minsu Jang , Young-Guk Ha , Joo-Chan Sohn , Sang Jo Lee, MoA: OWL ontology merging and alignment tool for the semantic web, Proceedings of the 18th international conference on Innovations in Applied Artificial Intelligence, p.722-731, June 22-24, 2005, Bari, Italy [doi>10.1007/11504894_100]
• 18: M. Klein. Combining and relating ontologies: an analysis of problems and solutions. In A. Gomez-Perez, M. Gruninger, H. Stuckenschmidt, and M. Uschold, editors, Workshop on Ontologies and Information Sharing, IJCAI'01, Seattle, USA, 2001.
• 19: M. Koperski, M. Sauer, W. Braun, and S. Gradstein. Referenzliste der Moose Deutschlands, volume 34. Schriftenreihe Vegetationsk, 2000.
• 20: K. Kotis and G. A. Vouros. The HCONE approach to ontology merging. In C. Bussler, J. Davies, D. Fensel, and R. Studer, editors, ESWS, volume 3053 of Lecture Notes in Computer Science, pages 137--151. Springer, 2004.
• 21: K. Kotis, G. A. Vouros, and K. Stergiou. Towards automatic merging of domain ontologies: The HCONE-merge approach. J. Web Sem., 4(1):60--79, 2006.
• 22: Patrick Lambrix , He Tan, SAMBO-A system for aligning and merging biomedical ontologies, Web Semantics: Science, Services and Agents on the World Wide Web, v.4 n.3, p.196-206, September, 2006 [doi>10.1016/j.websem.2006.05.003]
• 23: C. Linnaeus. Systema Naturae. Laurentii Salvii, Stockholm, 1758.
• 24: Deborah L. McGuinness , Richard Fikes , James Rice , Steve Wilder, The Chimaera Ontology Environment, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.1123-1124, July 30-August 03, 2000
• 25: D. L. McGuinness, R. Fikes, J. Rice, and S. Wilder. An environment for merging and testing large ontologies. In Proc. of the Seventh International Conference on Principles of Knowledge, Breckenridgeand Coloradoand United States, April 2000.
• 26: Natalya F. Noy , Mark A. Musen, The PROMPT suite: interactive tools for ontology merging and mapping, International Journal of Human-Computer Studies, v.59 n.6, p.983-1024, December 2003 [doi>10.1016/j.ijhcs.2003.08.002]
• 27: C. Orengo, A. Michie, S. Jones, D. Jones, M. Swindells, and J. Thornton. CATH - a hierarchic classification of protein domain structures. Structure, 5(8):1093--1108, aug 1997.
• 28: R. K. Peet. Ranunculus data set. June 2005.
• 29: D. A. Randell, Z. Cui, and A. Cohn. A spatial logic based on regions and connection. In B. Nebel, C. Rich, and W. Swartout, editors, KR'92. Principles of Knowledge Representation and Reasoning: Proceedings of the Third International Conference, pages 165--176. Morgan Kaufmann, San Mateo, California, 1992.
• 30: Jochen Renz , Bernhard Nebel, On the complexity of qualitative spatial reasoning: a maximal tractable fragment of the region connection calculus, Artificial Intelligence, v.108 n.1-2, p.69-123, March 1999 [doi>10.1016/S0004-3702(99)00002-8]
• 31: Alexandre Riazanov , Andrei Voronkov, The design and implementation of VAMPIRE, AI Communications, v.15 n.2, p.91-110, September 2002
• 32: S. S. Staff. Soil taxonomy. A basic system of soil classification for making and interpreting soil surveys. Number 436 in Soil Conservation Service Agricultural Handbook. United States Department of Agriculture, 1975.
• 33: G. Stumme and A. Maedche. FCA-MERGE: Bottom-Up Merging of Ontologies. In Proc. of the 17th International Joint Conference on Artificial, pages 225--234, 2001.
• 34: G. Stumme and A. Maedche. Ontology merging for federated ontologies on the semantic web, 2001.
• 35: David Thau, Reasoning about taxonomies and articulations, Proceedings of the 2008 EDBT Ph.D. workshop, March 25-25, 2008, Nantes, France [doi>10.1145/1387150.1387153]
• 36: D. Thau and B. Ludäscher. Reasoning about taxonomies in first-order logic. Ecological Informatics, 2(3):195--209, 2007.
• 37: M. Wessel. On spatial reasoning with description logics-position paper. In I. Horrocks and S. Tessaris, editors, Proceedings of the International Workshop in Description Logics, pages 156--163, Touluse, France, April 2002. CEUR Workshop Proceedings.
• 38: W.W.McCune. Prover 9: http://www.cs.unm.edu/mccune/prover9/, July 2008.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.12 Interoperability

  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Algorithms

Keywords:
automated deduction (reasoning), merging, taxonomies