4

I am looking at a large scale low latency way to calculate the geometric distance between vectors.

Let's say I have a vector A. It has size 128 and of type 32 bit float. I want to get it's geometric distance from about 10milion other vectors of the same type. So basically how far is A from all the other vectors. The result should also be returned in a sorted order. ( Edit, The result should return top N vector id's to the client )

This operation is tied into the UX of a website and needs to be low latency and will be called at least a couple of times per client session.

With 2-dimensional vectors, GeoIndexing can be used. But I have not found an indexing solution for higher dimensions.

Which approach/technology would be a good fit to solve this problem?

8
  • 10 million numbers to be returned to the UI of a client web site? Really? Sure you do not need only "top hundred nearest" (or farthest) first? Indexing won't help you if you do not restrict the query result in some way.
    – Doc Brown
    Commented Apr 26, 2016 at 10:39
  • Oh yeah, I left that out. Top N is only required. In the range of 10-100 ids. Commented Apr 26, 2016 at 10:47
  • 3
    I guess, k-d trees is what you are looking for, see en.wikipedia.org/wiki/K-d_tree. The article scetches nearest neighbour search and "k nearest neighbour search" as well.
    – Doc Brown
    Commented Apr 26, 2016 at 11:19
  • I looked at KD-trees. Sounds like the best solution in theory. It says however that you need the number of points n to be bigger than (2 ^ dimensions) for the K nearest neighbour search to perform better than the linear case. Not sure if I interpreted this right but that would require 2 ^ 128 data points, which is enormous. Commented Apr 28, 2016 at 5:51
  • From the Wikiepdia article: "when the number of points is only slightly higher than the number of dimensions, the algorithm is only slightly better than a linear search of all of the points"
    – Doc Brown
    Commented Apr 28, 2016 at 20:13

1 Answer 1

1

I built similar functionality for a web site. In my case I had less dimensions than you, but I had 15 million records (similar to your case). I needed to serve about 5000 requests per second which meant that each request has a budget of about 10ms on a 64-core server.

I tried various approaches including k-d tree and after bench marking each approach ended up with the one described below, which was well within my 10ms budget when written in C# and running on .Net 4.0.

The algorithm is is easier to draw than write, so I hope you can follow my explanation. Lets think about it in 2 dimensions first (it's easier to visualize) then extend it to more dimensions after.

Imagine you have a set of 10 million points with x and y coordinates in a 2D space. Loop through all the points and find the minimum and maximum values of x and y, and also the value of x and y where half of the points are above and half of the points are below this value. This gives you a rectangular space divided into four quadrants where each quadrant contains the same number of points.

Repeat this in each of the four quadrants breaking them into four quadrants and repeat recursively until the quadrants contain a number of points similar to the N in your Top-N. As you do this make sure each point knows which rectangle it is inside of, and the rectangles know the nesting structure of rectangles within rectangles.

Building this index takes a while but you only have to completely rebuild it once in a while (maybe once a day). Throughout the day as the data changes you can move points from one rectangle to another. As you move points around the index becomes unbalanced and less efficient, so you do have to rebuild from scratch every so often.

When you want to find the N nearest neighbors, you only need to consider the adjacent rectangles. Lets say you are looking for the 10 nearest neighbors, then the index will continue splitting rectangles into 4 quadrants until each rectangle contains about 10 points. Now the 10 nearest points must be in the same rectangle or one of the adjacent rectangles. You can find the adjacent rectangles by going up the rectangle tree and down to it's children. If you are at a boundary you might have to go up a few levels and back down the same number of levels, but you can pre-compute the list of adjacent rectangles for each rectangle to make it faster (but use more memory). Note that most rectangles are in the middle somewhere and will have 8 adjacent rectangles. Rectangles on the edge of the coordinate space will have less.

To extend this from 2D to 3D, the whole space is now a cube instead of a rectangle and you divide each cube into 8 smaller cubes each containing the same number of points rather than dividing rectangles into 4 smaller rectangles, and each cube will have up to 26 adjacent cubes.

This can be logically extended to more dimensions. In my application I had 4 (latitude, longitude and 2 others). In your case the numbers get pretty big so you are going to need lots of memory! I didn't do the math, but to split each 128-dimensional region in half on each dimension might result in 2^128 child regions - which is clearly not feasible. If this is the case I think you will need to experiment with variations on this approach, but hopefully this will give you a starting point.

Note that this algorithm is imperfect by design. The imperfections didn't matter to my application and speed was much more important. The imperfection come from the fact that rectangles are sub-divided by number of points not by size, so the adjacent rectangles are not lined up with this rectangle. This doesn't matter too much because you must still compute the actual distance from the target point to all of its neighboring rectangles and take the closest N, and also you know that even if the adjacent rectangle is not exactly lined up with this one there are no other rectangles that are closer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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