Changeset 12979

Timestamp:

10/02/15 01:08:30 (9 years ago)

Author:

bburlacu

Message:

#1772:

• added parameters to the SchemaCreator for calculating things in parallel
• added parallel code to the SchemaEvaluator
• implemented quality calculation and saving of estimated values in the scope in the UpdateEstimatedValuesOperator
• small refactoring of QueryMatch (added some useful methods and made NodeInfo internal)
• updated query match unit test

Location:

branches/HeuristicLab.EvolutionTracking

Files:

• HeuristicLab.EvolutionTracking.Tests/QueryMatchPerformanceTest.cs (modified) (3 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaCreator.cs (modified) (7 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaEvaluator.cs (modified) (9 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/UpdateEstimatedValuesOperator.cs (modified) (3 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/QueryMatch.cs (modified) (7 diffs)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.EvolutionTracking.Tests/QueryMatchPerformanceTest.cs

@@ -1 +1 @@
 using System;
+using System.Diagnostics;
 using System.Linq;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
@@ -11 +12 @@
     private const int MaxDepth = 12;
     private const int MaxLength = 50;
-    private const int N = 100000;
-
+    private const int N = 50000;
+    private const int Repetitions = 5;
 
     [TestMethod]
@@ -28 +29 @@
       };
       var qm = new QueryMatch(comparer) { MatchParents = true };
-
+      // warmup
       int count = trees.Skip(1).Count(x => qm.Match(x, trees[0]));
 
+      var sw = new Stopwatch();
+      sw.Start();
+      for (int i = 0; i < Repetitions; ++i)
+        count = trees.Skip(1).Count(x => x.Length >= trees[0].Length && qm.Match(x, trees[0]));
+      sw.Stop();
+
       Console.WriteLine("Count: " + count);
+      Console.WriteLine("Query matches per second: " + (N - 1) / (sw.ElapsedMilliseconds / 1000.0) * Repetitions);
+      Console.WriteLine("Total time: " + sw.ElapsedMilliseconds / 1000.0 + "s");
+
+      sw.Restart();
+      for (int i = 0; i < Repetitions; ++i)
+        count = qm.GetMatchingTrees(trees.Skip(1), trees[0]).Count();
+      sw.Stop();
+
+      Console.WriteLine("Count: " + count);
+      Console.WriteLine("Optimized query matches per second: " + (N - 1) / (sw.ElapsedMilliseconds / 1000.0) * Repetitions);
+      Console.WriteLine("Total time: " + sw.ElapsedMilliseconds / 1000.0 + "s");
     }
   }

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaCreator.cs

@@ -42 +42 @@
     private const string ReplacementRatioParameterName = "ReplacementRatio";
     private const string RandomReplacementParameterName = "RandomReplacement";
+    private const string ExecuteInParallelParameterName = "ExecuteInParallel";
+    private const string MaxDegreeOfParalellismParameterName = "MaxDegreeOfParallelism";
 
     #region parameters
@@ -48 +50 @@
     }
 
