4

We have a stream of points with about 1000 points per second. For each point, we have a complex vector (hundreds of dimensions). Our goal, for each point is to link it to the 5 closest points that we've already seen.

We determine "closest" by computing a distance (euclidian or other) between 2 points. Obviously, in a perfect world we would have enough money and time to compute the distance between a new point with each of the points we've already seen and it would keep the 5 closest. The world is not perfect and we're looking for a solution.

Has anyone worked with this before?

  • Interesting question. I think you need to give more information about your constraints. For example, you could only consider a window of the last n nodes you have seen but would this be good enough for you? So, again, have you defined any constraints that an approximate solution should satisfy? – Giorgio Jun 15 '13 at 16:56
  • Yes, windowing could be good enough, but of course, i'd rather avoid it, or rather, I'd rather not make the size of the window something too significant. Another factor on which I'm flexible is the "closest" term. We could accept a little nuance here where rather than the 5 closest points, we could have 5 close points among the closests. – Julien Genestoux Jun 15 '13 at 17:06
  • But how to avoid windowing? If you compare each new node with all the nodes you have already encountered you get a factorial increase of the number of comparisons. – Giorgio Jun 15 '13 at 17:08
  • Do you intend to store all the vectors seen? at 1000 points per second with x*100 dimensions, I'd wager you'll soon have much more troubling issues than this algorithm. If you don't keep them all, what's the selection strategy? – Frank Jun 15 '13 at 17:24
  • @Giorgio I don't know! Mayve there is a way to only keep some "relevant" points. That's why I'm asking the question! – Julien Genestoux Jun 15 '13 at 19:07
1

A good starting point may be a simplified version of iDistance. The full algorithm works by defining (central) cluster nodes, which are used to reduce the multiple dimensions to one. That one dimensional scalar is used to search a B+ tree. There are other algorithms like it, but they basically use the same approach. (Indexing High-Dimensional Data for Efficient In-Memory Similarity Search gives a nice overview of several algorithms and their performance.)

However, if we allow some approximations and discarding of nodes, then it may be enough to just have a tree of cluster nodes, perhaps a few layers deep. Search that tree for the nearest cluster node, and then search for the 5 nearest points attached to that node. All brute force calculations of the distance between points in N-dimensional space. Or however you want to optimize it.

Consider the following algorithm in pseudo code:

Cluster clusters[200];

FillRandom(clusters);

for (i = 0; i < 10000; ++i)
    Vector v = randomVector();

    cluster = clusters.findNearestCluster(v); // brute force search on distance squared

    PointArray points[] = cluster.sortPointsOnDistanceSquared(v);

    selectFirstFive(points);

Implemented in Java, 100 dimensions, each dimension between 0.0 and 10.0, runs in 5-8 seconds, on an Intel i7, second generation. Which means, well below the 1000/s stream speed. There is a lot of room for optimization. (I'd share the code, but really, it won't add anything.)

There is more than enough time to do something about rebalancing your cluster tree. Clusters that are in the middle of nowhere and get no hits can be removed. Clusters that have too many hits might be split or otherwise reduced. There should be some radius attached, some overlap tested, etcetera.

In this example code, these were some of the timings:

Minimum: 0, Maximum: 1067, #Clusters_having_points: 96, Average: 104, Time: 7498ms
Minimum: 0, Maximum: 1095, #Clusters_having_points: 97, Average: 103, Time: 7241ms
Minimum: 0, Maximum: 1010, #Clusters_having_points: 99, Average: 101, Time: 6465ms
Minimum: 0, Maximum:  832, #Clusters_having_points: 99, Average: 101, Time: 5688ms

With Min/Max/Avg the min/max/avg points per cluster node. It's programmed in no time, and easy to play around with, to get some picture of how the data handles itself.

The way I see it, most algorithms offer exactness, and keep all their data. They spent their time on the reduction of the N-dimensional point to one dimension. They need that one dimension, to use all kinds of balancing data structures, so they can sift through gazillions of data. By letting go of that exactness (and history), you free up time to use more mundane methods to balance your search tree. "Too many points for this cluster? Throw away half, as long as we can find 5 points that are (nearly) as close as any other we'd find." That's a bit crude, but you get the idea, I hope.

It's the same principle as used in games. If you can't do the real thing, fake it. It's okay as long as it looks good.

If that's not satisfactory, though, then you may go for the more exact algorithms that are known. Searching for some of them, as mentioned in the article I linked, will easily lead to interesting reading material, including algorithms.

0

To my knowledge, the best software for doing this sort of processing is Apache Mahout. There are algorithms that are more efficient than a linear search, but generally only for lower dimensions. Fortunately (although not for your pocketbook), it's highly parallelizable, so you can always throw more hardware at the problem.

To improve latency on a live stream, you might consider preprocessing some historical data to get a feel for a typical distance between closest nodes, then use that distance as a heuristic. Instead of the absolute five closest, you can pick the first five that are within, say, 5x of the typical distance. You can increase or decrease that margin as processing power permits.

Another potentially useful heuristic is that once you identify one relatively close point, its previously identified nearest neighbors are good candidates for your new point, and you can branch out from there, rather than picking candidates at random.

For example, if 95% of the nearest neighbors have a distance of 10 or less, first do a linear search to find any point within 50, then look at that point's nearest neighbors, then the closest of the neighbor's neighbors, and so on.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.