Looking for a very memory-efficient way of finding exporting all relations in a family tree

Question

Think of the question as a family tree, in the PS section I will explain what exactly it is but family tree is easier to imagine: so father, has kids, those kids may have more kids, those kids may have more kids, etc..

1- I don't have the whole information in memory to traverse them. With each method call and hitting the database I have just the father at some level and its kids. See here is the high-level of the method that I have and need to some how use some good parts of it:

private void Foo(string fatherNode)
{
  // call some DB scripts and grab data you need to work with.
  int numberOfKids = // get it from the thing you populated from the DB call.
  for(int i = 1  to numberOfKids)
  {
     Node Child = // grab child[i] from the list we populated from DB calls
     //Add it to the treeView
  }
}

Well this was working because it is a GUI application and with each you know "click" event we were really requesting just one level of info but Now I need a new functionality where I can click an Export button and it writes the WHOLE structure of this whole family tree to a XML file..( so you can expand those nodes and still see the family hierarchy)

2- There is a lot of data. One Father might have 400 children, each children might have 10 more children and each of those chilcren might have 500 more children...so I need to also be concerned about getting memory exceptions...

3- Recursion? can we really load ALL of this hierarchy to memory? I don't think so..remember the goal is to export it to a XML SO Maybe the efficient way is write a good algorithm that at each call writes one level of hierarchy to file and doesn't load the whole thing in memory...

But I am pulling my hair and banging my head on desk and can't crack the code and figure it out.. So what are your pseduo-code- suggestions... I am using C# by the way.

---

P.S: This is actually a Clinical Bioinformatics hierarchy, so you say Ok human genomes..ok now there 27000 genes under it, Ok now gets gene234 and let's say what are its children,...

Answer 1

The straightforward solution

void Export(Node currentNode)
{
  WriteContentToXmlFile(currentNode); // delete this if you have only content for leafs
  int numberOfKids = currentNode.GetNumberOfChildren();
  if(numberOfKids==0)
  {
      // add "WriteContentToXmlFile(currentNode)" here if you have only content for leafs
      return;
  }
  WriteStartingTagForASubTreeIntoXmlFile(); // for example, <subtree>
  for(int i = 1  to numberOfKids)
  {
     Node child = currentNode.GetChild(i);  // gets it from your database
     Export(child);
     // leaving the scope frees "child" from memory
  }
  WriteEndingTagForASubTreeIntoXmlFile(); //  for example, </subtree>
}

does never pull more nodes into main memory as the depth of the tree (the length of the longest path from root to a leaf). So, when you write your xml file sequentially to disk (and do not keep it in main memory), you won't run into problems, I guess.

You have to adapt this surely to the kind of XML structure you have in mind, but I hope you see that memory should not be much of a problem.

Answer 2

This is why I wish technologies like RDF/XML were popular on the .net platform..

I see two options:

1. If you need to write the tree depth first using XML:

   You have identified your problem correctly. The stack has the potential to get very large and each stack frame even larger in a deeply recursive tree. The simple and slowest solution is to issue a database call for every node in the tree. So, rather than getting all the children, simply get the node in question. In a database backed model of your tree, when you get the Children of a Father, you don't have to store the whole level of children in memory at once. Rather, you can retrieve and free each one as you "visit" it. Does that make sense? Obviously this will increase the number of database calls you need, but it is pretty memory efficient.

   EDIT: This ^ is what Doc Brown describes in his answer..

   I would start by not worrying about memory though and simply develop it as you described: a recursive export method where you obtain one level at a time and write the tree to XML depth first. Then rework it if you actually run into memory problems. Despite the size of your data, I honestly don't think you'll have a problem exporting the whole tree. If you do have out of memory issues, work at a solution. You worst case, however, will be SPACE(N).

2. Use RDF properly (my recommendation):

   Using RDF/XML, writing the data in constant space, SPACE(K), is trivial and basically solves all your problems. But, RDF/XML is a highly underused technology because it has a high learning curve. IF you're willing to switch to Java, there are numerous tools to do database backed RDF models, such as Apache's Jena, that will make this job incredibly easy. If you are stuck on C#, but want to give RDF a shot, take a look at the C# SemWeb Library.

   The idea is that you write the structure of the data along with the actual data itself to RDF/XML in a condensed n-triples format. Since the structure is also exported, the data can be serialized k nodes at a time, thus in constant space. This is the optimal solution especially if you have a graph that may not ever fit in a viable amount of memory (if the data set is really as big as you claim (; ).

Answer 3

Can't you just use a good old fashioned k-ary tree? Load the entire tree into memory at start-up. Then implement some sort of event mechanism to update it if the DB changes after startup. You should be able to find it in any standard Data Structures and Algorithms book. I would use a linked list for the underlying storage mechanism, since you don't know how many children each node will have. Recursion should not be an issue for a linked list implementation, since you will essentially just have references to the first item in each list. If you are that worried about it, you can make sure you use tail recursion, or even better, implement your own stack to call the recursive functions on. However, without recursion, tree traversal will be too complicated to be good and maintainable code.

I am not sure how .NET's System.Text.Xml stuff stores the nodes. However, if it is array based, then that will not be as efficient (or fun?) as just implementing a tree yourself.

I would do something like (sorry for the C++ syntax, I don't remember generics for C# off of the top of my head).

template <typename E> 
class TreeNode
{
public:
  E value();
  bool isLeaf();
  TreeNode* parent();
  TreeNode* lefmostChild();
  TreeNode* rightSibling();
  void insertFirst(TreeNode<E>*);
  void insertNext(TreeNode<E>*);
  void setValue(E&);
  ...

};

class FamilyMember
{
   //store all of your data for the family member in here.
};

Then load up a Tree of FamilyMembers when the application starts. Then traversal will be a breeze (if you are good with recursion), and it will not be that bad on the stack. You can actually calculate this. Anyways, the important number is big-oh(n log* n) for the traversal. Memory is almost always irrelevant in this type of thing. If memory does become an issue, consider using a sequential tree implementation instead. Anyhow, n log*n is more than acceptable, and there are plenty of tree traversals that will do it that efficiently. Furthermore, you can improve this even more if you use the weighted union rule (though I think you will be fine). Once you have it in this structure, xml conversion will be trivial.