+    public IFixedValueParameter<BoolValue> ExecuteInParallelParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters[ExecuteInParallelParameterName]; }
+    }
+
+    public IFixedValueParameter<IntValue> MaxDegreeOfParallelismParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[MaxDegreeOfParalellismParameterName]; }
+    }
+
     public IFixedValueParameter<PercentValue> MinimumSchemaFrequencyParameter {
       get { return (IFixedValueParameter<PercentValue>)Parameters[MinimumSchemaFrequencyParameterName]; }
@@ -62 +72 @@
 
     #region parameter properties
-    public int MinimumSchemaLength {
-      get { return MinimumSchemaLengthParameter.Value.Value; }
-    }
+    public int MinimumSchemaLength { get { return MinimumSchemaLengthParameter.Value.Value; } }
+    public int MaxDegreeOfParallelism { get { return MaxDegreeOfParallelismParameter.Value.Value; } }
+    public bool ExecuteInParallel { get { return ExecuteInParallelParameter.Value.Value; } }
     #endregion
 
@@ -72 +82 @@
     private DataTableValuesCollector valuesCollector;
     private ResultsCollector resultsCollector;
+    private UpdateEstimatedValuesOperator updateEstimatedValuesOperator;
 
     private void ParameterizeOperators() {
@@ -89 +100 @@
       resultsCollector = new ResultsCollector();
       resultsCollector.CollectedValues.Add(new LookupParameter<DataTable>("Diversification"));
+
+      updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
     }
 
     public SchemaCreator() {
       Parameters.Add(new FixedValueParameter<IntValue>(MinimumSchemaLengthParameterName, new IntValue(10)));
-      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumSchemaFrequencyParameterName, new PercentValue(0.05)));
-      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumPhenotypicSimilarityParameterName, new PercentValue(0.8)));
-      Parameters.Add(new FixedValueParameter<PercentValue>(ReplacementRatioParameterName, new PercentValue(0.2)));
+      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumSchemaFrequencyParameterName, new PercentValue(0.01)));
+      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumPhenotypicSimilarityParameterName, new PercentValue(0.9)));
+      Parameters.Add(new FixedValueParameter<PercentValue>(ReplacementRatioParameterName, new PercentValue(0.9)));
       Parameters.Add(new FixedValueParameter<BoolValue>(RandomReplacementParameterName, new BoolValue(false)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(ExecuteInParallelParameterName, new BoolValue(false)));
+      Parameters.Add(new FixedValueParameter<IntValue>(MaxDegreeOfParalellismParameterName, new IntValue(-1)));
+
+      ExecuteInParallelParameter.Hidden = true;
+      MaxDegreeOfParallelismParameter.Hidden = true;
 
       ParameterizeOperators();
@@ -116 +134 @@
         return base.Apply();
       // for now, only consider crossover offspring
+
+      var scopes = new ScopeList(this.ExecutionContext.Scope.SubScopes);
       var vertices = GenealogyGraph.GetByRank(gen).Where(x => x.InDegree == 2).Cast<IGenealogyGraphNode<ISymbolicExpressionTree>>();
       var groups = vertices.GroupBy(x => x.Parents.First()).OrderByDescending(g => g.Count()).ToList();
       var anySubtreeSymbol = new AnySubtreeSymbol();
 
-      var scopes = new ScopeList(this.ExecutionContext.Scope.SubScopes);
-
       if (schemaEvaluator == null || schemaCleanupOperator == null || changedTreesReducer == null || valuesCollector == null || resultsCollector == null)
         ParameterizeOperators();
@@ -129 +147 @@
       var collectResults = ExecutionContext.CreateChildOperation(resultsCollector);
 
-      var oc = new OperationCollection();
+      var updateEstimatedValues = new OperationCollection { Parallel = true };
+      foreach (var s in scopes) {
+        if (!s.Variables.ContainsKey("EstimatedValues"))
+          s.Variables.Add(new Core.Variable("EstimatedValues"));
+        updateEstimatedValues.Add(ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, s));
+      }
+      var oc = new OperationCollection { updateEstimatedValues };
 
       #region create schemas and add subscopes representing the individuals

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaEvaluator.cs

@@ -22 +22 @@
 using System;
 using System.Linq;
+using System.Threading.Tasks;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -50 +51 @@
     private const string RandomReplacementParameterName = "RandomReplacement";
     private const string ChangedTreesParameterName = "ChangedTrees";
+    private const string ExecuteInParallelParameterName = "ExecuteInParallel";
+    private const string MaxDegreeOfParalellismParameterName = "MaxDegreeOfParallelism";
     #endregion
 
     #region parameters
+    public ILookupParameter<BoolValue> ExecuteInParallelParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters[ExecuteInParallelParameterName]; }
+    }
+    public ILookupParameter<IntValue> MaxDegreeOfParallelismParameter {
+      get { return (ILookupParameter<IntValue>)Parameters[MaxDegreeOfParalellismParameterName]; }
+    }
     public ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>> EvaluatorParameter {
       get { return (ILookupParameter<ISymbolicDataAnalysisSingleObjectiveEvaluator<IRegressionProblemData>>)Parameters[EvaluatorParameterName]; }
@@ -98 +107 @@
 
     #region parameter properties
-    public PercentValue MinimumSchemaFrequency {
-      get { return MinimumSchemaFrequencyParameter.ActualValue; }
-    }
-
-    public PercentValue ReplacementRatio {
-      get { return ReplacementRatioParameter.ActualValue; }
-    }
-
-    public PercentValue MinimumPhenotypicSimilarity {
-      get { return MinimumPhenotypicSimilarityParameter.ActualValue; }
-    }
-
-    public BoolValue RandomReplacement {
-      get { return RandomReplacementParameter.ActualValue; }
-    }
+    public PercentValue MinimumSchemaFrequency { get { return MinimumSchemaFrequencyParameter.ActualValue; } }
+    public PercentValue ReplacementRatio { get { return ReplacementRatioParameter.ActualValue; } }
+    public PercentValue MinimumPhenotypicSimilarity { get { return MinimumPhenotypicSimilarityParameter.ActualValue; } }
+    public BoolValue RandomReplacement { get { return RandomReplacementParameter.ActualValue; } }
     #endregion
 
@@ -124 +122 @@
     };
 
