3 ms·
The article explains why the search algorithm is valid. But it doesn't explain why the tree should be built up in the way described. Is there some rationale?
by adrianratnapala 10y ago
The article explains why the search algorithm is valid. But it doesn't explain why the tree should be built up in the way described.
Is there some rationale? And can it be extended to non-integer metrics?
- mshenfield 10y agohttps://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.