2012-01-14 Fractal Genealogy

mathematical pedigree

H-tree

An H-tree is a space-efficient tree-layout technique for balanced binary trees.
The first thing you probably gathered from that sentence is that H-tree is some theoretical mathematical or computer science concept. Don't worry if you don't like mathematics though; H-trees belong to the rather enjoyable branch of mathematics known as fractals.

fractal

A fractal is self-similar geometric shape; each part of the shape is similar to the whole; it is exactly or approximately the same shape as the whole. The most famous fractal is the Mandelbrot set.
There are several fractal programs that let you explore fractals, and when you zoom in on the fractal border of the Mandelbrot set, you can't help but see what self-similar means.

algorithm

Each fractal is defined by an algorithm, a recipe for constructing it. The recipe for the H-tree is very simple, and because it really is a tree (in the mathematical, graph theory sense), it can easily be explained without any mathematical symbols. In fact, the H-tree is recursive graphic, which is best explained using a few images.
The recipe is just one step, which is repeated over and over again. The number of steps executed so far is the order of the H-tree; if the step has been executed three times, the resulting drawing is a third-order H-tree.

The H-tree is called an H-tree because the first-order H-tree looks like the letter H.

how to draw

A H-tree is typically drawn within a square, but it trivial to stretch it to rectangle. The zeroth-order H-tree is an empty square. Imagine a dot at the centre of the square. A simple straight cross through that dot would divide the square into four smaller equally-sized squares, each with their own centre.

The first step is to draw a single line, as large as the side of these smaller squares. That first line is centred within the square; from the centre of the square, it extends equally either way. The iteration step is to draw a line across the endpoints of the existing figure, always half as large as the lines in the previous iteration, always perpendicular to those lines, and always extending equally in either direction. That's it. That's all there is to it.
The fractal part is that you recursively repeat this step for each of the four smaller squares.
After just two step, the figure looks like the letter H, and that is why it is called an H-tree.

properties

The H-tree has interesting mathematical properties, and practical applications in computer science. H-tree are used in VLSI layout, and for interconnecting processors in large parallel supercomputers.
One reason for that is that H-tree is a binary tree; every time its splits, its splits in two, and that is just ideal for binary computers. There is another reason; the H-tree layout is a considerably more space efficient layout for balanced binary trees than a straightforward binary tree layout.

The drawing shows a 31-node balanced binary tree in both a traditional and H-tree layout. The H-tree layout clearly uses less space, and the difference becomes more pronounced as the depth of the tree increases.

H-tree ancestry

The H-tree is that it is a space-efficient tree-layout technique for balanced binary trees. A binary tree is a tree in which each node has up to two subtrees. It just so happens that ancestral trees are binary trees; every individual has two parents, and you have information on zero, one or two of them.
A balanced tree is tree in which the height of subtrees for any particular node never differ more than one. There are plenty of exceptions, but ancestral trees tend to be fairly balanced. Moreover, most ancestral charts limit the display to a relatively small, fixed number of generations anyway. Thus, H-trees are a space-efficient tree-layout technique for ancestral trees.

H-trees have been around for decades, they are suitable layout for an ancestry, yet not one genealogy application or chart printing service is offering ancestral charts in an H-tree layout. The H-tree layout is quite different from traditional genealogical layouts, not everyone will like it. Its strength is that it is space-efficient; that makes it an attractive display option for the increasing number of mobile genealogy applications that have display ancestries on relatively small screens.

first implementation

In 2010, Claurissa Tuttle turned the idea of using H-trees for pedigrees into a pedigree visualisation application called PedVis. That formed the basis for PedVis: A Structured, Space-Efficient Technique for Pedigree Visualization, her thesis for a Master of Science in Graphics and Visualisation.