Changes between Version 9 and Version 10 of similarity_SimFlood
 Timestamp:
 09/25/06 18:02:03 (11 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

similarity_SimFlood
v9 v10 2 2 3 3 = Similarity Measure: Similarity Flooding = 4 Developers: [mailto:kiesel @dfki.unikl.de Malte Kiesel] [mailto:endres@dfki.unikl.de Björn Endres] [mailto:Lizhen.Qu@dfki.de Lizhen Qu]4 Developers: [mailto:kiesel(at)dfki.unikl.de Malte Kiesel] [mailto:endres(at)dfki.unikl.de Björn Endres] [mailto:Lizhen.Qu(at)dfki.de Lizhen Qu] 5 5 6 6 == Description == 7 This module is based on the algorithm similarity flooding from Sergey Melnik, Hector GarciaMolina and Erhard Rahm. The detailed description of the algorithmus can be found at [http://wwwdb.stanford.edu/~melnik/mm/sfa/ Similarity Flooding: A Versatile Graph Matching Algorithm]. Besides a implementation of the original algorithmus, [mailto:Lizhen.Qu @dfki.de Lizhen Qu] provides a optimized version to make it run more efficiently with huge ontologies.7 This module is based on the algorithm similarity flooding from Sergey Melnik, Hector GarciaMolina and Erhard Rahm. The detailed description of the algorithmus can be found at [http://wwwdb.stanford.edu/~melnik/mm/sfa/ Similarity Flooding: A Versatile Graph Matching Algorithm]. Besides a implementation of the original algorithmus, [mailto:Lizhen.Qu(at)dfki.de Lizhen Qu] provides a optimized version to make it run more efficiently with huge ontologies. 8 8 9 9  10 10 11 11 = Original SF = 12 Developers: [mailto:kiesel @dfki.unikl.de Malte Kiesel] [mailto:Lizhen.Qu@dfki.de Lizhen Qu] [mailto:endres@dfki.unikl.de Björn Endres]12 Developers: [mailto:kiesel(at)dfki.unikl.de Malte Kiesel] [mailto:Lizhen.Qu(at)dfki.de Lizhen Qu] [mailto:endres(at)dfki.unikl.de Björn Endres] 13 13 14 14 The original SF takes a matrix calculation based approach, the library colt supporting efficient matrix calculations. The whole implementation is achieved through the two classes Graph and SimFlood. The class Graph is used for several purposes: A graph model representing the Ontology, a data structure for pairwise connectivity graph (PCG) and the conversion from the PCG to the induced propagation graph (IPG). The IPG is represented as an object of cern.colt.matrix.DoubleMatrix2D. The class SimFlood, which implements the SimilarityMeasure, calculates the similarity values from IPG and stores them in an object of class de.dfki.km.phaselib.impl.similarities.common.SFSimilarityMatrix. … … 37 37 38 38 = Optimized SF = 39 Developer: [mailto:Lizhen.Qu @dfki.de Lizhen Qu]39 Developer: [mailto:Lizhen.Qu(at)dfki.de Lizhen Qu] 40 40 41 41 The central class of the optimized SF is SimilarityMatcher, which implements SimilarityMeasure. OntoGraph describes a model, which is a graph representation of an ontology. A pairwise connectivity graph is represented by PCGGraph. Because IPG is basically a PCG with weighted edges going into two directions, it's also represented by the class PCGGraph. Other than the original implementation, optimized SF uses PCGVertex to store the similarity values, which makes it easier to add new subgraphs later on.