Fast Algorithms and Efficient Statistics: N-point Correlation Functions

Abstract

We present here a new algorithm for the fast computation of N-point correlation functions in large astronomical data sets. The algorithm is based on kdtrees which are decorated with cached sufficient statistics thus allowing for orders of magnitude speed-ups over the naive non-tree-based implementation of correlation functions. We further discuss the use of controlled approximations within the computation which allows for further acceleration. In summary, our algorithm now makes it possible to compute exact, all-pairs, measurements of the 2, 3 and 4-point correlation functions for cosmological data sets like the Sloan Digital Sky Survey (SDSS; York et al. 2000) and the next generation of Cosmic Microwave Background experiments (see Szapudi et al. 2000).

To appear in Proceedings of MPA/MPE/ESO Conference "Mining the Sky", July 31 - August 4, 2000, Garching, Germany

Cited by in corpus (30)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• EMERGE - An empirical model for the formation of galaxies since $z\sim 10$
• Data Mining and Machine Learning in Astronomy
• The Skewness of the Aperture Mass Statistic
• nbodykit: an open-source, massively parallel toolkit for large-scale structure
• Computing the Three-Point Correlation Function of Galaxies in $\mathcal{O}(N^2)$ Time
• Testing the theory of gravity with DESI: estimators, predictions and simulation requirements
• Three-Point Correlation Functions of SDSS Galaxies: Luminosity and Color Dependence in Redshift and Projected Space
• Modelling non-linear redshift-space distortions in the galaxy clustering pattern: systematic errors on the growth rate parameter
• Empirical constraints on the formation of early-type galaxies
• ENCORE: An $\mathcal{O}(N_{\mathrm{g}}^2)$ Estimator for Galaxy $N$-Point Correlation Functions
• Fast n-point correlation functions and three-point lensing application
• GaBoDS: The Garching-Bonn Deep Survey: VII. Probing galaxy bias using weak gravitational lensing
• Evidence for an environment-dependent shift in the baryon acoustic oscillation peak
• Estimating Covariance Matrices for Two- and Three-Point Correlation Function Moments in Arbitrary Survey Geometries
• Graph Database Solution for Higher Order Spatial Statistics in the Era of Big Data
• Redshift-Space Enhancement of Line-of-Sight Baryon Acoustic Oscillations in the SDSS Main-Galaxy Sample
• How covariant is the galaxy luminosity function?
• Search for primordial non-Gaussianity in the quasars of SDSS-III BOSS DR9
• When do cosmic peaks, filaments or walls merge? A theory of critical events in a multi-scale landscape
• Efficient Computation of $N$-point Correlation Functions in $D$ Dimensions
• CMB Power Spectrum Estimation via Hierarchical Decomposition
• Conditional Cumulants in Weakly Non-linear Regime
• On the Fast Random Sampling and Other Properties of the Three Point Correlation Function in Galaxy Surveys
• Tree-less 3d Friends-of-Friends using Spatial Hashing
• Galactos: Computing the Anisotropic 3-Point Correlation Function for 2 Billion Galaxies
• Multibody Multipole Methods
• Pair Counting without Binning -- A New Approach to Correlation Functions in Clustering Statistics
• A fast algorithm for identifying Friends-of-Friends halos
• K-minus Estimator Approach to Large Scale Structure