[DL-Learner SVN] SF.net SVN: dl-learner:[4108] trunk/components-core

[<lor...@us...>]

Revision: 4108
          http://sourceforge.net/p/dl-learner/code/4108
Author:   lorenz_b
Date:     2013-09-14 06:45:10 +0000 (Sat, 14 Sep 2013)
Log Message:
-----------
Extended fragment extraction.

Modified Paths:
--------------
    trunk/components-core/pom.xml
    trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java
    trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java
    trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/impl/QueryTreeFactoryImpl.java
    trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/impl/QueryTreeFactoryImpl2.java
    trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/NBR.java
    trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/EvaluatedQueryTree.java
    trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/LGGGeneratorImpl.java
    trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGG.java
    trunk/components-core/src/test/java/org/dllearner/algorithms/qtl/LGGTest.java

Added Paths:
-----------
    trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/FragmentExtractionStrategy.java
    trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/FragmentExtractor.java
    trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/IndividualBasedFragmentExtractor.java
    trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/MaximumModalDepthDetector.java
    trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/PatternBasedAxiomLearningAlgorithm.java
    trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/TimeBasedFragmentExtractor.java
    trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGGMultithreaded.java

Modified: trunk/components-core/pom.xml
===================================================================
--- trunk/components-core/pom.xml	2013-09-10 15:52:48 UTC (rev 4107)
+++ trunk/components-core/pom.xml	2013-09-14 06:45:10 UTC (rev 4108)
@@ -314,6 +314,11 @@
       <artifactId>jwnl</artifactId>
       <version>1.4.1.RC2</version>
     </dependency>
+		<dependency>
+			<groupId>org.apache.commons</groupId>
+			<artifactId>commons-math3</artifactId>
+			<version>3.1.1</version>
+		</dependency>
 	</dependencies>
 	<dependencyManagement>
 		<dependencies>

Added: trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/FragmentExtractionStrategy.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/FragmentExtractionStrategy.java	                        (rev 0)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/FragmentExtractionStrategy.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -0,0 +1,20 @@
+/**
+ * 
+ */
+package org.dllearner.algorithms.pattern;
+
+/**
+ * @author Lorenz Buehmann
+ *
+ */
+public enum FragmentExtractionStrategy {
+
+	/**
+	 * Extract a fragment based on a given number of examples.
+	 */
+	INDIVIDUALS,
+	/**
+	 * Extract as much information as possible in a given time.
+	 */
+	TIME
+}

Added: trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/FragmentExtractor.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/FragmentExtractor.java	                        (rev 0)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/FragmentExtractor.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -0,0 +1,23 @@
+/**
+ * 
+ */
+package org.dllearner.algorithms.pattern;
+
+import org.dllearner.core.owl.NamedClass;
+
+import com.hp.hpl.jena.rdf.model.Model;
+
+/**
+ * @author Lorenz Buehmann
+ *
+ */
+public interface FragmentExtractor {
+	
+	/**
+	 * @param cls
+	 * @param maxFragmentDepth
+	 * @return
+	 */
+	Model extractFragment(NamedClass cls, int maxFragmentDepth);
+
+}

Added: trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/IndividualBasedFragmentExtractor.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/IndividualBasedFragmentExtractor.java	                        (rev 0)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/IndividualBasedFragmentExtractor.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -0,0 +1,109 @@
+/**
+ * 
+ */
+package org.dllearner.algorithms.pattern;
+
+import java.sql.SQLException;
+import java.util.HashSet;
+import java.util.Set;
+import java.util.concurrent.TimeUnit;
+
+import org.aksw.jena_sparql_api.cache.core.QueryExecutionFactoryCacheEx;
+import org.aksw.jena_sparql_api.cache.extra.CacheCoreEx;
+import org.aksw.jena_sparql_api.cache.extra.CacheCoreH2;
+import org.aksw.jena_sparql_api.cache.extra.CacheEx;
+import org.aksw.jena_sparql_api.cache.extra.CacheExImpl;
+import org.aksw.jena_sparql_api.core.QueryExecutionFactory;
+import org.dllearner.core.owl.Individual;
+import org.dllearner.core.owl.NamedClass;
+import org.dllearner.kb.SparqlEndpointKS;
+import org.dllearner.kb.sparql.ConciseBoundedDescriptionGenerator;
+import org.dllearner.kb.sparql.ConciseBoundedDescriptionGeneratorImpl;
+import org.dllearner.kb.sparql.QueryExecutionFactoryHttp;
+import org.dllearner.kb.sparql.SparqlEndpoint;
+
+import com.hp.hpl.jena.query.QueryExecution;
+import com.hp.hpl.jena.query.QuerySolution;
+import com.hp.hpl.jena.query.ResultSet;
+import com.hp.hpl.jena.rdf.model.Model;
+import com.hp.hpl.jena.rdf.model.ModelFactory;
+
+/**
+ * @author Lorenz Buehmann
+ *
+ */
+public class IndividualBasedFragmentExtractor implements FragmentExtractor{
+	
+	public static final FragmentExtractionStrategy extractionStrategy = FragmentExtractionStrategy.INDIVIDUALS;
+	private QueryExecutionFactory qef;
+	
+	private long maxNrOfIndividuals;
+	private long startTime;
+	
+	private ConciseBoundedDescriptionGenerator cbdGen;
+	
+	public IndividualBasedFragmentExtractor(SparqlEndpointKS ks, String cacheDir, int maxNrOfIndividuals) {
+		this.maxNrOfIndividuals = maxNrOfIndividuals;
+		
+		SparqlEndpoint endpoint = ks.getEndpoint();
+		
+		qef = new QueryExecutionFactoryHttp(endpoint.getURL().toString(), endpoint.getDefaultGraphURIs());
+		if(cacheDir != null){
+			try {
+				long timeToLive = TimeUnit.DAYS.toMillis(30);
+				CacheCoreEx cacheBackend = CacheCoreH2.create(cacheDir, timeToLive, true);
+				CacheEx cacheFrontend = new CacheExImpl(cacheBackend);
+				qef = new QueryExecutionFactoryCacheEx(qef, cacheFrontend);
+			} catch (ClassNotFoundException e) {
+				e.printStackTrace();
+			} catch (SQLException e) {
+				e.printStackTrace();
+			}
+		}
+		
+		cbdGen = new ConciseBoundedDescriptionGeneratorImpl(endpoint, cacheDir);
+	}
+	
+	public IndividualBasedFragmentExtractor(SparqlEndpointKS ks, int maxNrOfIndividuals) {
+		this(ks, null, maxNrOfIndividuals);
+	}
+
+	/* (non-Javadoc)
+	 * @see org.dllearner.algorithms.pattern.FragmentExtractor#extractFragment(org.dllearner.core.owl.NamedClass)
+	 */
+	@Override
+	public Model extractFragment(NamedClass cls, int maxFragmentDepth) {
+		startTime = System.currentTimeMillis();
+		Model fragment = ModelFactory.createDefaultModel();
+		
+		//get some random individuals
+		Set<Individual> individuals = getRandomIndividuals(cls);
+		
+		//get for each individual the CBD
+		Model cbd;
+		for (Individual ind : individuals) {
+			cbd = cbdGen.getConciseBoundedDescription(ind.getName(), maxFragmentDepth);
+			fragment.add(cbd);
+		}
+		return fragment;
+	}
+	
+	private Set<Individual> getRandomIndividuals(NamedClass cls){
+		Set<Individual> individuals = new HashSet<Individual>();
+		
+		String query = "SELECT ?s WHERE {?s a <" + cls.getName() + ">} LIMIT " + maxNrOfIndividuals;
+		QueryExecution qe = qef.createQueryExecution(query);
+		ResultSet rs = qe.execSelect();
+		QuerySolution qs;
+		while(rs.hasNext()){
+			qs = rs.next();
+			if(qs.get("s").isURIResource()){
+				individuals.add(new Individual(qs.getResource("s").getURI()));
+			}
+			
+		}
+		qe.close();
+		
+		return individuals;
+	}
+}

