Реализация дерева k-d для поиска «ближайшего соседа» в MYSQL? - PullRequest
Новая
       32

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

4 голосов
/ 10 августа 2011

Я занимаюсь разработкой программного обеспечения для автоматической торговли на валютном рынке. В базе данных 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?

1 Ответ

0 голосов
/ 11 августа 2011

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

SELECT * FROM myTable
WHERE M1 BETWEEN searchM1 - radiusM1 AND searchM1 + radiusM1
  AND M2 BETWEEN searchM2 - radiusM2 AND searchM2 + radiusM2
  AND M3 BETWEEN searchM3 - radiusM3 AND searchM3 + radiusM3
  AND M4 BETWEEN searchM4 - radiusM4 AND searchM4 + radiusM4

В случае сферы все значения radius, конечно, будут одинаковыми.Затем вы настраиваете радиус, пока не достигнете максимально возможного количества записей.Я бы предложил бинарный поиск .

Я не уверен, хотите ли вы возиться с дистрибутивом или нет, но, если вы это сделаете, вам просто нужно дать каждое значение поискаранг между двумя значениями, между которыми он попадет в вашу таблицу (например, если ранг 5 равен 5,5, ранг 6 равен 5,9 и значение поиска 5,6, тогда ранг поиска может быть 5,5)

...