Abstract
Cosmological N-body simulations are crucial for understanding how the Universe evolves. Studying large-scale distributions of matter in these simulations and comparing them to observations usually involves detecting dense clusters of particles called "halos," which are gravitationally bound and expected to form galaxies. However, traditional cluster finders are computationally expensive and use massive amounts of memory. Recent work by Liu et al. (2015) showed the connection between cluster detection and memory-efficient streaming algorithms and presented a halo finder based on the heavy hitter algorithm. Later, Ivkin et al. (2018) improved the scalability of the suggested streaming halo finder with an efficient GPU implementation. Both works map particles' positions onto a discrete grid, and therefore lose the rest of the information, such as their velocities. Therefore, two halos traveling through each other are indistinguishable in positional space, while the velocity distribution of those halos can help to identify this process. In this project, we analyze data from the Millennium Simulation Project to motivate the inclusion of velocity into the streaming method. We demonstrate a method that allows one to find the same halos as before while also detecting those which were indistinguishable in prior methods.
Introduction
Cosmological N-body simulations model how the universe evolves by tracking billions (or even trillions) of particles. To make sense of this data, researchers look for "halos"—dense clusters of particles that represent the seeds of galaxies. The primary challenge is scale. A simulation with $10^{12}$ particles requires roughly 12 terabytes of RAM just to load the data, making traditional cluster-finding algorithms computationally prohibitive.
While previous "streaming" algorithms solved the memory issue by processing data in a single pass using a 3D grid, they had a significant blind spot: spatial overlap. If two halos are traveling through each other, they appear as a single dense blob in 3D space. To tell them apart, velocity data is required, but adding three extra dimensions (velocity in x, y, and z) to a grid-based approach usually causes memory requirements to explode.
Methodology
The proposed algorithm adapts the Count Sketch algorithm—a standard tool in computer science for finding "heavy hitters" in a massive data stream—to work with 6D particle data. The process involves:
- Discretization: Mapping the 3D simulation space into a grid of cells (1 Mpc/h per side).
- Velocity Integration: Instead of a full 6D grid, which would be too sparse, the researchers run four sketches in parallel: one 3D sketch for position and three 4D sketches, each combining 3D position with one component of velocity ($v_x, v_y,$ or $v_z$).
- The ID Function: A mathematical transformation maps a particle's 4D coordinates into a single unique integer ID for the streaming algorithm.
- Peak Detection: After processing, the algorithm examines approximate velocity histograms for each dense spatial cell. If a cell shows two distinct velocity peaks, it is flagged as a "region of interest" containing overlapping halos.
Key Insights and Results
By analyzing data from the Millennium Simulation Project (a single snapshot containing $10^{10}$ particles), the authors validated their method against the established SUBFIND catalog. Key findings include:
- Velocity as a Discriminator: For nearly 10,000 pairs of halos in close proximity, over 80% had mean velocity vectors separated by more than 25 degrees, confirming velocity as an effective "tie-breaker."
- High Recall: The streaming method captured up to 91% of the 267 regions of interest identified by an exact (non-streaming) version of the same algorithm.
- Accuracy Boost: Implementing a rule to ignore "noisy" peaks improved the algorithm's accuracy by 30%.
- Scalability: Memory usage scales linearly with the fraction of interesting regions found, allowing researchers to tune the algorithm based on available hardware.
Conclusion
This work demonstrates that a full 6D grid is not necessary to resolve overlapping clusters. Running separate 4D sketches for each velocity component is memory-efficient while providing sufficient information to identify multi-peak distributions. Future work will focus on integrating this 6D logic into high-performance GPU-based streaming tools to enable real-time halo finding in the world's largest simulations.
Summary updated