Added: trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/MaximumModalDepthDetector.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/MaximumModalDepthDetector.java	                        (rev 0)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/MaximumModalDepthDetector.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -0,0 +1,503 @@
+/**
+ * 
+ */
+package org.dllearner.algorithms.pattern;
+
+import org.semanticweb.owlapi.model.OWLAnnotationAssertionAxiom;
+import org.semanticweb.owlapi.model.OWLAnnotationPropertyDomainAxiom;
+import org.semanticweb.owlapi.model.OWLAnnotationPropertyRangeAxiom;
+import org.semanticweb.owlapi.model.OWLAsymmetricObjectPropertyAxiom;
+import org.semanticweb.owlapi.model.OWLAxiom;
+import org.semanticweb.owlapi.model.OWLAxiomVisitor;
+import org.semanticweb.owlapi.model.OWLClass;
+import org.semanticweb.owlapi.model.OWLClassAssertionAxiom;
+import org.semanticweb.owlapi.model.OWLClassExpression;
+import org.semanticweb.owlapi.model.OWLClassExpressionVisitor;
+import org.semanticweb.owlapi.model.OWLDataAllValuesFrom;
+import org.semanticweb.owlapi.model.OWLDataExactCardinality;
+import org.semanticweb.owlapi.model.OWLDataHasValue;
+import org.semanticweb.owlapi.model.OWLDataMaxCardinality;
+import org.semanticweb.owlapi.model.OWLDataMinCardinality;
+import org.semanticweb.owlapi.model.OWLDataPropertyAssertionAxiom;
+import org.semanticweb.owlapi.model.OWLDataPropertyDomainAxiom;
+import org.semanticweb.owlapi.model.OWLDataPropertyRangeAxiom;
+import org.semanticweb.owlapi.model.OWLDataSomeValuesFrom;
+import org.semanticweb.owlapi.model.OWLDatatypeDefinitionAxiom;
+import org.semanticweb.owlapi.model.OWLDeclarationAxiom;
+import org.semanticweb.owlapi.model.OWLDifferentIndividualsAxiom;
+import org.semanticweb.owlapi.model.OWLDisjointClassesAxiom;
+import org.semanticweb.owlapi.model.OWLDisjointDataPropertiesAxiom;
+import org.semanticweb.owlapi.model.OWLDisjointObjectPropertiesAxiom;
+import org.semanticweb.owlapi.model.OWLDisjointUnionAxiom;
+import org.semanticweb.owlapi.model.OWLEquivalentClassesAxiom;
+import org.semanticweb.owlapi.model.OWLEquivalentDataPropertiesAxiom;
+import org.semanticweb.owlapi.model.OWLEquivalentObjectPropertiesAxiom;
+import org.semanticweb.owlapi.model.OWLFunctionalDataPropertyAxiom;
+import org.semanticweb.owlapi.model.OWLFunctionalObjectPropertyAxiom;
+import org.semanticweb.owlapi.model.OWLHasKeyAxiom;
+import org.semanticweb.owlapi.model.OWLInverseFunctionalObjectPropertyAxiom;
+import org.semanticweb.owlapi.model.OWLInverseObjectPropertiesAxiom;
+import org.semanticweb.owlapi.model.OWLIrreflexiveObjectPropertyAxiom;
+import org.semanticweb.owlapi.model.OWLNegativeDataPropertyAssertionAxiom;
+import org.semanticweb.owlapi.model.OWLNegativeObjectPropertyAssertionAxiom;
+import org.semanticweb.owlapi.model.OWLObjectAllValuesFrom;
+import org.semanticweb.owlapi.model.OWLObjectComplementOf;
+import org.semanticweb.owlapi.model.OWLObjectExactCardinality;
+import org.semanticweb.owlapi.model.OWLObjectHasSelf;
+import org.semanticweb.owlapi.model.OWLObjectHasValue;
+import org.semanticweb.owlapi.model.OWLObjectIntersectionOf;
+import org.semanticweb.owlapi.model.OWLObjectMaxCardinality;
+import org.semanticweb.owlapi.model.OWLObjectMinCardinality;
+import org.semanticweb.owlapi.model.OWLObjectOneOf;
+import org.semanticweb.owlapi.model.OWLObjectPropertyAssertionAxiom;
+import org.semanticweb.owlapi.model.OWLObjectPropertyDomainAxiom;
+import org.semanticweb.owlapi.model.OWLObjectPropertyRangeAxiom;
+import org.semanticweb.owlapi.model.OWLObjectSomeValuesFrom;
+import org.semanticweb.owlapi.model.OWLObjectUnionOf;
+import org.semanticweb.owlapi.model.OWLReflexiveObjectPropertyAxiom;
+import org.semanticweb.owlapi.model.OWLSameIndividualAxiom;
+import org.semanticweb.owlapi.model.OWLSubAnnotationPropertyOfAxiom;
+import org.semanticweb.owlapi.model.OWLSubClassOfAxiom;
+import org.semanticweb.owlapi.model.OWLSubDataPropertyOfAxiom;
+import org.semanticweb.owlapi.model.OWLSubObjectPropertyOfAxiom;
+import org.semanticweb.owlapi.model.OWLSubPropertyChainOfAxiom;
+import org.semanticweb.owlapi.model.OWLSymmetricObjectPropertyAxiom;
+import org.semanticweb.owlapi.model.OWLTransitiveObjectPropertyAxiom;
+import org.semanticweb.owlapi.model.SWRLRule;
+
+import arq.cmdline.ModAlgebra;
+
+/**
+ * @author Lorenz Buehmann
+ *
+ */
+public class MaximumModalDepthDetector implements OWLAxiomVisitor, OWLClassExpressionVisitor{
+	
+	int maxModalDepth;
+	
+	public static int getMaxModalDepth(OWLAxiom axiom){
+		MaximumModalDepthDetector depthDetector = new MaximumModalDepthDetector();
+		axiom.accept(depthDetector);
+		return depthDetector.maxModalDepth;
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAnnotationAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLAnnotationAssertionAxiom)
+	 */
+	@Override
+	public void visit(OWLAnnotationAssertionAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAnnotationAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLSubAnnotationPropertyOfAxiom)
+	 */
+	@Override
+	public void visit(OWLSubAnnotationPropertyOfAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAnnotationAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLAnnotationPropertyDomainAxiom)
+	 */
+	@Override
+	public void visit(OWLAnnotationPropertyDomainAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAnnotationAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLAnnotationPropertyRangeAxiom)
+	 */
+	@Override
+	public void visit(OWLAnnotationPropertyRangeAxiom axiom) {
+	}
+
+	
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLDeclarationAxiom)
+	 */
+	@Override
+	public void visit(OWLDeclarationAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLSubClassOfAxiom)
+	 */
+	@Override
+	public void visit(OWLSubClassOfAxiom axiom) {
+		OWLClassExpression subClass = axiom.getSubClass();
+		subClass.accept(this);
+		int tmp = maxModalDepth;
+		maxModalDepth = 1;
+		OWLClassExpression superClass = axiom.getSuperClass();
+		superClass.accept(this);
+		maxModalDepth = Math.max(tmp, maxModalDepth);
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLNegativeObjectPropertyAssertionAxiom)
+	 */
+	@Override
+	public void visit(OWLNegativeObjectPropertyAssertionAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLAsymmetricObjectPropertyAxiom)
+	 */
+	@Override
+	public void visit(OWLAsymmetricObjectPropertyAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLReflexiveObjectPropertyAxiom)
+	 */
+	@Override
+	public void visit(OWLReflexiveObjectPropertyAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLDisjointClassesAxiom)
+	 */
+	@Override
+	public void visit(OWLDisjointClassesAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLDataPropertyDomainAxiom)
+	 */
+	@Override
+	public void visit(OWLDataPropertyDomainAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLObjectPropertyDomainAxiom)
+	 */
+	@Override
+	public void visit(OWLObjectPropertyDomainAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLEquivalentObjectPropertiesAxiom)
+	 */
+	@Override
+	public void visit(OWLEquivalentObjectPropertiesAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLNegativeDataPropertyAssertionAxiom)
+	 */
+	@Override
+	public void visit(OWLNegativeDataPropertyAssertionAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLDifferentIndividualsAxiom)
+	 */
+	@Override
+	public void visit(OWLDifferentIndividualsAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLDisjointDataPropertiesAxiom)
+	 */
+	@Override
+	public void visit(OWLDisjointDataPropertiesAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLDisjointObjectPropertiesAxiom)
+	 */
+	@Override
+	public void visit(OWLDisjointObjectPropertiesAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLObjectPropertyRangeAxiom)
+	 */
+	@Override
+	public void visit(OWLObjectPropertyRangeAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLObjectPropertyAssertionAxiom)
+	 */
+	@Override
+	public void visit(OWLObjectPropertyAssertionAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLFunctionalObjectPropertyAxiom)
+	 */
+	@Override
+	public void visit(OWLFunctionalObjectPropertyAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLSubObjectPropertyOfAxiom)
+	 */
+	@Override
+	public void visit(OWLSubObjectPropertyOfAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLDisjointUnionAxiom)
+	 */
+	@Override
+	public void visit(OWLDisjointUnionAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLSymmetricObjectPropertyAxiom)
+	 */
+	@Override
+	public void visit(OWLSymmetricObjectPropertyAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLDataPropertyRangeAxiom)
+	 */
+	@Override
+	public void visit(OWLDataPropertyRangeAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLFunctionalDataPropertyAxiom)
+	 */
+	@Override
+	public void visit(OWLFunctionalDataPropertyAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLEquivalentDataPropertiesAxiom)
+	 */
+	@Override
+	public void visit(OWLEquivalentDataPropertiesAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLClassAssertionAxiom)
+	 */
+	@Override
+	public void visit(OWLClassAssertionAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLEquivalentClassesAxiom)
+	 */
+	@Override
+	public void visit(OWLEquivalentClassesAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLDataPropertyAssertionAxiom)
+	 */
+	@Override
+	public void visit(OWLDataPropertyAssertionAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLTransitiveObjectPropertyAxiom)
+	 */
+	@Override
+	public void visit(OWLTransitiveObjectPropertyAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLIrreflexiveObjectPropertyAxiom)
+	 */
+	@Override
+	public void visit(OWLIrreflexiveObjectPropertyAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLSubDataPropertyOfAxiom)
+	 */
+	@Override
+	public void visit(OWLSubDataPropertyOfAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLInverseFunctionalObjectPropertyAxiom)
+	 */
+	@Override
+	public void visit(OWLInverseFunctionalObjectPropertyAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLSameIndividualAxiom)
+	 */
+	@Override
+	public void visit(OWLSameIndividualAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLSubPropertyChainOfAxiom)
+	 */
+	@Override
+	public void visit(OWLSubPropertyChainOfAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLInverseObjectPropertiesAxiom)
+	 */
+	@Override
+	public void visit(OWLInverseObjectPropertiesAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLHasKeyAxiom)
+	 */
+	@Override
+	public void visit(OWLHasKeyAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.OWLDatatypeDefinitionAxiom)
+	 */
+	@Override
+	public void visit(OWLDatatypeDefinitionAxiom axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLAxiomVisitor#visit(org.semanticweb.owlapi.model.SWRLRule)
+	 */
+	@Override
+	public void visit(SWRLRule axiom) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLClass)
+	 */
+	@Override
+	public void visit(OWLClass ce) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLObjectIntersectionOf)
+	 */
+	@Override
+	public void visit(OWLObjectIntersectionOf ce) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLObjectUnionOf)
+	 */
+	@Override
+	public void visit(OWLObjectUnionOf ce) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLObjectComplementOf)
+	 */
+	@Override
+	public void visit(OWLObjectComplementOf ce) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLObjectSomeValuesFrom)
+	 */
+	@Override
+	public void visit(OWLObjectSomeValuesFrom ce) {
+		maxModalDepth++;
+		ce.getFiller().accept(this);
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLObjectAllValuesFrom)
+	 */
+	@Override
+	public void visit(OWLObjectAllValuesFrom ce) {
+		maxModalDepth++;
+		ce.getFiller().accept(this);
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLObjectHasValue)
+	 */
+	@Override
+	public void visit(OWLObjectHasValue ce) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLObjectMinCardinality)
+	 */
+	@Override
+	public void visit(OWLObjectMinCardinality ce) {
+		maxModalDepth++;
+		ce.getFiller().accept(this);
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLObjectExactCardinality)
+	 */
+	@Override
+	public void visit(OWLObjectExactCardinality ce) {
+		maxModalDepth++;
+		ce.getFiller().accept(this);
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLObjectMaxCardinality)
+	 */
+	@Override
+	public void visit(OWLObjectMaxCardinality ce) {
+		maxModalDepth++;
+		ce.getFiller().accept(this);
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLObjectHasSelf)
+	 */
+	@Override
+	public void visit(OWLObjectHasSelf ce) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLObjectOneOf)
+	 */
+	@Override
+	public void visit(OWLObjectOneOf ce) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLDataSomeValuesFrom)
+	 */
+	@Override
+	public void visit(OWLDataSomeValuesFrom ce) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLDataAllValuesFrom)
+	 */
+	@Override
+	public void visit(OWLDataAllValuesFrom ce) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLDataHasValue)
+	 */
+	@Override
+	public void visit(OWLDataHasValue ce) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLDataMinCardinality)
+	 */
+	@Override
+	public void visit(OWLDataMinCardinality ce) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLDataExactCardinality)
+	 */
+	@Override
+	public void visit(OWLDataExactCardinality ce) {
+	}
+
+	/* (non-Javadoc)
+	 * @see org.semanticweb.owlapi.model.OWLClassExpressionVisitor#visit(org.semanticweb.owlapi.model.OWLDataMaxCardinality)
+	 */
+	@Override
+	public void visit(OWLDataMaxCardinality ce) {
+	} 
+	
+	
+}

