https://en.wikipedia.org/wiki/BK-tree https://en.wikipedia.org/wiki/BK-tree A BK-tree is... specifically adapted to discrete metric spaces. There are others

https://en.wikipedia.org/wiki/BK-tree https://en.wikipedia.org/wiki/BK-tree A BK-tree is... specifically adapted to discrete metric spaces. There are others that have a similar principal for real valued metrics. • Ball Tree (also known as VP-Tree) (implemented in sklearn) • GH-Tree (rough description in this large PDF https://github.com/searchivarius/nmslib/raw/master/docs/manual.pdf https://github.com/searchivarius/nmslib/raw/master/docs/manu... ) • Multi-Vantage Point Tree As for the rationale, I think grouping them together is an efficient way to exploit the triangle inequality for each subtree.