-
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      if (!Parameters.ContainsKey(ChangedTreesParameterName))
-        Parameters.Add(new LookupParameter<IntValue>(ChangedTreesParameterName));
-    }
+    [Storable]
+    private readonly UpdateEstimatedValuesOperator updateEstimatedValuesOperator;
 
     public SchemaEvaluator() {
       qm = new QueryMatch(comp) { MatchParents = true };
+      this.updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
 
       Parameters.Add(new LookupParameter<ISymbolicExpressionTree>(SchemaParameterName, "The current schema to be evaluated"));
@@ -148 +143 @@
       Parameters.Add(new LookupParameter<BoolValue>(RandomReplacementParameterName));
       Parameters.Add(new LookupParameter<IntValue>(ChangedTreesParameterName));
-    }
-
+      Parameters.Add(new LookupParameter<BoolValue>(ExecuteInParallelParameterName));
+      Parameters.Add(new LookupParameter<IntValue>(MaxDegreeOfParalellismParameterName));
+    }
 
     [StorableConstructor]
@@ -155 +151 @@
 
     protected SchemaEvaluator(SchemaEvaluator original, Cloner cloner) : base(original, cloner) {
-      this.comp = (ISymbolicExpressionTreeNodeEqualityComparer)original.comp.Clone();
-      this.qm = new QueryMatch(comp) { MatchParents = original.qm.MatchParents };
+      this.comp = original.comp == null ? new SymbolicExpressionTreeNodeEqualityComparer {
+        MatchConstantValues = false,
+        MatchVariableWeights = false,
+        MatchVariableNames = true
+      } : (ISymbolicExpressionTreeNodeEqualityComparer)original.comp.Clone();
+      this.qm = new QueryMatch(comp) { MatchParents = original.qm?.MatchParents ?? true };
+      this.updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
     }
 
@@ -163 +164 @@
     }
 