Added: trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/PatternBasedAxiomLearningAlgorithm.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/PatternBasedAxiomLearningAlgorithm.java	                        (rev 0)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/PatternBasedAxiomLearningAlgorithm.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -0,0 +1,273 @@
+/**
+ * 
+ */
+package org.dllearner.algorithms.pattern;
+
+import java.io.ByteArrayInputStream;
+import java.io.InputStream;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+import java.util.concurrent.TimeUnit;
+
+import org.dllearner.core.AbstractAxiomLearningAlgorithm;
+import org.dllearner.core.Score;
+import org.dllearner.core.owl.Axiom;
+import org.dllearner.core.owl.NamedClass;
+import org.dllearner.kb.SparqlEndpointKS;
+import org.dllearner.kb.sparql.SparqlEndpoint;
+import org.dllearner.utilities.owl.DLLearnerAxiomConvertVisitor;
+import org.dllearner.utilities.owl.OWLAPIAxiomConvertVisitor;
+import org.dllearner.utilities.owl.OWLClassExpressionToSPARQLConverter;
+import org.semanticweb.owlapi.model.AxiomType;
+import org.semanticweb.owlapi.model.IRI;
+import org.semanticweb.owlapi.model.OWLAnnotationProperty;
+import org.semanticweb.owlapi.model.OWLAxiom;
+import org.semanticweb.owlapi.model.OWLClass;
+import org.semanticweb.owlapi.model.OWLClassExpression;
+import org.semanticweb.owlapi.model.OWLDataFactory;
+import org.semanticweb.owlapi.model.OWLEntity;
+import org.semanticweb.owlapi.model.OWLEquivalentClassesAxiom;
+import org.semanticweb.owlapi.model.OWLSubClassOfAxiom;
+import org.semanticweb.owlapi.model.PrefixManager;
+import org.semanticweb.owlapi.util.DefaultPrefixManager;
+import org.semanticweb.owlapi.util.OWLObjectDuplicator;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import uk.ac.manchester.cs.owl.owlapi.OWLDataFactoryImpl;
+
+import com.google.common.collect.HashMultiset;
+import com.google.common.collect.Multiset;
+import com.hp.hpl.jena.query.Query;
+import com.hp.hpl.jena.query.QueryExecutionFactory;
+import com.hp.hpl.jena.query.QuerySolution;
+import com.hp.hpl.jena.query.ResultSet;
+import com.hp.hpl.jena.query.ResultSetFormatter;
+import com.hp.hpl.jena.rdf.model.Model;
+import com.hp.hpl.jena.rdf.model.ModelFactory;
+import com.hp.hpl.jena.rdf.model.Resource;
+import com.hp.hpl.jena.vocabulary.RDF;
+
+/**
+ * @author Lorenz Buehmann
+ *
+ */
+public class PatternBasedAxiomLearningAlgorithm extends AbstractAxiomLearningAlgorithm{
+	
+	private static final Logger logger = LoggerFactory.getLogger(PatternBasedAxiomLearningAlgorithm.class);
+	
+	
+	private Axiom pattern;
+	private NamedClass cls;
+	
+	private FragmentExtractor fragmentExtractor;
+	private OWLClassExpressionToSPARQLConverter converter = new OWLClassExpressionToSPARQLConverter();
+	private OWLDataFactory dataFactory = new OWLDataFactoryImpl();
+	
+	private OWLAnnotationProperty confidenceProperty = dataFactory.getOWLAnnotationProperty(IRI.create("http://dl-learner.org/pattern/confidence"));
+
+
+	private double threshold = 0.4;
+	
+	public PatternBasedAxiomLearningAlgorithm(SparqlEndpointKS ks, FragmentExtractionStrategy extractionStrategy) {
+		this(ks, null, extractionStrategy);
+	}
+	
+	public PatternBasedAxiomLearningAlgorithm(SparqlEndpointKS ks, String cacheDir, FragmentExtractionStrategy extractionStrategy) {
+		this.ks = ks;
+		
+		if(extractionStrategy == FragmentExtractionStrategy.TIME){
+			fragmentExtractor = new TimeBasedFragmentExtractor(ks, cacheDir, 20, TimeUnit.SECONDS);
+		} else if(extractionStrategy == FragmentExtractionStrategy.INDIVIDUALS){
+			fragmentExtractor = new IndividualBasedFragmentExtractor(ks, cacheDir, 20);
+		}
+	}
+	
+	/**
+	 * @param pattern the pattern to set
+	 */
+	public void setPattern(Axiom pattern) {
+		this.pattern = pattern;
+	}
+	
+	/**
+	 * @param cls the cls to set
+	 */
+	public void setClass(NamedClass cls) {
+		this.cls = cls;
+	}
+	
+	@Override
+	public void start() {
+		logger.info("Start learning...");
+		
+		startTime = System.currentTimeMillis();
+		
+		logger.info("Pattern: " + pattern);
+		
+		//get the maximum modal depth in the pattern axioms
+		int modalDepth = MaximumModalDepthDetector.getMaxModalDepth(OWLAPIAxiomConvertVisitor.convertAxiom(pattern));
+		logger.info("Modal depth: " + modalDepth);
+		
+		//extract fragment
+		Model fragment = fragmentExtractor.extractFragment(cls, modalDepth);
+		
+		//try to find instantiation of the pattern with confidence above threshold
+		Set<OWLAxiom> instantiations = applyPattern(OWLAPIAxiomConvertVisitor.convertAxiom(pattern), dataFactory.getOWLClass(IRI.create(cls.getName())), fragment);
+		System.out.println(instantiations);
+		
+		logger.info("...finished in {}ms.", (System.currentTimeMillis()-startTime));
+	}
+	
+	private Set<OWLAxiom> applyPattern(OWLAxiom pattern, OWLClass cls, Model fragment) {
+		Map<OWLAxiom, Score> axioms2Score = new HashMap<OWLAxiom, Score>();
+		
+		OWLClassExpression patternSubClass = null;
+		OWLClassExpression patternSuperClass = null;
+		
+		if(pattern.isOfType(AxiomType.EQUIVALENT_CLASSES)){
+			Set<OWLSubClassOfAxiom> subClassOfAxioms = ((OWLEquivalentClassesAxiom)pattern).asOWLSubClassOfAxioms();
+			for (OWLSubClassOfAxiom axiom : subClassOfAxioms) {
+				if(!axiom.getSubClass().isAnonymous()){
+					patternSubClass = axiom.getSubClass();
+					patternSuperClass = axiom.getSuperClass();
+					break;
+				}
+			}
+		} else if(pattern.isOfType(AxiomType.SUBCLASS_OF)){
+			patternSubClass = ((OWLSubClassOfAxiom) pattern).getSubClass();
+			patternSuperClass = ((OWLSubClassOfAxiom) pattern).getSuperClass();
+		} else {
+			logger.warn("Pattern " + pattern + " not supported yet.");
+			return Collections.emptySet();
+		}
+		
+		Set<OWLEntity> signature = patternSuperClass.getSignature();
+		signature.remove(patternSubClass.asOWLClass());
+		Query query = converter.asQuery("?x", dataFactory.getOWLObjectIntersectionOf(cls, patternSuperClass), signature);
+		logger.info("Running query\n" + query);
+		Map<OWLEntity, String> variablesMapping = converter.getVariablesMapping();
+		com.hp.hpl.jena.query.ResultSet rs = QueryExecutionFactory.create(query, fragment).execSelect();
+		QuerySolution qs;
+		Set<String> resources = new HashSet<String>();
+		Multiset<OWLAxiom> instantiations = HashMultiset.create();
+		while (rs.hasNext()) {
+			qs = rs.next();
+			resources.add(qs.getResource("x").getURI());
+			// get the IRIs for each variable
+			Map<OWLEntity, IRI> entity2IRIMap = new HashMap<OWLEntity, IRI>();
+			entity2IRIMap.put(patternSubClass.asOWLClass(), cls.getIRI());
+			boolean skip = false;
+			for (OWLEntity entity : signature) {
+				String var = variablesMapping.get(entity);
+				if(qs.get(var) == null){
+					logger.warn("Variable " + var + " is not bound.");
+					skip = true;
+					break;
+				}
+				if(qs.get(var).isLiteral()){
+					skip = true;
+					break;
+				}
+				Resource resource = qs.getResource(var);
+				if(entity.isOWLObjectProperty() && resource.hasURI(RDF.type.getURI())){
+					skip = true;
+					break;
+				}
+				entity2IRIMap.put(entity, IRI.create(resource.getURI()));
+			}
+			if(!skip){
+				// instantiate the pattern
+				OWLObjectDuplicator duplicator = new OWLObjectDuplicator(entity2IRIMap, dataFactory);
+				OWLAxiom patternInstantiation = duplicator.duplicateObject(pattern);
+				instantiations.add(patternInstantiation);
+			}
+		}
+		// compute the score
+		int total = resources.size();
+		for (OWLAxiom axiom : instantiations.elementSet()) {
+			int frequency = instantiations.count(axiom);
+//			System.out.println(axiom + ":" + frequency);
+			Score score = computeScore(total, Math.min(total, frequency));
+			axioms2Score.put(axiom, score);
+		}
+
+		return asAnnotatedAxioms(axioms2Score);
+	}
+	
+	private Set<OWLAxiom> asAnnotatedAxioms(Map<OWLAxiom, Score> axioms2Score){
+		Set<OWLAxiom> annotatedAxioms = new HashSet<OWLAxiom>();
+		for (Entry<OWLAxiom, Score> entry : axioms2Score.entrySet()) {
+			OWLAxiom axiom = entry.getKey();
+			Score score = entry.getValue();
+			if(score.getAccuracy() >= threshold){
+				annotatedAxioms.add(axiom.getAnnotatedAxiom(
+						Collections.singleton(dataFactory.getOWLAnnotation(confidenceProperty, dataFactory.getOWLLiteral(score.getAccuracy())))));
+				
+			}
+		}
+		return annotatedAxioms;
+	}
+	
+	public static void main(String[] args) throws Exception {
+		OWLDataFactoryImpl df = new OWLDataFactoryImpl();
+		PrefixManager pm = new DefaultPrefixManager("http://dllearner.org/pattern#");
+		
+		Model model = ModelFactory.createDefaultModel();
+		String triples = 
+				"<http://ex.org/a> a <http://ex.org/A>."+
+				"<http://ex.org/a> <http://ex.org/p> <http://ex.org/y1>."+
+				"<http://ex.org/y1> a <http://ex.org/B>."+
+				
+				"<http://ex.org/b> a <http://ex.org/A>."+
+				"<http://ex.org/b> <http://ex.org/p> <http://ex.org/y2>."+
+				"<http://ex.org/y2> a <http://ex.org/B>."+
+				
+				"<http://ex.org/c> a <http://ex.org/A>."
+				;
+		InputStream is = new ByteArrayInputStream( triples.getBytes("UTF-8"));
+		model.read(is, null, "TURTLE");
+		
+		String query = "SELECT DISTINCT   ?x WHERE  { "
+				+ "?x a <http://ex.org/A> .}";
+		
+		ResultSet rs = QueryExecutionFactory.create(query, model).execSelect();
+		System.out.println(ResultSetFormatter.asText(rs));
+		
+		query = "SELECT DISTINCT  ?p0 ?cls0 ?x WHERE  { "
+				+ "?x a <http://ex.org/A> ."
+				+ "?x ?p0 ?s0    "
+				+ "    { SELECT  ?x ?p0 ?cls0 (count(?s1) AS ?cnt1)"
+				+ "      WHERE"
+				+ "        { ?x ?p0 ?s1 ."
+				+ "          ?s1 <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> ?cls0"
+				+ "        }"
+				+ "      GROUP BY ?x ?cls0 ?p0"
+				+ "    }"
+				+ "    { SELECT  ?x ?p0 (count(?s2) AS ?cnt2)"
+				+ "      WHERE"
+				+ "        { ?x ?p0 ?s2 }"
+				+ "      GROUP BY ?x ?p0"
+				+ "    }"
+				+ "    FILTER ( ?cnt1 = ?cnt2 )  }";
+		
+		rs = QueryExecutionFactory.create(query, model).execSelect();
+		System.out.println(ResultSetFormatter.asText(rs));
+		
+		SparqlEndpoint endpoint = SparqlEndpoint.getEndpointDBpedia();
+//		endpoint = SparqlEndpoint.getEndpointDBpediaLOD2Cloud();
+//		endpoint = SparqlEndpoint.getEndpointDBpediaLiveAKSW();
+		NamedClass cls = new NamedClass("http://dbpedia.org/ontology/SoccerPlayer");
+		OWLAxiom pattern = df.getOWLSubClassOfAxiom(df.getOWLClass("A", pm),
+				df.getOWLObjectAllValuesFrom(df.getOWLObjectProperty("p", pm), df.getOWLClass("B", pm)));
+		
+		PatternBasedAxiomLearningAlgorithm la = new PatternBasedAxiomLearningAlgorithm(new SparqlEndpointKS(endpoint), "cache", FragmentExtractionStrategy.INDIVIDUALS);
+		la.setClass(cls);
+		la.setPattern(DLLearnerAxiomConvertVisitor.getDLLearnerAxiom(pattern));
+		la.start();
+	}
+}

