In cosmological simulations like the MultiDark simulation, we encounter small objects (dark matter halos) being embedded in larger ones, which in turn may reside in even bigger structures. Once these objects are found, their hierarchical structure can be represented with a substructure tree, in much the same way as the build-up process of halo formation is usually expressed with merger trees.

Substructures in AHF

The AHF's halo-finding algorithm is fully recursive, automatically identifying halos, subhalos, sub-subhalos, etc. The hostid flag therefore points to the direct host it resides in and not the treerootid (see picture below).

Substructures in BDM

The BDM, e.g. bolshoi.bdmv halo finder does not distinguish subhalo and sub-sub halos. There is only one pointer in the BDM catalogues: the column hostFlag. It is -1, if a halo is a distinct halo; otherwise it points to the halo in which the subhalo resides.

Note: Currently, halos which belong to a host halo on the opposite side of the box (periodic boundary!) are not linked to their corresponding host at the moment. We will update the corresponding hostFlags soon.

Substructures in the FOF main catalogues

The main FOF tables FOF – FOF4 were created using the FOF tables, e.g. MDR1 FOF halofinder and contain FOF groups of galaxy cluster size and smaller for 4 different linking lengths. We constructed substructure trees for them for redshift 0 only. The interested user could also reconstruct them themselves, using the FOF tables from e.g. MDR1 tables tables.

Substructure trees for superclusters

Currently we provide substructure information for superclusters (FOF groups obtained with a linking length of 0.35, corresponding to an overdensity of 94) found with the FOF algorithm. The FOF catalogues for these clusters were created for different linking lengths (i.e. density thresholds, also see MDR1 LinkLength table and FOFScl at MDR1 tables and the FOF groups were then connected with each other. Note that the nature of the FOF algorithm implies that substructures always lie completely within their host and FOF groups cannot intersect with each other (if there is a connection, they are joined and considered as one group, see FOF halofinders, e.g. mdr1.fof).

Storing substructure trees in the database

For storing the substructure information in a database table, we first built a tree of substructures like the one in the figure below. The biggest cluster (lowest density threshold, lowest sclevel and largest linking length) is given at the top, followed by successively smaller clusters or groups in the next rows (increasing sclevel, smaller linking length). The FOF substructures are also sorted by mass from left to right for each sub-tree, i.e. the main branch of a tree is always the leftmost branch.

Substructure tree

Substructure tree: the top node as the root of the tree represents the biggest object (with largest linking length). Each row contains FOF groups of smaller linking lengths, which are substructures of their host(s) (the FOF groups “above” them). Additionally FOF substructures are sorted by mass from left to right for each FOF group. The numbers indicate the ranking of FOF groups in a depth first ordering. The thick green line marks the main branch of the tree root (0). The identifiers (ids) given here for node 2 are stored for each node in the database table and explained below.

The objects of a substructure tree are numbered by walking the tree in a depth-first order, starting with 0 at the tree root (top node). This rank in the substructure tree is added to the identifier (id) of the tree root, which allows to quickly relate all FOF groups of one substructure tree with each other. Details on the identifiers used for storing the substructure tree follow below.


This is the id of the top node in the substructure tree, i.e. the supercluster with the largest linking length (sclevel=0, the host). The id is calculated based on the snapshot number and the number of the FOF cluster in the FOF catalogue (line number, starting with 0):

treeRootId = (snapnum*10^9+(rank in file)) *10^6

fofSubId, lastSubId and hostId

The fofSubIds are the unique object identifiers of the FOF groups in the corresponding database table. In order to encode the tree membership, we just add the FOF group’s rank in the substructure tree to the corresponding treeRootId:

fofSubId = treeRootId + (rank in substructure tree)

For convenience, we store in the table for each FOF group its fofSubId, its treeRootId, the id of the direct host (one level lower, hostId) and also the id of the last FOF group in its substructure tree as the lastSubId. Thus it becomes possible to quickly extract all children of a node, i.e. all substructures within a FOF group: they are all groups with ids between the node’s id and its lastSubId.
Thus, SQL queries for finding all FOF substructures of a given supercluster (e.g. no. 2 in the figure) are done like this:

select * from <tablename>
where fofsubid between <cluster_fofsubid> and <cluster_lastsubid>

where <cluster_fofsubsd> is the fofSubId of the given supercluster and <cluster_lastsubid> is its lastSubId.

Main branch

The main branch in the substructure tree is defined as the branch along the most massive substructures. The depth first search is performed such that the most massive group in the next level (deeper in the tree) is visited first. In this way, it is easily possible to extract the main branch of a substructure tree: all groups until the group with the mainLeafId (see figure above) belong to the main branch. Please note that mainLeafId points to the very last FOF group in the main branch, not only the next one.
SQL queries for the main branch have then following structure:

select * from <tablename>
where fofsubid between <cluster_fofsubid> and <cluster_mainLeafid>

<cluster_mainleafid> could also be replaced by

(select mainLeafId from <tablename> where fofSubId = <cluster_fofsubid>)

resulting in a nested SQL query.

“Loose” particles

In addition to the subgroups, a FOF group can also contain “loose” particles, which are not a member of any subgroup (of the given level). The original FOF-substructure catalogues include them as a “fake halo” in the substructure list; however, for simplicity, we did not include them in the substructure tree for the database. Instead, we store this information as an additional column nloose in the database table.