Fast Graph-based Higher-Order Clustering Statistics on the GPU
summary
The gist
We present a significant update to GRAMSCI (GRAph Made Statistics for Cosmological Information; C.
In short
GRAMSCI is an algorithm for fast computation of N-point spatial correlation functions using kd-trees and graph databases. Version 2 introduces speedups by replacing slow loops with merge-walk algorithms and implements parity decomposition for testing galaxy distribution symmetry. A major update is the GPU port, achieving speedups up to 9x on a single consumer GPU.
Key concepts
- kd-trees
- A data structure used to efficiently organize discrete points in R n space. They allow the algorithm to quickly find neighboring points within a given length scale without checking every possible pair, significantly speeding up spatial queries.
- N-point spatial correlation function
- A statistical measure that quantifies how often groups of N discrete points are found together in space. This goes beyond simple two-point measurements and helps scientists understand the complex clustering patterns in galaxy distributions.
- parity decomposition
- A technique used to separate the signal of a distribution into even and odd components. This allows researchers to directly test for parity violation, which is crucial for understanding if the galaxy clustering exhibits symmetry or asymmetry.
- GPU port (OpenACC)
- The implementation of GRAMSCI kernels on a Graphics Processing Unit using OpenACC. This leverages parallel processing power to drastically accelerate the computation of higher-order statistics like 3pCF and 4pCF, leading to significant performance gains over CPU calculations.
Terminology used across episodes
This episode discusses
- Fast Graph-based Higher-Order Clustering Statistics on the GPU · Paper Radio
- KDTREE 2: Fortran 95 and C++ software to efficiently search for near neighbors in a multi-dimensional Euclidean space
- Measurement of Parity-Violating Modes of the Dark Energy Spectroscopic Instrument (DESI) Year 1 Luminous Red Galaxies' 4-Point Correlation Function
The paper
Fast Graph-based Higher-Order Clustering Statistics on the GPU · Read on arXiv
Natural Science Research Institute (NSRI), University of Seoul
We present a significant update to GRAMSCI (GRAph Made Statistics for Cosmological Information; Sabiu et.al 2019), an algorithm for the fast computation of the general N-point spatial correlation function of any discrete point set embedded in R n. Utilizing the concepts of kd-trees and graph databases, we count all possible N-tuples in binned configurations within a given length scale. In this Version 2 update we describe several additions to the original code. We replace the binary-search inner loop, which cost O(m m) per hub--spoke pair, where m is the mean neighbor count, with a merge-walk algorithm that reduces the inner loop to O(m). We implement a parity-decomposed 4pCF that separates the signal into even and odd channels, enabling direct tests of parity violation in the galaxy distribution. We estimate the disconnected 4pCF internally on the same graph to return the connected 4pCF. We provide a Python interface so the Fortran engine can be called directly from NumPy arrays. Finally, and principally, we present a GPU port of the full query engine (OpenACC): the 3pCF, 4pCF, and parity-decomposed 4pCF kernels run on a single consumer GPU with measured speedups of 2.6 times (3pCF) to 9 times (4pCF) over a 64-thread CPU node, and an out-of-core tiling scheme allows graphs far exceeding device memory. We measure a 9 times10 9-edge BAO-scale 3pCF on a 24,GB card with about 20% overhead. We validate the code against its CPU reference, against analytic injection tests, and demonstrate BAO-scale applications on the DESI DR1 LRG sample compared against the EZmock ensemble.
Transcript
Introduction to the show: ident: Astrophysics. The day in astrophysics: observations, models and what the data forces.
Vera: We're looking at the paper: "Fast Graph-based Higher-Order Clustering Statistics on the GPU".
Jocelyn: Here's the gist of the paper. We present a significant update to GRAMSCI (GRAph Made Statistics for Cosmological Information; C.
Vera: G.
Jocelyn: Sabiu et al.
Vera: 2019), an algorithm for the fast computation of the general N-point spatial correlation function of any discrete point set embedded in R n Utilizing the concepts of kd-trees and graph databases, we count all possible N-tuples in binned configurations within a given length scale In this Version 2 update we describe several additions to the original code.
Paper summary: Vera: So we're looking at this paper today by Sabiu and his team on this thing called Fast Graph-based Higher-Order Clustering Statistics on the GPU. It’s essentially an update to a tool called GRAMSCI, which is used for calculating the general N-point spatial correlation function for any discrete set of points in R n.
Jocelyn: That sounds like a pretty heavy lift, Vera. What’s the main idea here? What are they trying to speed up with this version two update?
Vera: They’re focusing on making the computation faster because calculating those N-point statistics can get really slow when you have a lot of data points. The abstract says they utilize kd-trees and graph databases to count all possible N-tuples in binned configurations within a given length scale.
Subrahmanyan: That setup with kd-trees and graph databases is smart because it lets you organize the points efficiently, which is necessary when you’re dealing with spatial information across different dimensions. But the real interest lies in how they're improving the counting process itself.
Vera: Right, that’s right. They replace a binary search loop that used to cost O of m log m per hub-spoke pair with something called a merge-walk algorithm, which cuts that inner loop cost down to just O of m. That’s a big win for computation time.
Jocelyn: Cutting the inner loop from logarithmic complexity down to linear complexity in terms of the mean neighbor count, that sounds like it could make those large calculations much more feasible on modern hardware. What else are they adding?
Vera: They also implemented this parity-decomposed four-point correlation function, or 4pCF <ref:2607.06604#pg1>. This breaks the signal into even and odd channels, which lets them directly test for parity violation in the galaxy distribution. Plus, they estimate the disconnected four-point correlation function internally on the same graph to give you the connected one.
Subrahmanyan: Testing for parity violation is significant because it’s a direct probe of fundamental symmetries in how structure forms; that kind of information is often inaccessible through just looking at the two-point correlation function alone. The connection between gravitational evolution and this structure generation is what makes the three-point correlation function so important, which they mention later.
Jocelyn: So they are moving beyond just counting pairs to looking at triplets and quadruplets, and they’re making it faster by using a GPU port with OpenACC that runs on a single consumer GPU. The speedup numbers are quite telling here.
Vera: They report measured speedups of two point six times for the three-point correlation function, or three point six times, and up to nine times for the four-point correlation function over a sixty four thread CPU node. That’s a measurable performance gain when you compare it to the baseline.
Subrahmanyan: Nine times is substantial, especially when you consider that this method allows you to probe higher-order moments like the four-point correlation function, which is related to the primordial trispectrum and inflationary models; that kind of structure gives us leverage on those physics questions.
Paper summary: Jocelyn: They also mentioned an out-of-core tiling scheme, which means they can handle graphs that are much larger than what fits in the device memory. That’s important for real cosmological surveys like the DESI DR1 LRG sample they used for validation.
Vera: They did validate this code against its CPU reference and even ran it against analytic injection tests to make sure everything was unbiased at a very low level, about zero point three percent error across the whole range.
Subrahmanyan: So, the implication here is that we can now tackle these higher-order statistics on much larger scales and with more complex structures than was previously possible due to computational limits. It gives us more direct handles on the galaxy-matter connection by breaking that degeneracy mentioned earlier in relation to the three-point correlation function.
Jocelyn: Thinking about those higher-order probes, what do you think is the bigger picture here for cosmology? What does being able to calculate these things faster actually mean for our understanding of structure formation?
Vera: It means we can get closer to testing models of nonlinear gravitational evolution more precisely because we aren't limited by slow computation; we can push the limits on what information those statistics reveal about galaxy bias and matter distribution.
Subrahmanyan: Precisely. If you want to confirm or kill certain inflationary models, you need these higher-order statistics, and this software makes that work much more accessible for the kind of large surveys we are running right now.
Jocelyn: So, looking at the title again, Fast Graph-based Higher-Order Clustering Statistics on the GPU. It’s clear this paper is focused on bridging the gap between complex statistical theory and actually being able to run these kinds of calculations quickly enough for real data sets.
Vera: The authors are making GRAMSCI much more capable by improving the core enumeration algorithm, giving us better tools for measuring things like the three-point correlation function and the connected four-point correlation function.
Subrahmanyan: It’s about making those higher-order probes practical; it moves them from being theoretical possibilities to something you can actually run on a large survey catalog.
Jocelyn: And with this GPU port, we see tangible speedups that let us probe scales relevant to surveys like DESI. The validation against the EZmock ensemble and the BAO-scale applications show that the results are consistent with what we expect from simulations.
Vera: It’s about providing a robust, fast engine for those calculations so we can finally extract meaningful cosmological information from these massive galaxy samples without getting bogged down in slow processing.
Subrahmanyan: So, to wrap up, this work gives us a faster way to calculate connected higher-order statistics on the GPU using kd-trees and graph databases, which helps break degeneracies in clustering measurements and provides better tests for cosmological models.
Conclusion: Vera: So we’re wrapping up on this GRAMSCI update, which is really focused on making these complex spatial statistics much more accessible by moving them to a GPU.
Jocelyn: Yeah, the title itself tells you a lot—it's about using graph databases and the GPU for these higher-order clustering statistics.
Subrahmanyan: What that means in plain terms is they’ve figured out a way to calculate things like the three-point or four-point correlation function much faster than before.
Vera: Exactly, because the original methods were slow, but this version uses kd-trees and graph databases to count those N-tuples efficiently.
Jocelyn: And they’ve seen some pretty good speedups on a consumer GPU, with numbers up to nine times faster for the four-point function.
Subrahmanyan: That speedup is important because it lets us finally look at probes like the four-point function, which tells us about things like the primordial trispectrum in inflationary models.
Vera: It means we can do more than just measure how galaxies clump together; we can test those deeper physics questions.
Jocelyn: The authors also added this parity decomposition, which lets them directly look for parity violation in how structures form in the universe.
Subrahmanyan: That’s a big deal for structure formation theory because it connects the observed galaxy distribution to fundamental symmetries of nature itself.
Vera: They validated this against real data from DESI and showed that their results match what we expect from simulations, which is a key check on the whole thing.
Jocelyn: The main implication is that these higher-order statistics are becoming practical tools for large cosmological surveys.
Subrahmanyan: So, we’re moving from theory that requires massive computation to something you can actually run on big data sets now.
Vera: And with faster tools, we can test those models more precisely and see if the universe behaves exactly as predicted by our current theories.
Jocelyn: It opens up a lot of new avenues for follow-up observations based on these higher-order measurements.
More episodes
- 2607.17929-gevolution 2.0: GPU-accelerated relativistic N-body simulations for cosmology
- The day in conversation for 2026-11-19
- Daily Summary for 2026-11-19
- 2509.02657-On the synergetic use of Ariel and JWST for exoplanet atmospheric science
- 2609.10042-Modelling Fourier filtering wavefront sensors for PSD-based methods: the AOPERA tool
- 2511.05639-Performance of the AstroPix Prototype Module for the Barrel Imaging Calorimeter at the ePIC Detector and in Space-Based Payloads
- 2610.19909-RPCA: a Resolved PSF reconstruction method for undersampled images
- 2512.03440-An Analysis of LIGO Glitches Using t-SNE During the First Part of the Fourth LIGO-Virgo-KAGRA Observing Run
- 2608.10284-Lunar Reflective Interferometry
- 2610.16633-Institutional broadening of the Japanese astronomy and astrophysics research community during 1996-2025