Seriously geeky: searching in metric spaces

[ciphergoth]

It's easy to see how to organise a database if you want to be able to, say, find all the people in it whose names are between "Charybdis" and "Scylla" in alphabetical order. But how would you organise it if you want to find all the people whose pictures look most like a particular sample picture, when all you have is a tool that measures how similar two pictures are? There's a family of very general approaches to the problem called "metric space searches"; in this approach, we don't need to know anything about what we're storing except that we can measure the distance between two items and get a sensible answer.

I thought I'd invented a smashing new algorithm for searching in metric spaces. But I'm having a hard time finding out if it's any good.

Searching in Metric Spaces (1999) provides an overview of the state of the art as of five years ago.

The usual assumption when designing these algorithms is that the distance measurement function is very expensive, and so the first order of business is to minimise the number of distance measurements. I implemented my algorithm and got very good results on random points in a cube. But when I tried a harder data set - random lines from "A Tale of Two Cities" with string edit distance as the metric, a standard test used in Brin's tests on his GNAT algorithm - I found it would compare the target string to over half the strings in the database before returning an answer.

So I tried implementing one of the standard algorithms from the paper - AESA, a simple one that's supposed to be very good at minimising distance measurements at search time, at the cost of very high startup time and storage - and that doesn't do much better!

Results using Hamming distance between random binary strings are even worse - AESA averages 882.4 measurements in a dataset of 1000 items, while my algorithm averages 999.3...

How am I supposed to assess my algorithm if I can't find an interesting test case on which any algorithm performs even vaguely OK? Random points in a cube is not a good test, because there are already much better algorithms for the special case of vector spaces...

Comments

[babysimon]

I read some of the paper and now my head is hurting.

I guess what you've discovered is that all the existing algorithms suck. I think this is probably why Google Image search doesn't have a "Find images similar to this one..." function.

From my brief read of AESA, I really don't see how it's supposed to be O(1) at all. It looks to me like its performance is heavily dependent on the value of r used - smaller r should eliminate many more elements of U on each iteration. What r are you using?

I'd be interested to hear what your algorithm is.

[ciphergoth.livejournal.com]

I'm doing a "Nearest neighbour" search, so r starts at infinity and gets smaller as I go along. I suppose I should re-do the earlier tests to reject more points every time r gets smaller - only just thought of that.

By O(1) they mean about O(1) distance measurements - it's at least O(n) overall work, and that's not counting the O(n^2) initialisation and storage requirements.

My algorithm is a variant of GHT. The big ideas are
(*) at each node in the tree, you use one old point (one you already know the distance to) and one new point to decide the dividing line between the two subtrees. But you can use any old node, not just one from the parent; you choose the one that gives you the biggest range in distances from the points in the subtree, then use the point furthest from that as the new node

(*) at each node in the tree, you record the range of distances for points contained in the node from *all* points already considered, to maximise the chances you'll be able to prune that branch

(*) instead of hyperplanes as the dividing line, you use hyperhyperbolae, in order to exactly divide the points remaining into two. IE your test is not d[1] - d[0] < 0 but d[1] - d[0] < node.bias. This turned out to make a substantial positive difference

(*) I'm considering beefing up the pruning some more by adding hyperhyperbola-based pruning: ie the range of values of d_a - d_b for every point in the node and for all d_a and d_b considered so far.

Er, that was all clear as mud wasn't it. OK, here's another way to put it. The function that constructs the node takes two arguments: a set of points to put in the node, and a set of "comparator points". When the search method on the node is called, it will be passed the target point, the range r, and the distance of the target point from each of the comparator points. It'll use all these distances to try and "early reject". Then failing that, it'll add a new comparator point to the set, measure the distance from the target to the new point, and use this new point along with an existing point to define a hyperbolic dividing plane. It decides which side of the plane the target point is on, searches the subtree corresponding to that side first, and then tries the other subtree unless it can demonstrate that nothing on the other side can be close enough.

Er, slightly clearer mud?

[babysimon]

By O(1) they mean about O(1) distance measurements

I still don't get it. AESA repeatedly measures distance between the pivot and the query node, rejecting a proportion of the data set each time. Not a constant proportion, so we can't be exact, but that sounds more like O(log n) to me. What am I missing?

Must read up on GHT before peering into your mud. Actually fuck that; must have bath, sort costume, talk to lovers etc...

[ciphergoth.livejournal.com]

I would have thought it would be log(n) as well, but they say O(1) was determined experimentally - *shrug*...

[eqe.livejournal.com]

It's nonsense to determine O experimentally -- it's too easy for a constant or linear term to dominate a log term over all testable values. For example, you can sort integers in O(n) if you assume that there's an upper bound (for example, 64-bit integers). I had a bit of a red face while trying to convince a Cray programmer that sorting was inherently O(n log n) -- he just kept pointing at his sort function which obviously had O(n) performance. And of course, he's right -- he can sort any useful set of integers in O(n) time. Doesn't change the fact that sorting is, mathematically, O(n log n).

"In theory, there's no difference between theory and practice."

[ciphergoth.livejournal.com]

For the reasons pavlos outlines, the purely theoretical worst-case analysis always yields meaningless results, so you have to rely to some extent on experiment.

I don't suppose it can be O(1), but if it's, say, O(log log n) then it would be very hard to determine that by experiment, so they're doing the right thing by reporting what they observe as best they can. And it's a survey paper so there's a limit on how much detail they can go into.