Отслеживание точек GPS и поиск их ближайших соседей?

У меня есть список из 1 миллиона (медленно) движущихся точек на земном шаре (хранящихся как широта и долгота). Время от времени каждая точка запрашивает список из 100 ближайших других точек (с настраиваемым максимальным диапазоном, если это помогает).

К сожалению, SELECT * SORT BY compute_geodetic_distance() LIMIT 100 выполняется слишком медленно для каждой точки снова и снова. Итак, мой вопрос: как мне эффективно справиться с этим? Известны ли для этого лучшие алгоритмы/структуры данных/...? Или это единственный способ, и я должен смотреть на распределение нагрузки на сервер?

(Примечание: это для приложения для Android, а точки — это пользователи, поэтому, если мне не хватает решения для Android, не стесняйтесь говорить об этом!)


mysql android algorithm gps nearest-neighbor
person user1111929    schedule 12.06.2013    source источник
comment
@eggyal, нет проблемы с двумерным индексированием, чтобы сократить один миллион до нескольких сотен операций.   -  person AlexWien    schedule 12.06.2013

Ответы (4)


arrow_upward
1
arrow_downward

Для ваших задач были придуманы геопространственные базы данных.
Есть Oracle Spatial (дорого) и PostGres (бесплатно).
Эти базы хранят ваши миллионы точек в географическом индексе, дереве квадрантов (Oracle). Такой запрос почти не требует времени.

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

Операции поиска и вставки легко реализовать. Обновление/удаление может быть более сложным. (Самый дешевый, связанный с усилиями по реализации, - это создание нового дерева квадрантов каждую минуту)

Используя дерево квадрантов, вы можете выполнить сотни или тысячи таких ближайших 100 точек за секунду.

person AlexWien    schedule 12.06.2013
comment
@eggyal, потому что это сортировка. сокращение от одного миллиона до нескольких должно быть выполнено заранее, например, в предложении where с использованием пространственного расширения. - person AlexWien; 12.06.2013
comment
Я вижу, что комментарий, в котором упоминается, что MySQL также имеет пространственные расширения, исчез. Поэтому я публикую это снова, так как считаю это ценной информацией. - person user1111929; 13.06.2013
comment
Не могли бы вы объяснить, как я могу сделать тысячи таких ближайших 100 точек за секунду? Для заданной точки curr теперь я выбираю ближайшие 100 точек по SELECT user_id, GLENGTH(LINESTRINGFROMWKB(LINESTRING(ASBINARY(curr),ASBINARY(pt)))) AS distance ORDER BY distance LIMIT 100, но на самом деле это довольно медленно. Возможно, все было бы быстрее, если бы я мог добавить предложение WHERE, но я не вижу способа заранее определить, будут ли ближайшие 100 точек находиться в пределах 5 км или 5000 км. - person user1111929; 15.06.2013
comment
Вопрос в том, действительно ли вам нужны 100 ближайших точек, даже если только 50 точек находятся в пределах 100 км? (так, где расстояние ‹ х). Если вы не нашли достаточно, вы можете продублировать расстояние x в предложении where. Для вашего точного вопроса было бы лучше загрузить все координаты в основную память и использовать собственное дерево квадрантов. В этом случае вы знаете, когда остановиться. - person AlexWien; 15.06.2013
comment
Боюсь, радиус 100 км часто дает только 1-2 балла в сельской местности. А радиус в 1000 км потенциально может включать половину пользовательской базы. Про построение собственного дерева в памяти: можно ли это как-то сделать на PHP? А если нет, то как я могу заставить его взаимодействовать с остальной частью моего приложения, написанного на PHP/MySQL на стороне сервера? - person user1111929; 15.06.2013
comment
В качестве альтернативы, есть ли способ выполнить двоичный поиск, чтобы найти правильный радиус? Начать с COUNT() на 100 км и в зависимости от результата перейти на 50 или 200 км? Затем снова посчитайте и дойдете до 25 или 75, или 150, или 400? Или сложность COUNT() не лучше, чем у SELECT в этих четырехъядерных деревьях? (т.е. проблематично ли выполнить COUNT(), который возвращает 500000?) - person user1111929; 15.06.2013
comment
Вот хороший ответ, который полезен для многих приложений. Хитрость заключается в том, чтобы вычислить из заданного радиуса maxLatitude, minLatitude, maxLongitude и minLongitude и использовать это в предложении where. Это сократит ваши поиски. Затем с этим вы можете выполнить бинарный поиск, как вы сказали. - person AlexWien; 15.06.2013

arrow_upward
0
arrow_downward

С архитектурной точки зрения я бы устроил так, чтобы каждая «точка» звонила домой на сервер с указанием их местоположения, когда оно изменяется более чем на определенную величину. На сервере вы можете выполнить тяжелую работу по вычислению расстояния между точкой, которая переместилась, и каждой из других точек, а также для каждой из других точек обновить их список из 100 ближайших точек, если это необходимо. Затем вы можете отправлять изменения в ближайший список 100 точек по мере их появления (тривиально, если вы используете App Engine, поддерживается Android push).

Это сводит объем работы к абсолютному минимуму:

  • Сообщайте об изменении местоположения только тогда, когда точка перемещается достаточно далеко
  • Пересчитывать расстояния только при получении отчета
  • Не перестраивайте ближайший список 100 для точки каждый раз, создайте список один раз, а затем определите, будет ли перемещенная точка добавлена ​​или удалена из списка всех остальных точек.
  • Уведомляйте точку об изменениях только в ее списке 100 лучших, чтобы сохранить пропускную способность.

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

person Phil Haigh    schedule 12.06.2013

arrow_upward
0
arrow_downward

Вы должны разделить землю на зоны, а затем использовать алгоритм внутренних точек, чтобы выяснить, в каких зонах находится телефон. Каждое возможное подмножество зон будет однозначно определять 100 ближайших узлов с достаточной точностью. Вы можете получить точный набор из 100 узлов, проверяя расстояние один за другим по узлам-кандидатам, которые (еще раз) определяются подмножеством зон.

person Tyler Durden    schedule 12.06.2013

arrow_upward
0
arrow_downward

Вместо r-tree или quadtree, то есть пространственного индекса, вы также можете использовать quadkey и кривую монстра. Эта кривая уменьшает размерность и полностью заполняет пространство. Вы можете скачать мою кривую Гильберта класса php с phpclasses.org. Вы можете использовать простой столбец varchar для quadkey и выполнять поиск по уровням слева направо. Хорошее объяснение взято с веб-сайта Microsoft Bing maps quadkey.

person Gigamegs    schedule 26.08.2013