Added: trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/TimeBasedFragmentExtractor.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/TimeBasedFragmentExtractor.java	                        (rev 0)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/pattern/TimeBasedFragmentExtractor.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -0,0 +1,119 @@
+/**
+ * 
+ */
+package org.dllearner.algorithms.pattern;
+
+import java.sql.SQLException;
+import java.util.concurrent.TimeUnit;
+
+import org.aksw.jena_sparql_api.cache.core.QueryExecutionFactoryCacheEx;
+import org.aksw.jena_sparql_api.cache.extra.CacheCoreEx;
+import org.aksw.jena_sparql_api.cache.extra.CacheCoreH2;
+import org.aksw.jena_sparql_api.cache.extra.CacheEx;
+import org.aksw.jena_sparql_api.cache.extra.CacheExImpl;
+import org.aksw.jena_sparql_api.core.QueryExecutionFactory;
+import org.aksw.jena_sparql_api.pagination.core.PaginationUtils;
+import org.dllearner.core.owl.NamedClass;
+import org.dllearner.kb.SparqlEndpointKS;
+import org.dllearner.kb.sparql.QueryExecutionFactoryHttp;
+import org.dllearner.kb.sparql.SparqlEndpoint;
+
+import com.hp.hpl.jena.query.ParameterizedSparqlString;
+import com.hp.hpl.jena.query.Query;
+import com.hp.hpl.jena.rdf.model.Model;
+import com.hp.hpl.jena.rdf.model.ModelFactory;
+
+/**
+ * @author Lorenz Buehmann
+ *
+ */
+public class TimeBasedFragmentExtractor implements FragmentExtractor{
+	
+	public static final FragmentExtractionStrategy extractionStrategy = FragmentExtractionStrategy.TIME;
+	private SparqlEndpointKS ks;
+	private QueryExecutionFactory qef;
+	
+	private long maxExecutionTimeInMilliseconds;
+	private long startTime;
+	
+	public TimeBasedFragmentExtractor(SparqlEndpointKS ks, String cacheDir, int maxExecutionTimeInMilliseconds, TimeUnit timeUnit) {
+		this.ks = ks;
+		this.maxExecutionTimeInMilliseconds = timeUnit.toMillis(maxExecutionTimeInMilliseconds);
+		
+		SparqlEndpoint endpoint = ks.getEndpoint();
+		
+		qef = new QueryExecutionFactoryHttp(endpoint.getURL().toString(), endpoint.getDefaultGraphURIs());
+		if(cacheDir != null){
+			try {
+				long timeToLive = TimeUnit.DAYS.toMillis(30);
+				CacheCoreEx cacheBackend = CacheCoreH2.create(cacheDir, timeToLive, true);
+				CacheEx cacheFrontend = new CacheExImpl(cacheBackend);
+				qef = new QueryExecutionFactoryCacheEx(qef, cacheFrontend);
+			} catch (ClassNotFoundException e) {
+				e.printStackTrace();
+			} catch (SQLException e) {
+				e.printStackTrace();
+			}
+		}
+	}
+	
+	public TimeBasedFragmentExtractor(SparqlEndpointKS ks, int maxExecutionTimeInMilliseconds, TimeUnit timeUnit) {
+		this(ks, null, maxExecutionTimeInMilliseconds, timeUnit);
+	}
+
+	/* (non-Javadoc)
+	 * @see org.dllearner.algorithms.pattern.FragmentExtractor#extractFragment(org.dllearner.core.owl.NamedClass)
+	 */
+	@Override
+	public Model extractFragment(NamedClass cls, int maxFragmentDepth) {
+		startTime = System.currentTimeMillis();
+		Model fragment = ModelFactory.createDefaultModel();
+		
+		Query query = buildConstructQuery(cls, maxFragmentDepth);
+		
+		long pageSize = PaginationUtils.adjustPageSize(qef, 10000);
+		query.setLimit(pageSize);
+		int offset = 0;
+		while(getRemainingRuntime() > 0){
+			query.setOffset(offset);System.out.println(query);
+			Model model = qef.createQueryExecution(query).execConstruct();
+			fragment.add(model);
+			offset += pageSize;
+		}
+		return fragment;
+	}
+	
+	private Query buildConstructQuery(NamedClass cls, int depth){
+		StringBuilder sb = new StringBuilder();
+		int maxVarCnt = 0;
+		sb.append("CONSTRUCT {\n");
+		sb.append("?s").append("?p0 ").append("?o0").append(".\n");
+		for(int i = 1; i < depth-1; i++){
+			sb.append("?o").append(i-1).append(" ").append("?p").append(i).append(" ").append("?o").append(i).append(".\n");
+			maxVarCnt++;
+		}
+		sb.append("?o").append(maxVarCnt).append(" a ?type.\n");
+		sb.append("}\n");
+		sb.append("WHERE {\n");
+		sb.append("?s a ?cls.");
+		sb.append("?s").append("?p0 ").append("?o0").append(".\n");
+		for(int i = 1; i < depth-1; i++){
+			sb.append("OPTIONAL{\n");
+			sb.append("?o").append(i-1).append(" ").append("?p").append(i).append(" ").append("?o").append(i).append(".\n");
+		}
+		sb.append("OPTIONAL{?o").append(maxVarCnt).append(" a ?type}.\n");
+		for(int i = 1; i < depth-1; i++){
+			sb.append("}");
+		}
+		
+		sb.append("}\n");
+		ParameterizedSparqlString template = new ParameterizedSparqlString(sb.toString());
+		template.setIri("cls", cls.getName());
+		return template.asQuery();
+	}
+	
+	private long getRemainingRuntime(){
+		return maxExecutionTimeInMilliseconds - (System.currentTimeMillis() - startTime);
+	}
+
+}

Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java	2013-09-10 15:52:48 UTC (rev 4107)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/QueryTree.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -59,11 +59,11 @@
     	
     boolean isLiteralNode();
     
