Changes between Version 1 and Version 2 of similarity_SimFlood


Ignore:
Timestamp:
05/02/06 00:24:11 (18 years ago)
Author:
lqu
Comment:

--

Legend:

Unmodified
Added
Removed
Modified

  • similarity_SimFlood

    v1 v2  
    33 
    44== Description == 
    5 This is based on the algorithmus similarity flooding from Sergey Melnik,Hector Garcia-Molina and Erhard Rahm. The detailed description of the algorithmus can be found at [http://www-db.stanford.edu/~melnik/mm/sfa/]. Besides a implementation of the original algorithmus, [mailto:Lizhen.Qu@dfki.de Lizhen Qu] provides a optimized version to make it more efficient under huge onologies.  
     5This is based on the algorithm similarity flooding from Sergey Melnik,Hector Garcia-Molina and Erhard Rahm. The detailed description of the algorithmus can be found at [http://www-db.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 efficient under huge onologies.  
    66 
    77 
    88== Specification == 
    9 The 2 versions of similarity flooding are provided by  
    10 === original === 
    11 === optimized === 
    12 The optimization is achieved by dividing the whole graph into several subgraphs. 
     9The original version from [mailto:kiesel@dfki.uni-kl.de Malte Kiesel] [mailto:endres@dfki.uni-kl.de Björn Endres] is under namespace de.dfki.km.phaselib.impl.similarities.sf. The opimized one is under de.dfki.km.phaselib.impl.similarities.sf.optimized. The usage of this similarity measure is no different than the other similarity measures, just call the corresponding methods that inherit from de.dfki.km.phaselib.model.evidence.SimilarityMeasure. 
    1310 
     11=== original SF === 
     12The original SF takes a matrix calculation based approach. The library colt enables the efficient matrix calculation. The whole implementation is achieved through 2 classes Graph and SimFlood. The class Graph is used for several purposes: A graph model representing the Ontology, a data structure for paarwise connectivity graph (PCG) and conversion from PCG to induced propagation graph(IPG). IPG is represented as an object of cern.colt.matrix.DoubleMatrix2D. The class SimFlood, which implements de.dfki.km.phaselib.model.evidence.SimilarityMeasure, calculates the similarity values from IPG and stores them in an object of class de.dfki.km.phaselib.impl.similarities.common.SFSimilarityMatrix. Every call of either calcSimilarities() or calcSimilarity results in a new calculation of similarity values.  
    1413 
     14==== dependencies ==== 
     15[http://hoschek.home.cern.ch/hoschek/colt/ colt] a efficient scientific library is used here for matrix based calculation. 
     16=== optimized SF === 
     17The central class of optimized SF is SimilarityMatcher, which implements SimilarityMeasure. OntoGraph describs a model, which is a graph representation of an ontology. A paarwise connectivity graph is represented by PCGGraph. Because IPG is basically a PCG with weighted edges going in 2 directions, it's also represented by the class PCGGraph. Other than the original implementation, optimized SF uses PCGVertex to store the similarity values, which make it easier to add new subgraphs latter on. 
    1518 
     19The similarity flooding (SF) is optimized through dividing the whole graph representing a ontology into several subgraphs. It tries to create a set of minimal paarwise connectivity graphs for latter fixpoint computation. 3 policies are adopted to create the subgraphs. According to the default one Taxonomy an OntoGraph object is created from each given class of the class pair. The graph objects contain all the classes having is-a relations to the given classes or vice versa. Then a paarwise connectivity graph is generated from the 2 OntoGraph objects. The other policy SuperSubClsOnly includes all the superclasses and subclasses of the given class pair, the superclasses of superclasses and subclasses of subclasses are considered. The vertices belonging to the same derivation level can make a combinatorisch PCG vertex. The vertices from different level will not make a PCG vertex. The last policy All provides the same result as the original implementation.  
     20The optimized SF allows also setting different fixpoint computing formula introduced in article [http://www-db.stanford.edu/~melnik/mm/sfa/ Similarity Flooding: A Versatile Graph Matching Algorithm]. It uses the same names A, B, C to identify the different formula.  
    1621 
    17 === Dependencies === 
     22According to policies SuperSubClsOnly and Taxonomy, new subgraphs will be added if required. To avoid computation overhead, the new graph will be firstly merged into the existing subgraphs, if the same vertex is found in the existing subgraphs, the existing ones will take place of the new ones. Then the subgraphs having the same vertices will be marked as dirty. A fixpoint computation will run on the new graph and the dirty graphs.    
     23 
     24==== dependencies ==== 
     25log4j - logging 
     26