3

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!

  • Mathematically, the (Euclidean) distance would actually be calculated as SQRT((c1-$myc1)^2 + (c2-$myc2)^2 + …). – Andriy M Dec 20 '16 at 13:59
  • @AndriyM I know but it will take a lot of time for big dataset, and we don't need so high accuracy – don-prog Dec 20 '16 at 14:33
  • See also stackoverflow.com/questions/41245001/… – Rick James Dec 21 '16 at 17:22
3

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
1

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.

  • Thanks for the answer! About plan A: if we will have big dataset I think search will take a lot of time. So it's main big problem, maybe a KD-tree can be a good solution? – don-prog Dec 21 '16 at 5:41
  • Or maybe an R-Tree? – Rick James Dec 21 '16 at 7:11
  • [1 part] I still can't find the answer. Unfortunately, KD-tree is not a good solution for a data with a many dimensions(I will have more than 120 dimensions), maybe I can use something like your solution but improve it using preliminary sorting? Every record has dimension with the biggest diference from the mean coordinate of this dimension(I have described it better in the question). So we can filter 50% the most closest records by the coord with the biggest difference, then filter 50% from previous query by the coord with the the second largest difference and so on. – don-prog Dec 28 '16 at 19:30
  • [2 part] Also please check this question which describe current question better. – don-prog Dec 28 '16 at 19:31
  • 50%, etc -- Aren't you are still stuck with touching every row in the dataset? I assume this is the main performance issue. (Computations are a lot cheaper than fetching rows.) – Rick James Dec 28 '16 at 20:43

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.