Quick search the most similar objects in the n-dimensional space

Question

Lets assume that we have a points in the n-dimensional space. So we have a n coords(n columns) which can describe location of the each point.

We need to implement a table which can be used for a quick searching the most similar points, i.e. points which have the smallest distance to the desired point.

E.g. points in the db:

id  c1  c2  c3  c4  c5
1   5   19  42  12  16
2   3   23  38  15  12
3   14  21  32  33  1
4   12  29  21  24  5

If we want to find the best matching for point with coords:

c1 c2  c3  c4  c5
4  20  40  14  15

We will get points with id 1 and 2.

We also have mean coordinate for each dimension(column) and vector for each point in which first element - number of the dimension in which point has the largest difference from the mean coordinate in this dimension, and last - number of the dimension in which point has the smallest difference. Maybe it can be used for the more rapid filtering points which have the biggest distance to the desired point.

So how can I do something like this using MySQL?

I think the composite index and order by abs(cx - $mycx) can be a good solution, but I can't use it because I will have more then 16 columns which I need to include in the one index.

Any help will be very useful!

Answer 1

PostgreSQL using cube

Using PostgreSQL this becomes pretty easy with the cube extension which I explained on your other question.. Sample data.

CREATE TABLE foo AS
SELECT *
FROM ( VALUES
  (1, cube(ARRAY[5 , 19, 42, 12, 16]) ),
  (2, cube(ARRAY[3 , 23, 38, 15, 12]) ),
  (3, cube(ARRAY[14, 21, 32, 33, 1 ]) ),
  (4, cube(ARRAY[12, 29, 21, 24, 5 ]) )
) AS t(id, c);

Finding distance...

SELECT
  id,
  c,
  c2,
  cube_distance(c,c2),
  rank() OVER (ORDER BY cube_distance(c,c2))
FROM foo
CROSS JOIN ( SELECT cube(ARRAY[4,20,40,14,15]) )
  AS t(c2)
ORDER BY cube_distance(c, c2);

Outputs.

 id |          c          |         c2          |  cube_distance   | rank 
----+---------------------+---------------------+------------------+------
  1 | (5, 19, 42, 12, 16) | (4, 20, 40, 14, 15) |  3.3166247903554 |    1
  2 | (3, 23, 38, 15, 12) | (4, 20, 40, 14, 15) | 4.89897948556636 |    2
  4 | (12, 29, 21, 24, 5) | (4, 20, 40, 14, 15) | 26.5706605111728 |    3
  3 | (14, 21, 32, 33, 1) | (4, 20, 40, 14, 15) | 26.8700576850888 |    4

Answer 2

Plan A: (In the absence of further info, I prefer this solution.)

ORDER BY 
    ABS(c1 - $c1) +
    ABS(c2 - $c2) +
    ABS(c3 - $c3) +
    ABS(c4 - $c4) +
    ABS(c5 - $c5)  ASC

Or "root mean square" (without the unnecessary SQRT):

ORDER BY 
    (c1 - $c1) * (c1 - $c1) +
    (c2 - $c2) * (c2 - $c2) +
    ...  ASC

For finding the 'closest' item to a single query ($c1, $c2, ...), that takes a single pass over the data. If the data is huge, it will be I/O-bound, so disk speed becomes the ruling constraint. The squares will be only trivially slower than ABS(), so pick the metric you prefer. (Note: Using POW(, 2) might be noticeable slower.)

No index is of any use in this query.

You could add LIMIT 10 to get the 10 "closest". If you want to find all of those with exactly the same metric (and closest), the code becomes a lot messier and slower.

Plan B: If the numbers "work right", it may be possible to use an index on one column. In doing so, you would first find rows that are "close" to the value in that column. (This list should not exceed 10% of the table.) Then use the above code to laboriously go through that subset of rows. The risk is that the other columns may be very close, while this column is too far to be filtered by the first pass.

Plan C is useful for finding the nearest pizza parlors, but it does not extend beyond 2 dimensions.