Paul B. Callahan
Skip Abstract Section
Abstract
We define the notion of a well-separated pair decomposition of points in d-dimensional space. We then develop efficient sequential and parallel algorithms for computing such a decomposition. We apply the resulting decomposition to the efficient computation of k-nearest neighbors and n-body potential fields.
- ~AARSETH, S. J., GOTr, J. R., III, AND TURNER, E. L. 1979. N-body simulations of galaxy ~clustering. I. Initial conditions and galaxy collapse times. Astrophys. J. 228, 664-683.Google Scholar
- ~ABRAHAMSON, K., DADOUN, N., KIRKPATRICK, D. A., AND PRZYTCHKA, T. 1989. A simple parallel ~tree contraction algorithm. J. Algorithms 10, 2, 287-302. Google Scholar
- ~ABRAMSON, N. 1963. Information Theory and Coding. McGraw-Hill, New York.Google Scholar
- ~AGARWAL, P. K., EDELSBRUNNER, H., SCHWARTZKOPF, O., AND WELZL, E. 1991. Euclidean ~minimum spanning trees and bichromatic closest pairs. Disc. Computat. Geom. 6, 407-422. Google Scholar
- ~AGARWAL, P. K., AND MATOU~EK, J. 1992. Relative neighborhood graphs in three dimensions. In ~Proceedings of the 3rd Annual Sympostum on Discrete Algorithms. ACM-SIAM, New York and ~Philadelphia, pp. 58-65. Google Scholar
- ~APPEL, A. W. 1985. An efficient program for many-body simulation. SIAM J. Sci. Star. Comput. ~6, 85-103.Google Scholar
- ~BARNES, J., AND HUT, P. 1986. A hierarchical O(N log N) force-calculation algorithm. Nature ~~ 324, 4, 446-449.Google Scholar
- ~BENTLEY, J. L. 1980. Multidimensional divide-and-conquer. Commun. ACM 23, 4 (Apr), 214-229. Google Scholar
- ~CALLAHAN, P. B., AND KOSAP, AJU, S. R. 1992. A decomposition of multi-dimensional point-sets ~with applications to k-nearest-neighbors and n-body potential fields. In Proceedings of the 24th ~Annual Symposium on the Theory of Computing (Victoria, B. C., Canada, May 4-6). ACM, New ~York, pp. 546-556. Google Scholar
- ~COLE, R., AND GOODRICH, M. T. 1988. Optimal parallel algorithms for polygon and point-set ~problems. In Proceedings of the 4th ACM Symposium on Computational Geometry (Urbana- ~Champaign, IlL, June 6-8). ACM, New York, pp. 201-210. Google Scholar
- ~COLE, R., AND GOODRICH, M. T. 1992. Optimal parallel algorithms for point-set and polygon ~problems. Algorithmica 7, 3-23.Google Scholar
- ~FRIEZE, A. M., MILLER, G. L., AND TENG, S.-H. 1992. Separator based parallel divide and ~Algorithms andArch~tectures (San Diego, Calif., June 29-July 1). ACM, New York, pp. 420-429. Google Scholar
- ~OAZIT, H., MILLER, O. L., AND TENG, S.-H. 1988. Optimal tree contraction in the EREW model. ~In Concurrent Computations, S. K. Tewsburg, B. W. Dickinson, and S. C. Schwartz, eds. Plenum ~Publishing, New York, pp. 139-155.Google Scholar
- ~GREENGARD, L. F. 1988. The Rapid Evaluation of Potential Ftelds in Particle Systems. The MIT ~Press, Cambridge, Mass.Google Scholar
- ~GREENGARD, L., AND GROPP, W. D. 1990. A parallel version of the fast multipole method ~Computers Math. Applic. 20, 7, 63-71.Google Scholar
- ~GREENGARD, m., AND ROKHLIN, V. 1987. A fast algorithm for particle simulations, J. Comput ~Physics 73, 325-348. Google Scholar
- ~HAFNER, C., AND mUSTER, N. 1991. Computations of electromagnetic fields by the multiple ~multipole method (generalized multipole technique). Radio Sci. 26, 1, 291-297.Google Scholar
- ~KATZENELSON, J. 1989. Computational structure of the N-body problem. SIAM J. Sci. Star ~Comput. 10, 4 (July), 787-815. Google Scholar
- ~KOSARAJU, S. R., AND DELCHER, A. L. 1988. Optimal parallel evaluation of tree-structured ~computations by raking. In VLSI Algorithms and Architectures: Proceedings of the 3rd Aegean ~Workshop on Computing, J. Reif, ed. Springer-Verlag, New York, pp. 101-110. Google Scholar
- ~MILLER, G. L., TENG, S.-H. AND VAVASIS, S. A. 1991. A unified geometric approach to graph ~separators. In Proceedings of the 32nd Annual Symposium on Foundatzons Computer Science ~IEEE, New York, pp. 538-547. Google Scholar
- ~MILLER, R. H., AND PRENDERGAST, K. H. 1968. Stellar dynamics in a discrete phase space ~Astrophys. J. 151, 699-709.Google Scholar
- ~MILLER, R. H., PRENDERGAST, K. H. AND QUIRK, W. J. 1970. Numerical experiments on spiral ~structure. Astrophys. J. 161, 903 916.Google Scholar
- ~PAN, V. Y., REIF, J. H., AND TATE, S. R. 1992. The power of combining the techniques oJ ~algebraic and numerical computing: Improved approximate multipoint polynomial evaluation ~and improved multipole algorithms. In Proceedings of the 32nd Annual Symposium of Founda- ~ttons of Computer Science. IEEE New York, pp. 703-7t3.Google Scholar
- ~PREPARATA, F. P., AND SHAMOS, M. I. 1985. Computational Geometry. An Introduction. Springer- ~Verlag, New York. Google Scholar
- ~REIF, J. H., AND TARE, S. R. 1992. N-body simulation I: Potential field evaluation. Technical ~report, Comput. Sci. Dept., Duke Univ.Google Scholar
- ~ROKHL1N, V. 1985. Rapid solution of integral equations of classical potential theory. J. Compu- ~tat. Phys. 60, 187-207.Google Scholar
- ~SCHMIDT, K. E., AND LEE, M. m. 1991. Implementing the fast multipole method in three ~dimensions. J. Star. Phys. 63 5-6 (June), 1223-1235.Google Scholar
- ~VAIDYA, P. M. 1986. An optimal algorithm for the all-nearest-neighbors problem. In Proceedin&, ~of the 27th Annual Sympostum Foundations of Computer Science. IEEE, New York, pp. 117-122Google Scholar
- ~AIDYA, P. M. 1989. An O(n log n) algorithm for the all-nearest-neighbors problem. Disc ~omputat. Geom. 4, 101-115. Google Scholar
- ~YAO, A. C. 1982. On constructing minimum spanning trees in k-dimensional space and related ~problems. SIAM J. Comput. 11,721-736.Google Scholar
- ~ZHAO, F., AND JOHNSSON, S. L. 1991. The parallel multipole method on the Connection ~Machine. SIAM J. Sct. Stat. Comput. 12, 6, 1420-1437. Google Scholar
Index Terms
- A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields
Recommendations
A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version)
STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of ComputingWe define the notion of a well-separated pair decomposition of points in d-dimensional space. We develop efficient sequential and parallel algorithms for computing such a decomposition. We apply the resulting decomposition to the efficient computation ...
Extending LAESA Fast Nearest Neighbour Algorithm to Find the k Nearest Neighbours
Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern RecognitionMany pattern recognition tasks make use of the k nearest neighbour (k-NN) technique. In this paper we are interested on fast k- NN search algorithms that can work in any metric space i.e. they are not restricted to Euclidean-like distance functions. ...
λ-Diverse Nearest Neighbors Browsing for Multidimensional Data
Traditional search methods try to obtain the most relevant information and rank it according to the degree of similarity to the queries. Diversity in query results is also preferred by a variety of applications since results very similar to each other ...
Comments