-    private static double CalculatePhenotypicSimilarity(ScopeList individuals, SymbolicExpressionTreePhenotypicSimilarityCalculator calculator) {
-      double similarity = 0;
-      int count = individuals.Count;
-      for (int i = 0; i < count - 1; ++i) {
-        for (int j = i + 1; j < count; ++j) {
-          similarity += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
-        }
-      }
-      return similarity / (count * (count - 1) / 2.0);
-    }
-
     public override IOperation Apply() {
       var individuals = ExecutionContext.Scope.SubScopes; // the scopes represent the individuals
@@ -179 +169 @@
       var random = RandomParameter.ActualValue;
       var mutator = MutatorParameter.ActualValue;
-      var evaluator = EvaluatorParameter.ActualValue;
-      var updateEstimatedValuesOperator = new UpdateEstimatedValuesOperator();
 
       var s = SchemaParameter.ActualValue;
-      var matchingIndividuals = new ScopeList();
-      foreach (var ind in individuals) {
-        var t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value;
-        if (t.Length >= s.Length && qm.Match(t, s))
-          matchingIndividuals.Add(ind);
-      }
-
-      if (matchingIndividuals.Count < (int)Math.Max(2, Math.Round(MinimumSchemaFrequency.Value * individuals.Count))) {
+      var sRoot = s.Root.GetSubtree(0).GetSubtree(0);
+      int countThreshold = (int)Math.Max(2, Math.Round(MinimumSchemaFrequency.Value * individuals.Count));
+
+      // first apply the length and root equality checks in order to filter the individuals
+      var filtered = (from ind in individuals
+                      let t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value
+                      where t.Length >= s.Length && qm.Comparer.Equals(t.Root.GetSubtree(0).GetSubtree(0), sRoot)
+                      select ind).ToList();
+
+      // if we don't have enough filtered individuals, then we are done
+      if (filtered.Count < countThreshold) {
         ChangedTreesParameter.ActualValue = new IntValue(0);
         return base.Apply();
       }
 
-      var similarity = CalculatePhenotypicSimilarity(matchingIndividuals, calculator);
+      // check if the filtered individuals match the schema
+      var sNodes = QueryMatch.InitializePostOrder(sRoot);
+      var matchingIndividuals = new ScopeList();
+      bool executeInParallel = ExecuteInParallelParameter.ActualValue.Value;
+      int maxDegreeOfParallelism = MaxDegreeOfParallelismParameter.ActualValue.Value;
+
+      if (executeInParallel) {
+        var matching = new bool[filtered.Count];
+
+        Parallel.For(0, filtered.Count, new ParallelOptions { MaxDegreeOfParallelism = maxDegreeOfParallelism },
+          i => {
+            var t = (ISymbolicExpressionTree)filtered[i].Variables["SymbolicExpressionTree"].Value;
+            var tNodes = QueryMatch.InitializePostOrder(t.Root.GetSubtree(0).GetSubtree(0));
+            if (qm.Match(tNodes, sNodes)) {
+              matching[i] = true;
+            }
+          });
+
+        for (int i = 0; i < matching.Length; ++i) {
+          if (matching[i])
+            matchingIndividuals.Add(filtered[i]);
+        }
+      } else {
+        for (int i = 0; i < filtered.Count; ++i) {
+
+          // break early if it becomes impossible to reach the minimum threshold
+          if (matchingIndividuals.Count + filtered.Count - i < countThreshold)
+            break;
+
+          var ind = filtered[i];
+          var t = (ISymbolicExpressionTree)ind.Variables["SymbolicExpressionTree"].Value;
+          var tNodes = QueryMatch.InitializePostOrder(t.Root.GetSubtree(0).GetSubtree(0));
+          if (qm.Match(tNodes, sNodes))
+            matchingIndividuals.Add(ind);
+        }
+      }
+
+      if (matchingIndividuals.Count < countThreshold) {
+        ChangedTreesParameter.ActualValue = new IntValue(0);
+        return base.Apply();
+      }
+
+      var similarity = CalculatePhenotypicSimilarity(matchingIndividuals, calculator, executeInParallel, maxDegreeOfParallelism);
       if (similarity < MinimumPhenotypicSimilarity.Value) {
         ChangedTreesParameter.ActualValue = new IntValue(0);
@@ -201 +234 @@
       }
 
-      var oc = new OperationCollection();
       int n = (int)Math.Floor(matchingIndividuals.Count * ReplacementRatio.Value);
       var individualsToReplace = RandomReplacement.Value ? matchingIndividuals.SampleRandomWithoutRepetition(random, n).ToList()
                                                          : matchingIndividuals.OrderBy(x => (DoubleValue)x.Variables["Quality"].Value).Take(n).ToList();
+      var mutationOc = new OperationCollection { Parallel = false }; // cannot be parallel due to the before/after operators which insert vertices in the genealogy graph
+      var updateEstimatedValues = new OperationCollection { Parallel = true }; // evaluation should be done in parallel when possible
       foreach (var ind in individualsToReplace) {
         var mutatorOp = ExecutionContext.CreateChildOperation(mutator, ind);
-        var evaluatorOp = ExecutionContext.CreateChildOperation(evaluator, ind);
-        var updateEstimatedValuesOp = ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, ind);
-        oc.Add(mutatorOp);
-        oc.Add(evaluatorOp);
-        oc.Add(updateEstimatedValuesOp);
+        var updateOp = ExecutionContext.CreateChildOperation(updateEstimatedValuesOperator, ind);
+        mutationOc.Add(mutatorOp);
+        updateEstimatedValues.Add(updateOp);
       }
       ChangedTreesParameter.ActualValue = new IntValue(individualsToReplace.Count);
-      return new OperationCollection(oc, base.Apply());
+      return new OperationCollection(mutationOc, updateEstimatedValues, base.Apply());
+    }
+
+    private static double CalculatePhenotypicSimilarity(ScopeList individuals, SymbolicExpressionTreePhenotypicSimilarityCalculator calculator, bool parallel = false, int nThreads = -1) {
+      double similarity = 0;
+      int count = individuals.Count;
+      if (parallel) {
+        var parallelOptions = new ParallelOptions { MaxDegreeOfParallelism = nThreads };
+        var simArray = new double[count - 1];
+        Parallel.For(0, count - 1, parallelOptions, i => {
+          double innerSim = 0;
+          for (int j = i + 1; j < count; ++j) {
+            innerSim += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
+          }
+          simArray[i] = innerSim;
+        });
+        similarity = simArray.Sum();
+      } else {
+        for (int i = 0; i < count - 1; ++i) {
+          for (int j = i + 1; j < count; ++j) {
+            similarity += calculator.CalculateSolutionSimilarity(individuals[i], individuals[j]);
+          }
+        }
+      }
+      return similarity / (count * (count - 1) / 2.0);
     }
   }

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/UpdateEstimatedValuesOperator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Linq;
 using HeuristicLab.Common;
