Skip to content
A Python library for large-scale nearest neigbhor computations via k-d trees and GPUs.
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
bufferkdtree release 1.3 Nov 11, 2016
docs update Nov 11, 2016
examples update Nov 11, 2016
.gitignore automatic numpy installation during setup Oct 19, 2016
CONTRIBUTING.md initial github commit Sep 16, 2015
LICENSE
MANIFEST.in installation process, documentation, examples Oct 27, 2016
README.rst update Nov 11, 2016
requirements.txt added copyright to all files Oct 24, 2016
setup.cfg added cl files to installation process Oct 1, 2015
setup.py installation process, documentation, examples Oct 27, 2016

README.rst

bufferkdtree

The bufferkdtree package is a Python library that aims at accelerating nearest neighbor computations using both k-d trees and modern many-core devices such as graphics processing units (GPUs). The implementation is based on OpenCL.

The buffer k-d tree technique can be seen as an intermediate version between a standard parallel k-d tree traversal (on multi-core systems) and a massively-parallel brute-force implementation for nearest neighbor search. In particular, it makes use of the top of a standard k-d tree (which induces a spatial subdivision of the space) and resorts to a simple yet efficient brute-force implementation for processing chunks of "big" leaves. The implementation is well-suited for data sets with a large reference set (e.g., 1,000,000 points) and a huge query set (e.g., 10,000,000 points) given a moderate dimensionality of the search space (e.g., from d=5 to d=50).

Documentation

See the documentation for details and examples.

Dependencies

The bufferkdtree package has been tested under Python 2.6/2.7/3.*. The required Python dependencies are:

  • NumPy >= 1.11.0

Further, Swig, OpenCL (version >= 1.2), setuptools, and a working C/C++ compiler need to be available. See the documentation for more details.

Quickstart

The package can easily be installed via pip via:

pip install bufferkdtree

To install the package from the sources, first get the current stable release via:

git clone https://github.com/gieseke/bufferkdtree.git

Afterwards, on Linux systems, you can install the package locally for the current user via:

python setup.py install --user

On Debian/Ubuntu systems, the package can be installed globally for all users via:

python setup.py build
sudo python setup.py install

Disclaimer

The source code is published under the GNU General Public License (GPLv2). The authors are not responsible for any implications that stem from the use of this software.

You can’t perform that action at this time.