wiki:similarity_SimFlood

Context Navigation

Version 4 (modified by endres, 18 years ago) (diff)
--

TracNav?

Similarity Measure: Similarity Flooding

Developers: Malte Kiesel Björn Endres Lizhen Qu

Description

This module 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 efficiently with huge ontologies.

Original SF

Developers: Malte Kiesel Lizhen Qu Björn Endres

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.

Characteristics

Every call of either calcSimilarities() or calcSimilarity() results in a new calculation of similarity values.

Evaluation/Performance

TODO

Specification

Intitialisation

The SimilarityMeasure class is

de.dfki.km.phaselib.impl.similarities.sf.SimFlood

Initialisation is straight forward (new SimFlood())

Parameters

none

Dependencies

colt - an efficient scientific library used here for matrix based calculation.

Optimized SF

Developer: Lizhen Qu

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.

Characteristics

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 pairwise connectivity graphs for later fixpoint computation. Three 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 two 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.