nips nips2009 nips2009-139 nips2009-139-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Parikshit Ram, Dongryeol Lee, William March, Alexander G. Gray
Abstract: Several key computational bottlenecks in machine learning involve pairwise distance computations, including all-nearest-neighbors (ďŹ nding the nearest neighbor(s) for each point, e.g. in manifold learning) and kernel summations (e.g. in kernel density estimation or kernel machines). We consider the general, bichromatic case for these problems, in addition to the scientiďŹ c problem of N-body simulation. In this paper we show for the ďŹ rst time O(đ?‘ ) worst case runtimes for practical algorithms for these problems based on the cover tree data structure [1]. 1
[1] A. Beygelzimer, S. Kakade, and J.C. Langford. Cover Trees for Nearest Neighbor. Proceedings of the 23rd International Conference on Machine learning, pages 97–104, 2006.
[2] J. H. Freidman, J. L. Bentley, and R. A. Finkel. An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Trans. Math. Softw., 3(3):209–226, September 1977.
[3] K. Deng and A. W. Moore. Multiresolution Instance-Based Learning. pages 1233–1242.
[4] D. Lee and A. G. Gray. Faster Gaussian Summation: Theory and Experiment. In Proceedings of the Twenty-second Conference on Uncertainty in ArtiďŹ cial Intelligence. 2006.
[5] J. Barnes and P. Hut. A Hierarchical đ?‘‚(đ?‘ log đ?‘ ) Force-Calculation Algorithm. Nature, 324, 1986.
[6] D. R. Karger and M. Ruhl. Finding Nearest Neighbors in Growth-Restricted Metrics. Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, pages 741–750, 2002.
[7] L. Greengard and V. Rokhlin. A Fast Algorithm for Particle Simulations. Journal of Computational Physics, 73:325–248, 1987.
[8] A. G. Gray and A. W. Moore. ‘đ?‘ -Body’ Problems in Statistical Learning. In NIPS, volume 4, pages 521–527, 2000.
[9] A. G. Gray and A. W. Moore. Nonparametric Density Estimation: Toward Computational Tractability. In SIAM International Conference on Data Mining, 2003.
[10] D. Lee, A. G. Gray, and A. W. Moore. Dual-Tree Fast Gauss Transforms. In Y. Weiss, B. Sch¨ lkopf, and J. Platt, editors, Advances in Neural Information Processing Systems 18, o pages 747–754. MIT Press, Cambridge, MA, 2006.
[11] D. Lee and A. G. Gray. Fast High-dimensional Kernel Summations Using the Monte Carlo Multipole Method. In To appear in Advances in Neural Information Processing Systems 21. 2009.
[12] S. Aluru, G. M. Prabhu, and J. Gustafson. Truly distribution-independent algorithms for the N-body problem. In Proceedings of the 1994 conference on Supercomputing, pages 420–428. IEEE Computer Society Press Los Alamitos, CA, USA, 1994.
[13] P. B. Callahan. Dealing with Higher Dimensions: the Well-Separated Pair Decomposition and its applications. PhD thesis, Johns Hopkins University, Baltimore, Maryland, 1995.
[14] P. B. Callahan and S. R. Kosaraju. A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-body Potential Fields. Journal of the ACM, 62(1):67– 90, January 1995.
[15] A. Beygelzimer, S. Kakade, and J.C. Langford. Cover trees for Nearest Neighbor. 2006. http://hunch.net/Ëœjl/projects/cover tree/paper/paper.ps.
[16] R. D. Skeel, I. Tezcan, and D. J. Hardy. Multiple Grid Methods for Classical Molecular Dynamics. Journal of Computational Chemistry, 23(6):673–684, 2002.
[17] A. G. Gray and A. W. Moore. Rapid Evaluation of Multiple Density Models. In ArtiďŹ cial Intelligence and Statistics 2003, 2003.
[18] A. G. Gray and A. W. Moore. Very Fast Multivariate Kernel Density Estimation via Computational Geometry. In Joint Statistical Meeting 2003, 2003. to be submitted to JASA.
[19] R. Krauthgamer and J. R. Lee. Navigating Nets: Simple Algorithms for Proximity Search. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 791–801, 2004.
[20] K. Clarkson. Fast Algorithms for the All Nearest Neighbors Problem. In Proceedings of the Twenty-fourth Annual IEEE Symposium on the Foundations of Computer Science, pages 226–232, 1983. 9