VP trees are interesting (previously discussed here: https://news.ycombinator.com/item?id=3304685 https://news.ycombinator.com/item?id=3304685), and there is al

VP trees are interesting (previously discussed here: https://news.ycombinator.com/item?id=3304685 https://news.ycombinator.com/item?id=3304685), and there is also the MVP variant (multi vantage point trees -- https://en.wikipedia.org/wiki/MVP_tree https://en.wikipedia.org/wiki/MVP_tree): Indexing Large Metric Spaces For Similarity Search Queries http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.43.7492&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.43....