This is an Erlang library for operating on k-d trees, implemented as a set of erlang NIF (native implemented functions).
For general information about k-d trees please see wikipedia article.
In short, k-d tree object is a set of points in k-dimensional space, organized (indexed) in memory so that the search operation for nearest point next to a given would be as fast as possible. This library is specially optimized for querying large dataset (millions of points).
-
Erlang R15 or later
-
GCC (tested on 4.8) or clang (tested on 3.3)
-
libc with -lm (should be available on any linux distribution by default)
-
GNU make
The C sources are made using options --std=C99 --Wall --Wextra --pedantic so I believe it should be easy to adopt those sources for other environments.
- Point coordinates are limited by IEEE 754 double-precission (64bit) boundaries.
- Node index is limited to uint64_t (erlang positive integer up to 2^64-1
Just 'cd' to project directory and type 'make'. This should build the erlang application in 'ebin' directory and shared object file in 'priv/lib'.
Then set the 'DESTDIR' environment variable and type 'make install', like this:
cd yalinka make DESTDIR=/usr/lib/erlang/lib make install
Don't forget to use 'gmake' if you're *bsd follower.
Currently there is no any configuration options.
Autogenerated module documentation available online here. The usage is actually as easy as
{ok, Reference} = yalinka:new([{0, 0.0,0.0,0.0}, {1, 1.0,1.0,1.0}]),
{ok, [{Idx, Distance}]} = yalinka:search(Reference, {0.7,0.7,0.7}, 1),
...it is pretty straightforward I believe.
First, we need to create a tree object. This can be done by calling yalinka:new/1 with the only one parameter - a list of node specification, in form {Idx, {X, Y, Z}}, where Idx is limited to positive integer and X, Y, Z is a float(). This call will swallow all the nodes, then build a tree in internal structure and return the pointer to that structure.
Next, we can query the engine to find the nearest node in the given tree to the given point. This is done by calling yalinka:search(Tree, {X, Y, Z}, Count), where Tree is the reference returned by yalinka:new/1, Count is the number of first nearest Count nodes to find and {X, Y, Z} is a point specification - a tuple with floats inside. The function cal returns {ok, List}, where List is the list of tuples {Idx, Distance}. Idx was an index from node specification when the tree was built while the Distance is the distance between specified point and found node.
For extremely large databases it is strongly advised to split data preparation and usage stages; at the first stage the data prepared should be stored to file using yalinka:store/2 and then, at the second stage, loaded by yalinka:load/1 into memory:
1> {ok, R} = yalinka:load("/home/fisher/erl/strikead/geoid/test/db/xperian").
{ok, _}
2> yalinka:size(R).
{ok,34244707}
On my local notebook it takes about 28 seconds to load 34 million points in 3d space. The beam process suddenly grows by 1.5 Gb in residential set memory =)
Since 'ekdtree' project already exists here on a github I choose 'yalinka' as a name for this project. Feel free to de-cypher it using 'yet another something' pattern, but actually 'yalinka' is a ukrainian word meaning 'christmas tree'. And now it is X-mas here in real world =)