Enriching One Taxonomy Using Another
Taxonomies, representing hierarchical data, are a key knowledge source in multiple disciplines. Information processing across taxonomies is not possible unless they are appropriately merged for commonalities and differences. For taxonomy merging, the first task is to identify common concepts between the taxonomies. Then, these common concepts along with their associated concepts in the two taxonomies need to be integrated. Doing this in a conflict-free manner is a challenging task and generally requires human intervention. In this paper, we explore the possibility of asymmetrically merging one taxonomy into another automatically. Given one or more source taxonomies and a destination taxonomy, modeled as directed acyclic graphs, we present intuitive algorithms that merge relevant portions of the source taxonomies into the destination taxonomy. We prove that our algorithms are conflict-free, information lossless, and scalable. We also define precision and recall measures for evaluating enriched taxonomies, such as T(A), the result of merging two taxonomies, with T(I), the ideal merger. Our experiments indicate the effectiveness of our approach.
taxonomy merging graph merging algorithms