14-18 October 2013
Amsterdam, Beurs van Berlage
Europe/Amsterdam timezone

A well-separated pairs decomposition algorithm for kd-trees implemented on multi-core architectures

17 Oct 2013, 11:44
Effectenbeurszaal (Amsterdam, Beurs van Berlage)


Amsterdam, Beurs van Berlage

Oral presentation to parallel session Software Engineering, Parallelism & Multi-Core Software Engineering, Parallelism & Multi-Core


Prof. Peter Hobson (Brunel University (GB))Dr raul lopes (School of Design and Engineering - Brunel University, UK)


Variations of kd-trees represent a fundamental data structure frequently used in geometrical algorithms, Computational Statistics, and clustering. They have numerous applications, for example in track fitting, in the software of the LHC experiments and in physics in general. Computer simulations of N-body systems, for example, have seen applications in the study of dynamics of interacting galaxies, particle beam physics, and molecular dynamics in biochemistry. The many-body tree methods devised by Barnes and Hutt in the 1980s and the Fast Multipole Method introduced in 1987 by Greengard and Rokhlin use variants of kd-trees to reduce the computation time upper bound to O(n log n) or even O(n) from the O(n^2) demanded by Particle in Cell algorithms. Naive approaches to kd-trees can, however, lead to algorithms that produce uncompressed trees and use O(n^2) work to build a tree for n items. We present an algorithm that uses the principle of well-separated pairs decomposition to always produce compressed trees in O(n log n) work. We present and evaluate parallel implementations for the algorithm that can take advantage of multi-core architectures.

Primary author

Dr raul lopes (School of Design and Engineering - Brunel University, UK)


Ivan Reid (Brunel University (GB)) Prof. Peter Hobson (Brunel University (GB))

Presentation Materials