unixjunkie / bisec-tree

Bisector tree implementation in OCaml

bisec-tree

Bisector tree implementation in OCaml.

A bisector tree allows to do fast and exact nearest neighbor searches in any space provided that you have a metric (function) to measure the distance between any two points in that space.

Cf. this article for details: "A Data Structure and an Algorithm for the Nearest Point Problem"; Iraj Kalaranti and Gerard McDonald. ieeexplore.ieee.org/iel5/32/35936/01703102.pdf

Figure: the Stanford bunny, consisting of 35947 3D points, guillotined by the first layer of a bisector tree.

bisec-tree's Issues

add length

without creating a potentially huge tmp list

provide some kind of 'progress bar'

upon construction of a large tree, users have a right to some feedback

add point set summarization function(s)

• hierarchical; using the K parameter (max bucket size)
• iterative simplification (more compute intensive but maybe higher quality)

to_dot

output in graphviz format

test k=0

doesn't compile with < 4.02.0

because not Array.for_all

add parallel construction

very easy if nprocs is a power of two

add method

to "grow" an existing tree with more points

send package in opam

once I have a stable version released

add function to brute force test the distance function

To try finding a counter example to the triangular inequality when you have doubts about the distance function

new major version

tag and push in opam once tests are OK

partition

like neighbors, but will also keep the non matching points

implement Two_bands_bootstrap heuristic

take a random partition (bootstrap) of all points instead of all points when doing two bands (when too many points to index)

add an any_neighbors query

boolean answer: yes/no your query point has neighbors in the tree at given distance;
i.e. the range query, but we don't care about the list of neighbors.
Such queries should terminate faster than the range query.

add interface file

corner case

P.dist vp1 vp2 = 0.0
then all remaining points must be put into the same bucket; this bucket might have a size > k

Pre_node is used too often

in one_band and two_bands.
This is a performance bug since the two VPs are random in that case.
We should use a bucket

simplify code in neighbors fun

the code can be simpler:

• should we include all points below
• else should we include nothing
• else inspect vp + points below

store distance between vps in a node

cut the number of distance computation upon searching into the bst

remove Config module parameter of the functor

This is just too annoying for users of the library.
Pass explicitly the heuristic and the bucket size when needed instead.

write a distributed version of the create function

use zmq for paral/dist

incremental build

algorithm:

• build tree for a smallish random partition
• address in parallel all remaining molecules
• emboss the small tree
• Eventually, continue building the tree for each group of molecules that obtained the same address

graphical output of the BST

for a 2D point set

buckets on disk

now this makes a lot of sense with the add method having been added (to grow an existing tree)

add a version parameterized by a functor with a distance bound

With the regulat functor: only exact distances are used.
If the user knows a cheap to compute upper bound, we could exploit that
one as often as possible.

Inspired by:

Swamidass, S. J., & Baldi, P. (2007). Bounds and algorithms for fast exact searches of chemical fingerprints in linear and sublinear time. Journal of chemical information and modeling, 47(2), 302-317.

test application

this could create the cool plot of points also

store buckets on disk

make another implementation, where only the index will be in memory, actual bucket
content's is in a persistent hash table on disk.
maybe just change the bucket type as a start, then add another config option (storage = Volatile | Persistent).

make the parallel version output/store molecule adresses

instead of marshalling sub trees.
Might scale better.

performance bug in neighbors

cf. code in vpt

get_addr method

a function to sample the distribution of distances in a point set

might be useful

diameter of a point set

implement this instead of using heuristics

Wording...

I'm a little puzzled by the wording in the README:

A bisector tree allows to do fast but exact nearest neighbor

isn't 'exact nearest neighbor' what we want, so it'd be better to say:

A bisector tree allows to do fast and exact nearest neighbor

or, and I've only read the abstract so it isn't clear but is it actual an inexact nearest neighbor?

if needed, use parallelization to accelerate stuffs

rm par_create?

since parallelization is poor

on-line algorithm

• randomize points
• two_band with given sample size
• address all remaining points in //
• add points to the tree
• recurse on remaining buckets

inspect function

like check but print problems and their address