Rangesearch-box is an algorithm performing range search queries.
Not pretending to be optimal or more flexible than other solutions,
but rather an experiment of a non tree based rangesearch algorithm.
The overall idea is to sort the points according to each dimension and index them.
We can then apply some efficient search algorithm in the sorted arrays (one per dimensions).
The intersection of indexes on each dimension will finally provide the boxes.
We successfully created a rangesearch algorithm which does not rely on tree data structure.
The big drawback of this approach is the constraints on the boxes shape.
However the performances of this approach are quite good for a python/numpy implementation.
Faster than sklearn Balltree (in cython) with a python metric (which is a bottle neck) by a factor ~ x25.
More details in the demo notebook.
We can also note that is scales properly with the number of dimensions (perf-wise)
It was a funny experiment =)
Could be interesting to implement in cython.