# Approximate Nearest Neighbor Search - Week 11

Last week, I have implemented generalized Spill Trees, to consider general splitting hyperplanes, not necessarily axis-orthogonal.

I added a new template parameter for Spill Trees: `HyperplaneType`

, and I implemented two candidate classes: `AxisOrthogonalHyperplane`

and `Hyperplane`

.

(+) `AxisOrthogonalHyperplane`

: consider an axis-parallel projection vector. So, we can project any vector in O(1) time, considering the appropiate dimension.

(+) `Hyperplane`

consider a general projection vector. So we can project any vector in O(d) time, through a dot product.

Inside Spill Tree, I consider `BallBound`

for non-axis-orthogonal hyperplanes, and `HrectBound`

for axis-orthogonal hyperplanes.

Considering this abstraction, I managed to significantly simplify the Split methods: `MeanSplit`

and `MidpointSplit`

. Now, they share most of the code.

By default, `SpillSearch`

considers `AxisOrthogonalHyperplanes`

because they seem to be faster in many cases, but this is not always true. We have to benchmark both methods and see which is faster and which is more accurate, I mean, which has the best relation between running time and relative approximation error.

All of this changes were included in the pull request: [1].

I plan to work next days in these topics:

+) Add many test cases for all the code developed: `SpillTree`

class, `SpillSearch`

class, `Hyperplane`

class, etc.

+) AppVeyor has shown some problems with the MSVC compiler, in the resolution of template parameters of alias templates, similar to an old issue: [2]. I have to fix it, probably including some extra definitions.

+) Check details in the Spill Tree's implementation.

Follow the progress in: [3].