I feel like the poster-child for the frequency illusion. There was an article on 538 a few weeks ago that caught my interest which used cosine similarity (a non-metric distance function). I dove in, and started wondering if there were any ways to find nearest neighbors using cosine similarity efficiently. A week later, Facebook's Faiss implements something of a general purpose toolkit for indexing metric and not metric spaces to minimize storage. And now this. It's like the world is trying to tell me something!
[0] http://scikit-learn.org/stable/modules/neighbors.html#k-d-tr...
EDIT: Deleted calculation about approximating arccos(z) <= arccos(x) + arccos(y) by cos(arccos(z)) <= cos(arccos(x) + arccos(y)) <= xy - (1-x^2)(1-y^2), completely disregarding that cos is a decreasing function in the relevant interval.
Interesting tid-bit, one Mr. Sergey Brin published this in 1995
"Near Neighbor Search in Large Metric Spaces"
http://www.vldb.org/conf/1995/P574.PDF
So I'm curious, because I had been planning on using a VP tree for something I'm mulling over. I could see stormy waters though for large dimensions.
Seriously interested to hear any feedback from people who have tried it. Any recommendations for what to do instead?
(AFAICT: Most of these trees have a "typical" case search time of some root of N based on dimensionality. The easiest way to visualize this is to consider a walk from the perimeter to a cell in Voroni space, and how many cells that will search.)
Metric-based data structures face the peculiar problem that the identity of each data point itself is not an actual "key", in the way that a data point in a hash-table or binary tree is a key. Rather, each data point in a metric tree is only "indexed" with relation to it's distance from all other keys. This makes it hard to get easily measured performance guarantees.