Fast Algorithms and Efficient Statistics: N-Point Correlation Functions

By Andrew W. Moore, Andrew J. Connolly, Christopher R. Genovese, A. Gray, La Grone, Nick Kanidoris, R. Nichol, Jeff Schneider, A. Szalay, Istvan Szapudi and 1 more. 2000

101 citations recorded by the source corpus.

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).

Subfields: Artificial Intelligence, Instrumentation, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Instrumentation

In Statistical and Nonlinear Physics

Citations in the corpus

Depth-Based Hand Pose Estimation: Methods, Data, and Challenges (2015, unknown): “We plot results for several systems on the ICL testset us-ing max-error (we include avg-error in supplemental Section B).”
Computing the Three-Point Correlation Function of Galaxies in $\mathcal{O}(N^2)$ Time (2015, methodology): “Current algorithms, such as that used for the McBride et al. (2011) measurement (presented in Moore et al. 2001, Gray et al. 2004, Nichol et al. 2006, and Gardner et al. 2007) fundamentally scale as the number of possible triangles in a survey.”
EMERGE – an empirical model for the formation of galaxies since z ∼ 10 (2017, methodology): “Finally, we calculate the z = 0 galaxy two-point correlation function in a given stellar mass bin using kd-trees following Moore et al. (2001), which we found to be very effective.”
Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifold (2003, methodology): “For many distributions of data, however—and especially for those concentrated on a thin submanifold of the input space—constructions such as K-D trees or ball trees can be used to compute the neighbors in O(N logN) time (Friedman et al., 1977; Gray and Moore, 2001; Moore et al., 2000; Omohundro, 198”
Weak Gravitational Lensing (2012, unknown): “pairs [96, 63].”
The skewness of the aperture mass statistic (2003, background): “Again, we defer to Moore et al. (2001) and Zhang & Pen (2004) for a more complete description of this type of data structure.”