-    void setLiteralNode(boolean isLiteralNode);
+    void setIsLiteralNode(boolean isLiteralNode);
     
     boolean isResourceNode();
     
-    void setResourceNode(boolean isResourceNode);
+    void setIsResourceNode(boolean isResourceNode);
     
     boolean isVarNode();
     

Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java	2013-09-10 15:52:48 UTC (rev 4107)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/datastructures/impl/QueryTreeImpl.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -70,6 +70,10 @@
  */
 public class QueryTreeImpl<N> implements QueryTree<N>{
 	
+	enum NodeType{
+		RESOURCE, LITERAL, BLANK, VARIABLE;
+	}
+	
 	private N userObject;
 
     private QueryTreeImpl<N> parent;
@@ -119,8 +123,8 @@
     	for(QueryTree<N> child : tree.getChildren()){
     		subTree = new QueryTreeImpl<N>(child);
     		subTree.setId(child.getId());
-    		subTree.setLiteralNode(child.isLiteralNode());
-    		subTree.setResourceNode(child.isResourceNode());
+    		subTree.setIsLiteralNode(child.isLiteralNode());
+    		subTree.setIsResourceNode(child.isResourceNode());
     		addChild(subTree, tree.getEdge(child));
     	}
     }
@@ -175,11 +179,11 @@
     }
     
     @Override
