Внедрение k-d дерева для поиска «ближайшего соседа» в MYSQL?

Я разрабатываю программное обеспечение для автоматической торговли на валютном рынке. В базе данных MYSQL у меня есть годовые рыночные данные с пятиминутными интервалами. У меня есть 4 разных метрики для этих данных, помимо цены и времени.

[Time|Price|M1|M2|M3|M4] 
x ~400,0000

Time - это первичный ключ, а с M1 по M4 - разные показатели (например, стандартное отклонение или наклон скользящей средней).

Вот реальный пример (отрывок :)

+------------+--------+-----------+--------+-----------+-----------+
|  Time      | Price  |     M1    |   M2   |    M3     |     M4    |
+------------+--------+-----------+--------+-----------+-----------+
| 1105410300 | 1.3101 |   12.9132 | 0.4647 |   29.6703 |        50 |
| 1105410600 | 1.3103 |    14.056 | 0.5305 | 29.230801 |        50 |
| 1105410900 | 1.3105 |   15.3613 | 0.5722 |   26.8132 |        25 |
| 1105411200 | 1.3106 | 16.627501 | 0.4433 | 24.395599 |  26.47059 |
| 1105411500 | 1.3112 |   18.7843 | 1.0019 | 24.505501 |    34.375 |
| 1105411800 | 1.3111 |   19.8375 | 0.5626 |        20 |   32.8125 |
| 1105412100 | 1.3105 |   20.0168 | 0.6718 |    9.7802 |   23.4375 |
| 1105412400 | 1.3105 |   20.4538 | 0.8943 |     7.033 |   23.4375 |
| 1105412700 | 1.3109 |   21.6078 | 0.4902 |   11.7582 |   29.6875 |
| 1105413000 | 1.3104 |   21.2045 |  1.565 |    8.6813 |    21.875 |
+------------+--------+-----------+--------+-----------+-----------+...400k more

Учитывая ввод M1, M2, M3 и M4, я хочу (быстро и точно) найти 5000 ближайших совпадений.

Пример ввода:

+------------+--------+-----------+--------+-----------+-----------+
|  Time      | Price  |     M1    |   M2   |    M3     |     M4    |
+------------+--------+-----------+--------+-----------+-----------+
| 1205413000 | 1.4212 |   20.1045 | 1.0012 |    9.1013 |    11.575 |
+------------+--------+-----------+--------+-----------+-----------+

Я решил, что каждую из этих метрик можно рассматривать как «измерение», и что я могу сделать nearest neighbor search, чтобы определить местонахождение ближайших точек данных в этом многомерном пространстве.

Кажется, самый простой способ сделать это - перебрать каждую отдельную точку данных и измерить многомерное расстояние до моей входной точки; но скорость имеет значение!

Я читал о чем-то под названием K-D Trees, используемом для этой цели. Может ли кто-нибудь объяснить или предоставить мне некоторый материал, объясняющий, как реализовать это в MYSQL?

Возможно, уместно упомянуть, что я могу предварительно обработать таблицу, но входные данные принимаются в режиме реального времени.

В настоящее время я просто создаю приблизительный кластер вокруг данных по каждому измерению независимо:

INSERT INTO Dim1 SELECT * FROM myTable AS myTable USE INDEX(M1) WHERE myTable.M1 < currentM1 ORDER BY M1 DESC LIMIT 2500;
INSERT INTO Dim1 SELECT * FROM myTable AS myTable USE INDEX(M1) WHERE myTable.M1 > currentM1 ORDER BY M1  ASC LIMIT 2500;

INSERT INTO Dim2 SELECT * FROM myTable AS myTable USE INDEX(M2) WHERE myTable.M2 < currentM2 ORDER BY M2 DESC LIMIT 2500;
INSERT INTO Dim2 SELECT * FROM myTable AS myTable USE INDEX(M2) WHERE myTable.M2 > currentM2 ORDER BY M2  ASC LIMIT 2500;

INSERT INTO Dim3 SELECT * FROM myTable AS myTable USE INDEX(M3) WHERE myTable.M3 < currentM3 ORDER BY M3 DESC LIMIT 2500;
INSERT INTO Dim3 SELECT * FROM myTable AS myTable USE INDEX(M3) WHERE myTable.M3 > currentM3 ORDER BY M3  ASC LIMIT 2500;

INSERT INTO Dim4 SELECT * FROM myTable AS myTable USE INDEX(M4) WHERE myTable.M4 < currentM4 ORDER BY M4 DESC LIMIT 2500;
INSERT INTO Dim4 SELECT * FROM myTable AS myTable USE INDEX(M4) WHERE myTable.M4 > currentM4 ORDER BY M4  ASC LIMIT 2500;

Важно понимать, что меня интересует расстояние по рангу, а не по ценности.

Изменить: я немного ближе к пониманию того, как это сделать (я думаю): мне нужно предварительно обработать каждую строку каждой метрики и присвоить ей percentile, которая будет представлять ее местоположение (в процентах ) в своем диапазоне.

Например, для любого заданного значения M1:

percentile = (#  rows with values less than input)/(# total rows) 

Если я вычисляю процентиль входных данных и использую это для поиска ближайшего соседа вместо фактического значения, я эффективно масштабирую различные метрики, чтобы их можно было использовать в качестве измерений.

Однако я все еще не знаю, как вести настоящий поиск. Возможно ли это даже эффективно выполнить в MySQL?