next up previous
Next: Noise Suppression in IsoDen Up: The IsoDen Method Previous: The IsoDen Method

Basic IsoDen Method

The main aim of the IsoDen method is to improve on FOF by identifying halos over a wide range of densities, thereby exploiting the full dynamic range available in the data. The motivation is similar to that of the DENMAX algorithm [3, 6], but the procedure is substantially different. Another related method is presented in [15], but it is restricted to spherical isodensity surfaces. In some respects IsoDen corresponds to applying the FOF method at a range of densities or linking lengths, a course suggested by [5], but in an integrated and consistent way.

The idea of IsoDen is to actually calculate a spatial density field defined by the particles, and then identify halo centers as local peaks in this field. Isodensity surfaces are grown around each center, to find those particles belonging to each peak. When the isodensity surfaces of different centers touch, a new composite halo and isodensity surface is created that encompasses the two constituent peaks. In order for the method to work, the density field derived from the particle distribution must be reasonably smooth, so that the interpretation of the method in terms of isodensity surfaces is valid.

The density at each particle, tex2html_wrap_inline2070, (i ranging from 1 to N), is calculated as the sum of the masses, tex2html_wrap_inline2078, of the nearest tex2html_wrap_inline2080 particles, divided by the volume of the sphere enclosing those particles. This is simply k-nearest neighbor density estimation with tex2html_wrap_inline2082 [11].
where tex2html_wrap_inline2086 is the distance from particle i to its tex2html_wrap_inline2090 nearest neighbor and the sum is over the tex2html_wrap_inline2080 nearest neighbors of particle i. The variable smoothing scale implicit in nearest neighbor estimation is important because of the large range in densities present in the simulations. By using the nearest neighbor method with, e.g., tex2html_wrap_inline2096, the local resolution in the density is tailored to the actual resolution available.

In principle the IsoDen method could use alternative density measures which satisfy the requirement of spatial continuity. One possibility is the phase space density: the mass per spatial volume element per velocity volume element. This may be advantageous for cosmology simulations, because low density halos generally have small internal velocities, (e.g., see Figures 1 to 4) and hence have similar phase space densities as halos with higher spatial density. Other density estimation techniques are also viable, c.f. [10], and may be more appropriate in other problem domains. We have experimented with the generalized nearest-neighbor technique [11] but find that for the same level of uncertainty in the density field, it is more computationally expensive.

The isodensity surfaces are defined implicitly by a graph-connectivity criterion similar to that used in FOF. Each particle is implicitly linked to tex2html_wrap_inline2098 nearest neighbors, where tex2html_wrap_inline2098 is a parameter of the method. An isodensity surface is defined by taking all the particles above some fixed density that are also linked together, as in FOF. The value of tex2html_wrap_inline2098 should be large enough that all particles are linked together when all particles are considered, i.e., the isodensity surface at zero density should comprise the entire system. tex2html_wrap_inline2098 should not be unnecessarily large, since this would compromise the spatial resolution of the method. In practice values of 12 to 24 have been successfully used. Note that isodensity surfaces are not directly calculated in the method (which is explained algorithmically below), but rather are a useful concept for understanding the method.

Once densities and linking lengths have been calculated, the particles are sorted by density, and then considered in order from highest density to lowest. Our goal is to assign each particle to a halo, which are numbered sequentially from zero. The halo number for each particle is calculated based on the halo numbers of the higher density particles to which it is linked, as follows:

This procedure results in a tree of halos, where the leaves correspond to the central regions of distinct halos, and the internal nodes correspond to composite halos, defined by isodensity surfaces, where various halos overlap.

next up previous
Next: Noise Suppression in IsoDen Up: The IsoDen Method Previous: The IsoDen Method

John Salmon
Sat Sep 27 18:44:36 PDT 1997