Placing elements in graph with a streaming/online algorthm

Question

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?

Answer 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.

Answer 2

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.