Efficient semantic matching-英文文献.pdfVIP

UNIVERSITY OF TRENTO DEPARTMENT OF INFORMATION AND COMMUNICATION TECHNOLOGY 38050 Povo – Trento (Italy), Via Sommarive 14 http://www.dit.unitn.it EFFICIENT SEMANTIC MATCHING Fausto Giunchiglia, Mikalai Yatskevich and Enrico Giunchiglia December 2004 Technical Report # DIT-04- 112 Also: paper accepted to 2nd European Semantic Web Conference (ESWC’05) . Efficient Semantic Matching 1 1 2 Fausto Giunchiglia , Mikalai Yatskevich , Enrico Giunchiglia 1 Dept. of Information and Communication Technology University of Trento, 38050 Povo, Trento, Italy {fausto, yatskevi}@dit.unitn.it 2 DIST – Universita di Genova Viale Causa 13, 16165, Genova, Italy enrico@dist.unige.it Abstract. We think of Match as an operator which takes two graph-like structures and produces a mapping between semantically related nodes. We concentrate on classifications with tree structures. In semantic matching, correspondences are discovered by translating the natural language labels of nodes into propositional formulas, and by codifying matching into a propositional unsatisfiability problem. We distinguish between problems with conjunctive formulas and problems with disjunctive formulas, and present various optimizations. For instance, we propose a linear time algorithm which solves