These data structures are well-suited for range query problems asking for every point
If there is no structure to the similarity measure then a brute force search requiring the comparison of the query image to every image in the dataset is the best that can be done [citation needed].
If, however, the similarity function satisfies the triangle inequality then it is possible to use the result of each comparison to prune the set of candidates to be examined.
[2] Other researchers were working independently on similar data structures.
In particular, Peter Yianilos claimed to have independently discovered the same method, which he called a vantage point tree (VP-tree).
[3] The research on metric tree data structures blossomed in the late 1990s and included an examination by Google co-founder Sergey Brin of their use for very large databases.