алгоритм Как найти ближайший POI к 1 миллиону координат эффективным способом

Это пост-интервью, где я должен был реализовать это--

Итак, мне дан список POI ресторана (около 2000 из них) в евклидовых координатах.

Затем мне дается список пользовательских координат (их 1 миллион)

Мне было поручено вернуть количество пользователей в определенном радиусе (10,15) от одной точки интереса, а во-вторых, радиус, необходимый для того, чтобы 75% пользователей находились на расстоянии от точки интереса.

Расстояние — это то, что я мог рассчитать, но перебор означал проверку 1 миллиона координат на 1000 координат, что заняло очень-очень много времени.

Что было бы более эффективным способом сделать это вместо этого?


java geocoding algorithm
person user3394313    schedule 30.10.2017    source источник
comment
Есть много способов сделать это, но в основном вы должны стремиться разделить пространство на части, достойные поиска, и части, которые не стоит искать.   -  person Andy Turner    schedule 31.10.2017
comment
Вы можете искать «пространственные структуры данных», особенно R-дерево.   -  person Ivan Smirnov    schedule 31.10.2017
comment
Для первой проблемы: Map Reduce может быть другим способом (захватом ресурсов). Для второй проблемы: сгруппируйте точки, а затем вычислите POI, ближайший к пользователю. Затем увеличьте радиус, чтобы покрыть 75% расстояния user_poi.   -  person displayName    schedule 01.11.2017

Ответы (2)


arrow_upward
1
arrow_downward

Лучше использовать фреймворк, который позволяет пространственно индексировать координаты и запускать эффективные пространственные операторы. Mapinfo, пространственно-ориентированная база данных (Oracle Spatial — может потребоваться дополнительное лицензирование для производственного использования), ESRI, открытый исходный код и т. д.

Обычно действие будет

  1. загружать POI в контейнер с пространственной индексацией (таблица с пространственным индексом).
  2. Загружать пользователей в контейнер с пространственной индексацией
  3. расширить POI как круглые объекты с требуемым радиусом расстояния.
  4. Пространственное объединение/объединение для пользователей в кругах POI

Эти пространственные соединения/объединители доступны в различных вариантах пространственных операторов.

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

1 миллион пользователей на самом деле не очень большой - это управляемо - проблема в том, что эти точки должны оцениваться по сравнению с 2000 POI. Я считаю, что лучший способ

  1. Сначала создайте ограничивающие квадраты вокруг POI, используя радиус 2 x в качестве стороны.
  2. Это позволит вам довольно быстро оценить, какие точки представляют интерес для каждого POI. В принципе, в качестве операторов могут использоваться только операторы больше и меньше.
  3. Имея для каждой POI набор пользователей, вы можете еще больше сузить его, выполнив расчет фактического расстояния.

Вы можете использовать все виды интеллектуального индексирования и сортировки, чтобы сделать это намного быстрее. Предлагаемое R-Tree в комментарии кажется очень подходящим, если у вас есть время для реализации. Это поможет вам во втором шаге выше.

Гораздо более простой подход - в зависимости от того, как расположены ваши координаты (как выглядит ваш мир), состоит в том, чтобы разделить ваш мир на большие квадраты и сначала определить для каждого пользователя и каждого POI, к какому квадрату они принадлежат. Вы можете быстро определить всех пользователей в пределах одного квадрата POI или любого соседнего квадрата как пользователей, представляющих интерес. Придумайте умную схему индексации/нумерации, которая также поможет вам идентифицировать соседей. Иметь список пользователей, проиндексированных в их квадраты через Hashmaps.

person YoYo    schedule 30.10.2017
comment
Извините за дополнительное ограничение, мне не разрешили использовать внешнюю структуру, которая уже создана. - person user3394313; 31.10.2017

arrow_upward
0
arrow_downward

Используйте структуру данных пространственного поиска или базу данных и делайте соответствующие запросы.

Чтобы радиус охватывал 75% пользователей, вы всегда можете просто выполнить двоичный поиск радиусов, используя известное общее количество пользователей и самые отдаленные координаты.

person sleeplessnerd    schedule 30.10.2017