-    public void setLiteralNode(boolean isLiteralNode) {
+    public void setIsLiteralNode(boolean isLiteralNode) {
     	this.isLiteralNode = isLiteralNode;
     }
     
-    public void setBlankNode(boolean isBlankNode) {
+    public void setIsBlankNode(boolean isBlankNode) {
 		this.isBlankNode = isBlankNode;
 	}
     
@@ -193,7 +197,7 @@
     }
     
     @Override
-    public void setResourceNode(boolean isResourceNode) {
+    public void setIsResourceNode(boolean isResourceNode) {
     	this.isResourceNode = isResourceNode;
     }
     

Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/impl/QueryTreeFactoryImpl.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/impl/QueryTreeFactoryImpl.java	2013-09-10 15:52:48 UTC (rev 4107)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/impl/QueryTreeFactoryImpl.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -243,7 +243,7 @@
 						subTree = new QueryTreeImpl<String>(sb.toString());
 //						subTree = new QueryTreeImpl<String>(lit.toString());
 						subTree.setId(nodeId++);
-						subTree.setLiteralNode(true);
+						subTree.setIsLiteralNode(true);
 						if(lit.getDatatype() == XSDDatatype.XSDinteger 
 								|| lit.getDatatype() == XSDDatatype.XSDdouble 
 								|| lit.getDatatype() == XSDDatatype.XSDdate
@@ -258,13 +258,13 @@
 					} else if(objectFilter.isRelevantResource(object.asResource().getURI())){
 						if(!tree.getUserObjectPathToRoot().contains(st.getObject().toString())){
 							subTree = new QueryTreeImpl<String>(st.getObject().toString());
-							subTree.setResourceNode(true);
+							subTree.setIsResourceNode(true);
 							tree.addChild(subTree, st.getPredicate().toString());
 							if(depth < maxDepth){
 								fillTree(subTree, resource2Statements, depth);
 							}
 							if(object.isAnon()){
-								subTree.setBlankNode(true);
+								subTree.setIsBlankNode(true);
 							}
 							
 						}
@@ -272,7 +272,7 @@
 						if(depth < maxDepth &&
 								!tree.getUserObjectPathToRoot().contains(st.getObject().toString())){
 							subTree = new QueryTreeImpl<String>(st.getObject().toString());
-							subTree.setResourceNode(true);
+							subTree.setIsResourceNode(true);
 							tree.addChild(subTree, st.getPredicate().toString());
 							fillTree(subTree, resource2Statements, depth);
 						}

Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/impl/QueryTreeFactoryImpl2.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/impl/QueryTreeFactoryImpl2.java	2013-09-10 15:52:48 UTC (rev 4107)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/impl/QueryTreeFactoryImpl2.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -243,13 +243,13 @@
 					subTree = new QueryTreeImpl<String>(sb.toString());
 //					subTree = new QueryTreeImpl<String>(lit.toString());
 					subTree.setId(nodeId++);
-					subTree.setLiteralNode(true);
+					subTree.setIsLiteralNode(true);
 					tree.addChild(subTree, st.getPredicate().toString());
 				} else if(objectFilter.isRelevantResource(object.asResource().getURI())){
 					if(tree.getUserObjectPathToRoot().size() < 3 && 
 							!tree.getUserObjectPathToRoot().contains(st.getObject().toString())){
 						subTree = new QueryTreeImpl<String>(st.getObject().toString());
-						subTree.setResourceNode(true);
+						subTree.setIsResourceNode(true);
 						tree.addChild(subTree, st.getPredicate().toString());
 						fillTree(subTree, resource2Statements);
 					}

Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/NBR.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/NBR.java	2013-09-10 15:52:48 UTC (rev 4107)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/NBR.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -558,8 +558,8 @@
 					genTree.addChange(new QueryTreeChange(node.getId(), ChangeType.REPLACE_LABEL));
 					genTree2Sum.put(genTree, sum(matrix.get(node)));
 					node.setUserObject(label);
-					node.setLiteralNode(isLiteralNode);
-					node.setResourceNode(!isLiteralNode);
+					node.setIsLiteralNode(isLiteralNode);
+					node.setIsResourceNode(!isLiteralNode);
 				}
 			}
 		}
