gieseke / bufferkdtree

A Python library for large-scale nearest neigbhor computations via k-d trees and GPUs.

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.

bufferkdtree's Issues

buffer_kd_tree, verbose=1 issue on python3.6

verbose=1 causes error in python3.
I updated buffer_kdtree/base.py to replace 'unicode' with 'str'

Using buffer kd tree for epsilon neighborhood search , graph creation, and with data having dimensional > 50 ?

Bonjour Fabian,

I have basically 2 questions:
1: what are the issues in using your library when the dimensionaity of the data-set is > 50 ?
(is it the accuracy of the neighbors found in that case not valid)
2: is it possible to use bufferkd tree for a range based search ( epsilon neighborhood ) instead of nearest neighbors ?

Kindly reply
Amitoz

Using the KDTree OpenCL Code directly

Good day, I would like to use your KDTree OpenCL code in a c++ program. Can I get some direction on where to look at and begin?

error install bufferkdtree

I run on google colab.
!pip install bufferkdtree

Error:
Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.

Full error:
Collecting bufferkdtree
Using cached bufferkdtree-1.3.tar.gz (192 kB)
WARNING: Discarding https://files.pythonhosted.org/packages/f0/34/2c4c1dd55cd27095ad87217f12a1dd213c92656d3c4c3a14156628833ead/bufferkdtree-1.3.tar.gz#sha256=96e5ea3254c9d94e5f149a49fb3b48ce752958e8d20ce317e9532bd100cf82e4 (from https://pypi.org/simple/bufferkdtree/). Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.
Using cached bufferkdtree-1.2.tar.gz (184 kB)
WARNING: Discarding https://files.pythonhosted.org/packages/38/48/bde2e6b2eab221423189e4f13d423590f140d0004ead4512777878adf4ea/bufferkdtree-1.2.tar.gz#sha256=d035f6478bf27c0cf9f55b49d05025ec7f0ee3320bf99829b85c9e7741d0769b (from https://pypi.org/simple/bufferkdtree/). Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.
Using cached bufferkdtree-1.1.1.tar.gz (173 kB)
WARNING: Discarding https://files.pythonhosted.org/packages/34/78/f2127a6c7e6da046aef7351fcc75eb94ee10b220e97f86f1335f5ed95446/bufferkdtree-1.1.1.tar.gz#sha256=7992ca3d114550c7a09d882216619b82114e9d096423d9489c49f497d5d892a1 (from https://pypi.org/simple/bufferkdtree/). Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.
Using cached bufferkdtree-1.1.tar.gz (173 kB)
WARNING: Discarding https://files.pythonhosted.org/packages/c5/ae/48b9239c4e631be078ebc8b5496440981bdc8555b2d1a5d07d88c42fdfb8/bufferkdtree-1.1.tar.gz#sha256=11242ce6283f908788c2be32519c6eb408b483a0a455376f8e5b3917c229cc7c (from https://pypi.org/simple/bufferkdtree/). Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.
Using cached bufferkdtree-1.0.2.tar.gz (99 kB)
WARNING: Discarding https://files.pythonhosted.org/packages/41/b2/dcba48b531a7401e915771881eb4cca00f7e53d75d2412c080244f464e4f/bufferkdtree-1.0.2.tar.gz#sha256=20296449aef5751cdcc49bf595a12bdec7bb3cc97065a28349f908be54ec1d9e (from https://pypi.org/simple/bufferkdtree/). Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.
Using cached bufferkdtree-1.0.1.tar.gz (98 kB)
WARNING: Discarding https://files.pythonhosted.org/packages/df/c4/60f36110e2157717e7b4a278a62d43d0140761637541f1ec7cecd47ef305/bufferkdtree-1.0.1.tar.gz#sha256=3aeb00e52b1abe0c693efa234c045c963a50d1f5143d9bfc3dec479e6e874a39 (from https://pypi.org/simple/bufferkdtree/). Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.
ERROR: Could not find a version that satisfies the requirement bufferkdtree (from versions: 1.0.1, 1.0.2, 1.1, 1.1.1, 1.2, 1.3)
ERROR: No matching distribution found for bufferkdtree

Can't run bufferkdtree example after installation

Hi, Fabian,

I'm trying to run the bufferkdtree code following the document. I install the bufferkdtree with the command "python setup.py install --user" and the last few lines of output are:

Writing /home/min/a/liu1274/.local/lib/python2.7/site-packages/neighbors_brute-0.0.0-py2.7.egg-info
running install_clib
customize UnixCCompiler

Since there is no obvious signal to show whether the installation succeeds or fails, so I assume it's good and continue with the example in the document. However, when I execute the "nbrs_buffer_kd_tree.fit(X)", it doesn't work well:

_Traceback (most recent call last):
File "test.py", line 16, in
nbrs_buffer_kd_tree.fit(X)
File "/home/min/a/liu1274/workspace/bufferkdtree-master/bufferkdtree/neighbors/base.py", line 194, in fit
self.wrapper = self._get_wrapper()
File "/home/min/a/liu1274/workspace/bufferkdtree-master/bufferkdtree/neighbors/base.py", line 295, in get_wrapper
from bufferkdtree.neighbors.brute.base import BruteNN
File "/home/min/a/liu1274/workspace/bufferkdtree-master/bufferkdtree/neighbors/brute/base.py", line 12, in
import bufferkdtree.neighbors.brute.wrapper_cpu_float as wrapper_cpu_float
ImportError: No module named wrapper_cpu_float

I was wondering whether I installed the bufferkdtree correctly and how to figure this problem out. I'm using a university server, so I can't have the root access.

Thanks very much!

Jianqiao

An OpenCL error with code -1001 in file /tmp/pip-install-dw80rw9b/bufferkdtree/bufferkdtree/src/opencl.c and line 215 occurred ...

An OpenCL error with code -1001 in file /tmp/pip-install-dw80rw9b/bufferkdtree/bufferkdtree/src/opencl.c and line 215 occurred ...
i got this error when i tried to run
can you help me solve this ?

Compilation issue on a Windows machine

Hi,

I have a windows machine with Python 3.6.5. I followed the instructions to make sure that I have a required Visual Studio, OpenCL support via CUDA, and Swig.

I downloaded the repository and run the command "python setup.py install". The installation ended with this error message:

c:\users\imarroquin\downloads\important_python_packages\bufferkdtree-master\bufferkdtree\src\neighbors\kdtree\include../../../include/util.h(20): fatal error C1083: Cannot open include file: 'sys/res
ource.h': No such file or directory

The "utils.h" file have these command lines:
#include <sys/resource.h>
#include <sys/time.h>

Searching on the web, it seems that these files are not part of a windows compiler. if this is the case, do you have a wheel file that I can use?

Many thanks,
Ivan

free kdtree memory in the GPU

Hi, is there any function that free the allocated kdtree memory in the GPU ?