'N-Body' Problems in Statistical Learning

By Alexander G. Gray, Andrew W. Moore. 2000

322 citations recorded by the source corpus.

Subfields: Statistics and Probability, Model Architectures

How researchers see this paper

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

In Statistics and Probability

In Model Architectures

Citations in the corpus

Maximum inner-product search using cone trees (2012, methodology): “The search is performed by traversing both trees simultaneously using the dual-tree algorithm [15].”
Barnes-Hut-SNE (2013, methodology): “This can be done using a dual-tree algorithm [7] that simultaneously traverses the quadtree twice, and for every pair of nodes decides whether the interaction between the corresponding cells can be used as “summary” for the interactions between all points inside these two cells.”
Fast maximum a-posteriori inference on Monte Carlo state spaces (2005, methodology): “In this paper, we address the need of fast algorithms for computing weighted max-kernel on Monte Carlo grids by demonstrating how the quadratic cost can be reduced to N logN by adopting and extending powerful algorithms proposed for N-body simulation [ 7 , 8].1”
Nonparametric Density Estimation: Toward Computational Tractability (2003, methodology): “We presented an early bare-bones dualtree method for the KDE problem in [11], which used the exclusion/inclusion idea and an ad hocapproximation method.”
Dynamic social network analysis using latent space models (2005, methodology): “This simplification is very important because we can now use a spatial data structure such as a kd-tree in the low dimensional latent space to retrieve all pairs of entities that lie within each other’s radius in timeO(rn+n log n) where r is the average number of in-radius neighbors of an entity [10”
Nonparametric Conditional Density Estimation in a High-Dimensional Regression Setting (2016, methodology): “…partition trees (Dasgupta and Sinha 2013), cover trees (Beygelzimer, Kakade, and Langford 2006), approximate NN methods (e.g., Nolen and Lin 2013), and (parallelizable) multi-trees (Gray and Moore 2000; Boyer, Riegel, and Gray 2007) that trade off evaluation precision and computational speed.”
Accelerating t-SNE using tree-based algorithms (2014, background): “The embedding of the street view house numbers data set clearly shows ten clusters that correspond to the ten different digits, whilst images that are difficult to recognize tend to be located near the center of the embedding. c©2014 Laurens van der Maaten.”
Think Globally, Fit Locally: Unsupervised Learning of Low Dimensional Manifold (2003, methodology): “…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 log N) time (Friedman et al., 1977; Gray and Moore, 2001; Moore et al., 2000; Omohundro, 1989, 1991).”
Cover trees for nearest neighbor (2006, background): “If the metric is non-Euclidean, or the Euclidean dimension is large, ball trees (Uhlmann, 1991; Omohundro, 1987) provide compelling performance in many practical applications (Gray & Moore, 2000).”
Spectral Clustering for Speech Separation (2009, methodology): “We can exploit classical efficient algorithms to perform this task (Gray and Moore, 2001).”
Learning Spectral Clustering, With Application To Speech Separation (2006, methodology): “We can exploit classical efficient algorithms to perform this task (Gray and Moore, 2001).”
Linear-time Algorithms for Pairwise Statistical Problems (2009, methodology): “So far, the improvements in runtimes have only been empirical with no rigorous runtime bounds [2, 8 , 9, 17, 18].”
Fast High-dimensional Kernel Summations Using the Monte Carlo Multipole Method (2008, methodology): “The subspace of each leaf node is computed using PCABASE which can use the exact PCA [3] or a stochastic one [2].”
Measuring Association on Topological Spaces Using Kernels and Geometric Graphs (2020, unknown): “, [44] (and http: // www.”