@@ -636,8 +636,8 @@
 					genTree.addChange(new QueryTreeChange(child.getId(), ChangeType.REPLACE_LABEL));
 					gens.add(genTree);
 					child.setUserObject(label);
-					child.setLiteralNode(isLiteralNode);
-					child.setResourceNode(!isLiteralNode);
+					child.setIsLiteralNode(isLiteralNode);
+					child.setIsResourceNode(!isLiteralNode);
 					for(QueryTree<N> c : child.getChildren()){
 						N oldLabel = node2Label.get(c.getId());
 						if(oldLabel != null){
@@ -814,8 +814,8 @@
     		}
     		this.nodeId++;
     		subTree = createFilteredTree(child);
-    		subTree.setLiteralNode(child.isLiteralNode());
-    		subTree.setResourceNode(child.isResourceNode());
+    		subTree.setIsLiteralNode(child.isLiteralNode());
+    		subTree.setIsResourceNode(child.isResourceNode());
     		filteredTree.addChild((QueryTreeImpl<N>)subTree, tree.getEdge(child));
     	}
     	return filteredTree;

Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/EvaluatedQueryTree.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/EvaluatedQueryTree.java	2013-09-10 15:52:48 UTC (rev 4107)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/EvaluatedQueryTree.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -7,12 +7,14 @@
 public class EvaluatedQueryTree<N> implements Comparable<EvaluatedQueryTree<N>>{
 	
 	private QueryTree<N> tree;
-	private Collection<QueryTree<N>> uncoveredExamples;
+	private Collection<QueryTree<N>> falseNegatives;
+	private Collection<QueryTree<N>> falsePositives;
 	private double score;
 
-	public EvaluatedQueryTree(QueryTree<N> tree, Collection<QueryTree<N>> uncoveredExamples, double score) {
+	public EvaluatedQueryTree(QueryTree<N> tree, Collection<QueryTree<N>> falseNegatives, Collection<QueryTree<N>> falsePositives, double score) {
 		this.tree = tree;
-		this.uncoveredExamples = uncoveredExamples;
+		this.falseNegatives = falseNegatives;
+		this.falsePositives = falsePositives;
 		this.score = score;
 	}
 	
@@ -20,10 +22,20 @@
 		return tree;
 	}
 	
-	public Collection<QueryTree<N>> getUncoveredExamples() {
-		return uncoveredExamples;
+	/**
+	 * @return the falseNegatives
+	 */
+	public Collection<QueryTree<N>> getFalseNegatives() {
+		return falseNegatives;
 	}
 	
+	/**
+	 * @return the falsePositives
+	 */
+	public Collection<QueryTree<N>> getFalsePositives() {
+		return falsePositives;
+	}
+	
 	public double getScore() {
 		return score;
 	}
@@ -39,4 +51,12 @@
 			return 1;
 		}
 	}
+	
+	/* (non-Javadoc)
+	 * @see java.lang.Object#toString()
+	 */
+	@Override
+	public String toString() {
+		return "QueryTree(Score:" + score + ")\n" + tree.getStringRepresentation();
+	}
 }
\ No newline at end of file

Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/LGGGeneratorImpl.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/LGGGeneratorImpl.java	2013-09-10 15:52:48 UTC (rev 4107)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/LGGGeneratorImpl.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -48,6 +48,8 @@
 	
 	private Logger logger = Logger.getLogger(LGGGeneratorImpl.class);
 	private int nodeId;
+	
+	private int calls = 0;
 
 	@Override
 	public QueryTree<N> getLGG(QueryTree<N> tree1, QueryTree<N> tree2) {
@@ -58,11 +60,13 @@
 	public QueryTree<N> getLGG(QueryTree<N> tree1, QueryTree<N> tree2,
 			boolean learnFilters) {
 		nodeId = 0;
+		calls = 0;
 		Monitor mon = MonitorFactory.getTimeMonitor("LGG");
 		mon.start();
 		QueryTree<N> lgg = computeLGG(tree1, tree2, learnFilters);
 		mon.stop();
 		addNumbering(lgg);
+		System.out.println("Calls needed: " + calls);
 		return lgg;
 	}
 
@@ -97,13 +101,13 @@
 		}
 		Monitor mon = MonitorFactory.getTimeMonitor("LGG");
 		mon.start();
-		QueryTree<N> lgg = computeLGG(treeList.get(0), treeList.get(1), learnFilters);
+		QueryTree<N> lgg = getLGG(treeList.get(0), treeList.get(1), learnFilters);
 		if(logger.isDebugEnabled()){
 			logger.debug("LGG for 1 and 2:\n" + lgg.getStringRepresentation());
 		}
 		
 		for(int i = 2; i < treeList.size(); i++){
-			lgg = computeLGG(lgg, treeList.get(i), learnFilters);
+			lgg = getLGG(lgg, treeList.get(i), learnFilters);
 			if(logger.isDebugEnabled()){
 				logger.debug("LGG for 1-" + (i+1) + ":\n" + lgg.getStringRepresentation());
 			}
@@ -118,7 +122,8 @@
 		return lgg;
 	}
 	
