Как бы вы решили эту проблему с GPS / местоположением и масштабировали ее? Вы бы использовали базу данных? R-дерево?

Question

Предположим, у меня есть люди и их координаты GPS:

User1, 52.99, -41.0
User2, 91.44, -21.4
User3, 5.12, 24.5
...

Моя цель: Учитывая набор координат,

1. Из всех этих пользователей найдите в пределах 20 метров. (как сделать оператор SELECT следующим образом?)
2. Для каждого из этих пользователей определите расстояние.

Как вы, наверное, догадались, эти координаты будут получены с мобильного телефона. Телефоны будут обновлять свою долготу / широту каждые 10 секунд, а также получать список пользователей <20 метров. Это динамично. </p>

Я бы хотел, чтобы это было наилучшим образом, чтобы оно могло масштабироваться.

• Будете ли вы хранить координаты в базе данных и обновлять их каждые 10 секунд? (Если вы храните его в базе данных ... как бы вы рассчитали это ...)
• Как бы вы сделали это, чтобы он мог масштабироваться?

Кстати, уже есть формула, которая может вычислить расстояние между двумя координатами http://www.johndcook.com/python_longitude_latitude.html. Мне просто нужно знать, как лучше это сделать технически (Деревья, База данных? Какая архитектура? Более конкретно ... как бы вы связали формулу длинного / латового расстояния с оператором "SELECT"?)

Answer 1

1. Создание таблицы MyISAM со столбцом типа данных Point

2. Создать индекс SPATIAL для этого столбца

3. Преобразование GPS координат в UTM (сетка) координат и сохранение их в вашей таблице

4. Выполнить этот запрос:

   SELECT  user_id, GLength(LineString(user_point, @mypoint))
   FROM    users
   WHERE   MBRWithin(user_point, LineString(Point(X(@mypoint) - 20, Y(@mypoint - 20)), Point(X(@mypoint) + 20, Y(@mypoint + 20))
           AND GLength(LineString(user_point, @mypoint)) <= 20
   

Обратите внимание, что этот запрос, скорее всего, будет выполняться для очень изменчивых данных, и вам потребуется своевременно выполнять дополнительные проверки.

Поскольку MySQL не может объединять SPATIAL индексов, будет лучше использовать какую-либо технологию поверхностного мозаичного изображения:

1. Разделите поверхность Земли на несколько плиток, скажем, 1 x 1 " (это примерно 30 метров меридиана и 30 * COS(lon) параллели.

2. Сохраните данные в столбце CHAR(14): 7 цифр lat + 7 цифр на lon (всего 14 цифр). Отключить сжатие ключей в этом столбце.

3. Создание составного индекса для (time, tile)

4. На клиенте рассчитайте все возможные плитки, в которых ваши друзья могут быть. Для расстояния 20 метров это будет самое большее 9 плиток, если только Вы глубоко на севере или юге. Однако вы можете изменить алгоритм листов для обработки этих случаев.

5. Введите этот запрос:

   SELECT  *
   FROM    (
           SELECT  tile1
           UNION ALL
           SELECT  tile2
           UNION ALL
           …
           ) tiles
   JOIN    users u
   ON      u.tile  = tiles.tile
           AND u.time >= NOW() 
           AND GLength(LineString(user_point, @mypoint)) <= 20
   

, где tile1 и т. Д. - это предварительно рассчитанные плитки.

SQL Server реализует этот алгоритм для своих пространственных индексов (вместо R-Tree, который используется MySQL).

Answer 2

Ну, наивным подходом было бы сделать O (n) проход по всем точкам, получить их расстояние от текущей точки и найти верхнюю 20. Это прекрасно для небольших наборов данных скажем <= 500 баллов), но на больших сетах это будет довольно медленно. В SQL это будет выглядеть так: </p>

SELECT point_id, DIST_FORMULA(x, y) as distance
FROM   points
WHERE  distance < 20

Чтобы устранить неэффективность описанного выше метода, вам придется использовать какой-то шаг предварительной обработки, скорее всего, разбиение пространства . Это часто может значительно улучшить производительность при поиске типа ближайшего соседа. Однако, в вашем случае, если все точки обновляются каждые 10 секунд, вам нужно будет выполнить проход Ω (n) , чтобы обновить положение каждой точки в дереве разбиения пространства. Если между каждым обновлением у вас более нескольких запросов, это будет полезно, в противном случае это будет просто накладные расходы.

Answer 3

Глава 11 «Дизайн базы данных Знай все» имеет некоторые мысли о том, как проектировать такую ​​базу данных.