wiki:similarity_SimFlood

Version 2 (modified by lqu, 18 years ago) (diff)

--

Similarity Measure: Similarity Flooding

Developer: Malte Kiesel Björn Endres Lizhen Qu

Description

This 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 Similarity Flooding: A Versatile Graph Matching Algorithm. Besides a implementation of the original algorithmus, Lizhen Qu provides a optimized version to make it run more efficient under huge onologies.

Specification

The original version from Malte Kiesel 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.

original SF

The 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.

dependencies

colt a efficient scientific library is used here for matrix based calculation.

optimized SF

The 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.

The 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. The optimized SF allows also setting different fixpoint computing formula introduced in article Similarity Flooding: A Versatile Graph Matching Algorithm. It uses the same names A, B, C to identify the different formula.

According 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.

dependencies

log4j - logging