-	private QueryTree<N> computeLGG(QueryTree<N> tree1, QueryTree<N> tree2, boolean learnFilters){System.out.println("call");
+	private QueryTree<N> computeLGG(QueryTree<N> tree1, QueryTree<N> tree2, boolean learnFilters){
+		calls++;
 		if(logger.isDebugEnabled()){
 			logger.debug("Computing LGG for");
 			logger.debug(tree1.getStringRepresentation());
@@ -126,9 +131,20 @@
 			logger.debug(tree2.getStringRepresentation());
 		}
 		
-		QueryTree<N> lgg = new QueryTreeImpl<N>(tree1.getUserObject());
+		
+		QueryTree<N> lgg;
+		//firstly, we check if both root nodes are resource nodes and have the same URI, i.e. the trees describe the same resource 
+		//if YES all child nodes should be also the same and we can just return one of the two tree as LGG
+		if(tree1.isResourceNode() && tree2.isResourceNode() && tree1.getUserObject().equals(tree2.getUserObject())){
+			if(logger.isDebugEnabled()){
+				logger.debug("Early termination. Tree 1(" + tree1 + ") and tree 2(" + tree2 + ") describe the same resource.");
+			}
+			return tree1;
+		}
+		//if NO we have to create a new tree as LGG and compute the LGG for the all child node pairs having the same edge to the parent nodes
+		lgg = new QueryTreeImpl<N>(tree1.getUserObject());
 		if(tree1.isResourceNode() && tree2.isResourceNode()){
-			lgg.setResourceNode(true);
+			lgg.setIsResourceNode(true);
 			
 		}
 		
@@ -153,8 +169,8 @@
 //		}
 		if(!lgg.sameType(tree2) || !lgg.getUserObject().equals(tree2.getUserObject())){
 			lgg.setUserObject((N)"?");
-			lgg.setLiteralNode(false);
-			lgg.setResourceNode(false);
+			lgg.setIsLiteralNode(false);
+			lgg.setIsResourceNode(false);
 		}
 		
 		if(tree1.isLiteralNode() && tree2.isLiteralNode()){
@@ -165,14 +181,14 @@
 				((QueryTreeImpl<N>)lgg).addLiterals(((QueryTreeImpl<N>)tree1).getLiterals());
 				((QueryTreeImpl<N>)lgg).addLiterals(((QueryTreeImpl<N>)tree2).getLiterals());
 			}
-			lgg.setLiteralNode(true);
+			lgg.setIsLiteralNode(true);
 		}
 		
 		Set<QueryTreeImpl<N>> addedChildren;
 		QueryTreeImpl<N> lggChild;
 		for(Object edge : new TreeSet<Object>(tree1.getEdges())){
 			if(logger.isTraceEnabled()){
-				logger.trace("Regarding egde: " + edge);
+				logger.trace("Analyzing egde: " + edge);
 			}
 			addedChildren = new HashSet<QueryTreeImpl<N>>();
 			for(QueryTree<N> child1 : tree1.getChildren(edge)){

Modified: trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGG.java
===================================================================
--- trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGG.java	2013-09-10 15:52:48 UTC (rev 4107)
+++ trunk/components-core/src/main/java/org/dllearner/algorithms/qtl/operations/lgg/NoiseSensitiveLGG.java	2013-09-14 06:45:10 UTC (rev 4108)
@@ -2,6 +2,7 @@
 
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.List;
 import java.util.PriorityQueue;
 import java.util.Queue;
@@ -15,6 +16,8 @@
 import com.jamonapi.Monitor;
 import com.jamonapi.MonitorFactory;
 
+import edu.stanford.nlp.util.Sets;
+
 public class NoiseSensitiveLGG<N> {
 	
 	
@@ -25,31 +28,50 @@
 	private Queue<EvaluatedQueryTree<N>> todoList;
 	private SortedSet<EvaluatedQueryTree<N>> solutions;
 	
+	private double currentlyBestScore = 0d;
+	
 	public NoiseSensitiveLGG() {
 	}
 
-	public List<EvaluatedQueryTree<N>> computeLGG(List<QueryTree<N>> trees){
+	public List<EvaluatedQueryTree<N>> computeLGG(List<QueryTree<N>> posExampleTrees){
+		return computeLGG(posExampleTrees, Collections.<QueryTree<N>>emptyList());
+	}
+	
+	public List<EvaluatedQueryTree<N>> computeLGG(List<QueryTree<N>> posExamples, List<QueryTree<N>> negExamples){
+		currentlyBestScore = 0d;
 		Monitor subMon = MonitorFactory.getTimeMonitor("subsumption-mon");
 		Monitor lggMon = MonitorFactory.getTimeMonitor("lgg-mon");
-		init(trees);
+		init(posExamples, negExamples);
 		EvaluatedQueryTree<N> currentElement;
 		do{
 			logger.trace("TODO list size: " + todoList.size());
 			//pick best element from todo list
 			currentElement = todoList.poll();
-			for (QueryTree<N> example : currentElement.getUncoveredExamples()) {
+			for (QueryTree<N> example : currentElement.getFalseNegatives()) {
 				QueryTree<N> tree = currentElement.getTree();
 				//compute the LGG
 				lggMon.start();
 				QueryTree<N> lgg = lggGenerator.getLGG(tree, example);
 				lggMon.stop();
-				//compute examples which are not covered by LGG
-				Collection<QueryTree<N>> uncoveredExamples = getUncoveredTrees(lgg, trees);
+				//compute positive examples which are not covered by LGG
+				Collection<QueryTree<N>> uncoveredPositiveExamples = getUncoveredTrees(lgg, posExamples);
+				//compute negative examples which are covered by LGG
+				Collection<QueryTree<N>> coveredNegativeExamples = getCoveredTrees(lgg, negExamples);
 				//compute score
-				double score = Heuristics.getConfidenceInterval95WaldAverage(trees.size(), trees.size() - uncoveredExamples.size());
-				//add to todo list, if not already contained in todo list or solution list
-				EvaluatedQueryTree<N> solution = new EvaluatedQueryTree<N>(lgg, uncoveredExamples, score);
-				todo(solution);
+				int coveredPositiveExamples = posExamples.size() - uncoveredPositiveExamples.size();
+				double recall = coveredPositiveExamples / (double)posExamples.size();
+				double precision = (coveredNegativeExamples.size() + coveredPositiveExamples == 0) 
+								? 0 
+								: coveredPositiveExamples / (double)(coveredPositiveExamples + coveredNegativeExamples.size());
+				
+				double score = Heuristics.getFScore(recall, precision);
+				if(score > currentlyBestScore){
+					//add to todo list, if not already contained in todo list or solution list
+					EvaluatedQueryTree<N> solution = new EvaluatedQueryTree<N>(lgg, uncoveredPositiveExamples, coveredNegativeExamples, score);
+					todo(solution);
+					currentlyBestScore = score;
+				}
+				
 			}
 			solutions.add(currentElement);
 //			todoList.remove(currentElement);
@@ -63,6 +85,12 @@
 		return new ArrayList<EvaluatedQueryTree<N>>(solutions);
 	}
 	
+	/**
+	 * Return all trees from the given list {@code allTrees} which are not already subsumed by {@code tree}.
+	 * @param tree
+	 * @param allTrees
+	 * @return
+	 */
 	private Collection<QueryTree<N>> getUncoveredTrees(QueryTree<N> tree, List<QueryTree<N>> allTrees){
 		Collection<QueryTree<N>> uncoveredTrees = new ArrayList<QueryTree<N>>();
 		for (QueryTree<N> queryTree : allTrees) {
@@ -74,14 +102,36 @@
 		return uncoveredTrees;
 	}
 	
-	private void init(List<QueryTree<N>> trees){
+	/**
+	 * Return all trees from the given list {@code allTrees} which are not already subsumed by {@code tree}.
+	 * @param tree
+	 * @param allTrees
+	 * @return
+	 */
+	private Collection<QueryTree<N>> getCoveredTrees(QueryTree<N> tree, List<QueryTree<N>> trees){
+		Collection<QueryTree<N>> coveredTrees = new ArrayList<QueryTree<N>>();
+		for (QueryTree<N> queryTree : trees) {
+			boolean subsumed = queryTree.isSubsumedBy(tree);
+			if(subsumed){
+				coveredTrees.add(queryTree);
+			}
+		}
+		return coveredTrees;
+	}
+	
+	/**
+	 * Initializes the todo list with all distinct trees contained in the given list {@code trees}.
+	 * Firstly, distinct trees are computed and afterwards, for each tree a score is computed.
+	 * @param trees
+	 */
+	private void init(List<QueryTree<N>> posExamples, List<QueryTree<N>> negExamples){
 		todoList = new PriorityQueue<EvaluatedQueryTree<N>>();
 		solutions = new TreeSet<EvaluatedQueryTree<N>>();
 //		EvaluatedQueryTree<N> dummy = new EvaluatedQueryTree<N>(new QueryTreeImpl<N>((N)"TOP"), trees, 0d);
 //		todoList.add(dummy);
 		//compute distinct trees
 		Collection<QueryTree<N>> distinctTrees = new ArrayList<QueryTree<N>>();
-		for (QueryTree<N> quer...
 
[truncated message content]