使用什么算法从高维数据点中过滤出来

Question

我在服务器的MySQL数据库中存储了4维数据点。一个时间维度数据与三个空间GPS数据(lat，lon，alt(。GPS数据是为成千上万的用户按1分钟的时间间隔采样的，并且正在全天候添加到我的服务器中。

示例REST/post-json看起来像

{
"id": "1005",
"location": {
"lat":-87.8788,
"lon":37.909090,
"alt":0.0,
},
"datetime": 11882784
}

现在，我需要过滤掉在给定时间段内其位置与给定userID相距k米以内的所有候选者(userID(。

用于过滤的示例REST/get查询参数如

{
"id": "1001",      // user for whose we need to filter out candidates IDs
"maxDistance":3,   // max distance in meter to consider (euclidian distance from users location to candidates location)
"maxDuration":14   // duration offset (in days) from current datetime to consider
}

正如我们所看到的，每分钟在我的数据库中插入数千个条目，这导致了大量的总条目。因此，为了迭代所有的过滤条目，我担心琐碎而天真的方法对于我当前的需求来说是不可行的。那么，我应该在服务器中实现什么算法呢？我尝试过实现幼稚的算法，比如

params ($uid, $mDis, $mDay)
1.     Init $candidates = []
2.     For all the locations $Li of user with $uid
3.         For all locations $Di in database within $mDay
4.             $dif = EuclidianDis($Li, $Di)
5.             If $dif < $mDis
6.                 $candidates += userId for $Di
7.     Return $candidates

然而，这种方法在实践中非常缓慢。预计算可能不可行，因为它为所有userIDs花费了巨大的空间。还有什么算法可以提高效率

Answer 1

您可以实现一种空间哈希算法，以便在给定的区域/时间内高效地查询数据库中的候选人。

将三维空间划分为宽度为k的立方体三维网格，在将数据点插入数据库时，计算该点位于哪个立方体中，并根据立方体坐标计算哈希值。

当查询另一个数据点d的k内的所有数据点时，计算d所在的立方体，并找到8个相邻的立方体(每个维度中+/-1(。计算9个多维数据集的哈希值，并在给定的时间段内查询数据库中具有这些哈希值的所有条目。你将有一个小的候选集，然后你可以从中迭代，找到d的k中的所有数据点。

如果你的k值可以在2-5米之间，那么给你的立方体一个5的宽度。

时间戳可以存储为一个单独的字段，或者您可以将多维数据集设为4维，并在哈希中包含时间戳，然后搜索27个多维数据集而不是9个。