@@ -51 +52 @@
     }
 
+
     public UpdateEstimatedValuesOperator() {
       Parameters.Add(new LookupParameter<IRegressionProblemData>(ProblemDataParameterName));
@@ -74 +76 @@
       var interpreter = InterpreterParameter.ActualValue;
 
-      var estimatedValues = interpreter.GetSymbolicExpressionTreeValues(tree, problemData.Dataset, problemData.TrainingIndices)
-                                       .LimitToRange(estimationLimits.Lower, estimationLimits.Upper).ToArray();
+      var estimatedValues = interpreter.GetSymbolicExpressionTreeValues(tree, problemData.Dataset, problemData.TrainingIndices).ToArray();
+      var targetValues = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices).ToArray();
+
+      if (estimatedValues.Length != targetValues.Length)
+        throw new ArgumentException("Number of elements in target and estimated values enumeration do not match.");
+
+      var linearScalingCalculator = new OnlineLinearScalingParameterCalculator();
+
+      for (int i = 0; i < estimatedValues.Length; ++i) {
+        var estimated = estimatedValues[i];
+        var target = targetValues[i];
+        if (!double.IsNaN(estimated) && !double.IsInfinity(estimated))
+          linearScalingCalculator.Add(estimated, target);
+      }
+      double alpha = linearScalingCalculator.Alpha;
+      double beta = linearScalingCalculator.Beta;
+      if (linearScalingCalculator.ErrorState != OnlineCalculatorError.None) {
+        alpha = 0.0;
+        beta = 1.0;
+      }
+
+      var scaled = estimatedValues.Select(x => x * beta + alpha).LimitToRange(estimationLimits.Lower, estimationLimits.Upper).ToArray();
+      OnlineCalculatorError error;
+      var r = OnlinePearsonsRCalculator.Calculate(targetValues, scaled, out error);
+      if (error != OnlineCalculatorError.None) r = 0;
+
+      var r2 = r * r;
+      if (r2 > 1.0) r2 = 1.0;
 
       var variables = ExecutionContext.Scope.Variables;
-      if (variables.ContainsKey("EstimatedValues"))
-        variables["EstimatedValues"].Value = new DoubleArray(estimatedValues);
-      else
-        variables.Add(new Core.Variable("EstimatedValues", new DoubleArray(estimatedValues)));
+      ((DoubleValue)variables["Quality"].Value).Value = r2;
+
+      if (variables.ContainsKey("EstimatedValues")) {
+        variables["EstimatedValues"].Value = new DoubleArray(scaled);
+      } else {
+        variables.Add(new Core.Variable("EstimatedValues", new DoubleArray(scaled)));
+      }
       return base.Apply();
     }

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/QueryMatch.cs

