Какой алгоритм используется, чтобы отфильтровать от точек данных более высокого измерения? - PullRequest
Новая
       23

Какой алгоритм используется, чтобы отфильтровать от точек данных более высокого измерения?

2 голосов
/ 04 апреля 2020

У меня есть 4-мерные точки данных, хранящиеся в моей базе данных MySQL на сервере. Данные одного временного измерения с тремя пространственными данными GPS (широта, долгота, альт). Данные GPS сэмплируются по 1 минуте для тысяч пользователей и добавляются на мой сервер 24x7.

Пример 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

Однако на практике этот подход очень медленный. И предварительный расчет может оказаться невозможным, поскольку он требует огромного пространства для всех userID с. Какой еще алгоритм может повысить эффективность?

1 Ответ

1 голос
/ 05 апреля 2020

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

Разделите трехмерное пространство на трехмерную сетку кубов с шириной k, и при вставке точки данных в базу данных вычислите, в каком кубе находится точка, и вычислите значение ha sh на основе координат куба.

При запросе всех точек данных в пределах k от другой datapoint d, вычислите куб, в котором d сидит, и найдите 8 смежных кубов (+/- 1 в каждом измерении). Вычислите значения ha sh для 9 кубов и запросите в вашей базе данных все записи с этими значениями ha sh за указанный период времени. У вас будет небольшой набор кандидатов, из которого вы сможете затем выполнить итерацию, чтобы найти все точки данных в пределах k от d.

Если ваше значение k может находиться в диапазоне 2-5 метров, дайте кубам ширину 5 *. 1009 *

Отметки времени могут храниться в виде отдельного поля, или же вы можете сделать ваши кубы четырехмерными и включить отметку времени в га sh и искать 27 кубов вместо 9.

...