我正在为外汇市场设计一个自动交易软件。 在 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 我想要(快速准确)的输入找到 5,000 个最接近的匹配项。

示例输入:

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

我认为这些指标中的每一个都可以被视为一个“维度”，并且我可以进行最近邻搜索以在这个多维空间中找到最近的数据点。

似乎最简单的方法是遍历每个数据点并测量到我的输入点的多维距离；但速度至关重要!

我读到有关用于此目的的称为 K-D 树 的东西。任何人都可以解释或向我提供一些解释如何在 MYSQL 中实现它的 Material 吗？

可能值得一提的是，我可以预处理表格，但输入是实时接收的。

目前我只是围绕每个维度上的数据独立地做一个粗略的集群:

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) 

如果我计算输入的百分位数并使用 that 而不是实际值进行最近邻搜索，我将有效地缩放各种指标，以便它们可以用作维度。

不过，我仍然不知道如何进行实际搜索。这甚至有可能在 MySQL 中高效地完成吗？

最佳答案

您应该能够执行如下查询:

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 值都是相同的。然后调整半径，直到尽可能接近所需的记录数。我建议 binary search .

我不确定你是否想打乱分布，但假设你这样做，你只需要给每个搜索值一个介于它在你的表中的两个值之间的排名(例如，如果排名5为5.5，排名6为5.9，搜索值为5.6，则搜索排名可能为5.5)

关于mysql - 在 MYSQL 中为 'nearest neighbor' 搜索实现 k-d 树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7005765/