@@ -28 +28 @@
   // by M. Götz, C. Koch and W. Martens in http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.182.5440
   public class QueryMatch {
-    private List<NodeInfo> dNodes;
-    private List<NodeInfo> qNodes;
-    private readonly ISymbolicExpressionTreeNodeEqualityComparer comparer;
+    public ISymbolicExpressionTreeNodeEqualityComparer Comparer { get; }
 
     private QueryMatch() { }
@@ -41 +39 @@
 
     public QueryMatch(ISymbolicExpressionTreeNodeEqualityComparer comparer) {
-      this.comparer = comparer;
+      this.Comparer = comparer;
+    }
+
+    internal bool Match(List<NodeInfo> data, List<NodeInfo> query) {
+      var dRoot = data.Last();
+      var qRoot = query.Last();
+
+      var result = Tmatch(dRoot, query.First(), qRoot);
+      return result == qRoot;
     }
 
@@ -49 +55 @@
 
     public bool Match(ISymbolicExpressionTreeNode data, ISymbolicExpressionTreeNode query) {
-      if (!comparer.Equals(data, query))
+      if (!Comparer.Equals(data, query))
         return false;
 
-      dNodes = InitializePostOrder(data);
-      qNodes = InitializePostOrder(query);
+      var dNodes = InitializePostOrder(data);
+      var qNodes = InitializePostOrder(query);
 
       var dRoot = dNodes.Last();
       var qRoot = qNodes.Last();
-      var result = Tmatch(dRoot, qNodes.First(), qNodes.Last());
+      var result = Tmatch(dRoot, qNodes.First(), qRoot);
       return result == qRoot;
+    }
+
+    public IEnumerable<ISymbolicExpressionTree> GetMatchingTrees(IEnumerable<ISymbolicExpressionTree> data, ISymbolicExpressionTree query) {
+      var qRoot = query.Root.GetSubtree(0).GetSubtree(0);
+      var filtered = data.Where(x => x.Length >= query.Length && Comparer.Equals(x.Root.GetSubtree(0).GetSubtree(0), qRoot));
+      var qNodes = InitializePostOrder(query.Root.GetSubtree(0).GetSubtree(0));
+      return from d in filtered let dNodes = InitializePostOrder(d.Root.GetSubtree(0).GetSubtree(0)) where Match(dNodes, qNodes) select d;
     }
 
@@ -66 +79 @@
         return false;
 
-      bool equals = comparer.Equals(a.Node, b.Node);
+      bool equals = Comparer.Equals(a.Node, b.Node);
 
       if (equals && MatchParents) {
@@ -74 +87 @@
           return true;
         if (pa != null && pb != null)
-          return pa.Level == pb.Level && comparer.Equals(pa.Node, pb.Node);
+          return pa.Level == pb.Level && Comparer.Equals(pa.Node, pb.Node);
         return false;
       }
@@ -145 +158 @@
     }
 
-    private List<NodeInfo> InitializePostOrder(ISymbolicExpressionTreeNode node) {
+    internal static List<NodeInfo> InitializePostOrder(ISymbolicExpressionTreeNode node) {
       var list = node.IterateNodesPostfix().ToList();
       var nodes = list.Select((x, i) => new NodeInfo { Node = x, Index = i, Level = node.GetBranchLevel(x) }).ToList();
@@ -171 +184 @@
       return nodes;
     }
-
-    private class NodeInfo {
-      public ISymbolicExpressionTreeNode Node { get; set; }
-      public int Index { get; set; }
-      public int Level { get; set; }
-      public NodeInfo Parent { get; set; }
-      public NodeInfo Previous { get; set; }
-      public NodeInfo PreviousSibling { get; set; }
-      public NodeInfo Next { get; set; }
-      public NodeInfo NextSibling { get; set; }
-      public NodeInfo LastSibling { get; set; }
-      public NodeInfo LastChild { get; set; }
-
-      public bool IsLeaf {
-        get { return Node.SubtreeCount == 0; }
-      }
-
-      public bool IsFirstSibling {
-        get { return Node.Parent != null && Node == Node.Parent.Subtrees.First(); }
-      }
-
-      public bool IsLastSibling {
-        get { return Node.Parent != null && Node == Node.Parent.Subtrees.Last(); }
-      }
-
-      public IEnumerable<NodeInfo> Ancestors {
-        get {
-          var p = Parent;
-          while (p != null) {
-            yield return p;
-            p = p.Parent;
-          }
+  }
+
+  internal class NodeInfo {
+    public ISymbolicExpressionTreeNode Node { get; set; }
+    public int Index { get; set; }
+    public int Level { get; set; }
+    public NodeInfo Parent { get; set; }
+    public NodeInfo Previous { get; set; }
+    public NodeInfo PreviousSibling { get; set; }
+    public NodeInfo Next { get; set; }
+    public NodeInfo NextSibling { get; set; }
+    public NodeInfo LastSibling { get; set; }
+    public NodeInfo LastChild { get; set; }
+
+    public bool IsLeaf {
+      get { return Node.SubtreeCount == 0; }
+    }
+
+    public bool IsFirstSibling {
+      get { return Node.Parent != null && Node == Node.Parent.Subtrees.First(); }
+    }
+
+    public bool IsLastSibling {
+      get { return Node.Parent != null && Node == Node.Parent.Subtrees.Last(); }
+    }
+
+    public IEnumerable<NodeInfo> Ancestors {
+      get {
+        var p = Parent;
+        while (p != null) {
+          yield return p;
+          p = p.Parent;
         }
       }