Блог

Я разрабатываю систему, в которой у меня есть список из 100000 геолокаций и 10000 геолокаций движущихся автомобилей, и каждые X секунд происходит обновление местоположения транспортного средства, то есть одновременно я могу получать обновления местоположения N транспортных средств.

Моя проблема в том, что каждые X секунд системе необходимо искать все транспортные средства, которые находятся близко к местоположению L, в настоящее время система просматривает список геолокаций, ища все транспортные средства, которые находятся в пределах определенного радиуса, и применяя некоторые фильтры поиска в этом процессе.

Но я заметил, что система вычисления расстояния, которая вычисляет расстояние по прямой, потребляет больше всего времени в этом процессе фильтрации, и поскольку в системе есть несколько методов, которые выполняют эти поиски, включая расстояние между точками L и N транспортных средств в радиусе,этот процесс становится все медленнее и медленнее, потому что для каждой точки L мне нужно просмотреть весь список транспортных средств.

Итак, я начал искать системы для индексации геолокаций и что я также могу выполнять поиск по этим индексам, используя правила, например, получить все транспортные средства в радиусе N км от географического местоположения X

H3 кажется мне чем-то интересным, но я не смог найти его в их документации, как я могу это сделать или как выполнить этот процесс добавления N транспортных средств на карту.

Вы можете посмотреть учебник о том, как использовать H3 для поиска по радиусу здесь: https://observablehq.com/@nrabinowitz/h3-radius-lookup

Основные шаги следующие:

• Проиндексируйте все ваши данные с помощью H3. В зависимости от вашей системы вы можете сохранить результат в памяти в виде хэш-карты или в хранилище K / V, где индекс H3 является ключом, а значение — список транспортных средств в этой ячейке.
• Чтобы выполнить поиск, вычислите k-кольцо с точки интереса L . Размер k-кольца зависит от разрешения H3, которое вы используете для индексации, и радиуса, который вы хотите выполнить поиск.
• Выполните поиск K / V в вашем индексе для каждой ячейки в k-кольце и добавьте результаты в некоторый выходной массив. Если вас интересует точное расстояние, а не приблизительное расстояние, вы можете сделать k-кольцо больше, чем необходимо, и фильтровать по истинному расстоянию в это время.

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

Вам все равно нужно будет индексировать свои транспортные средства по мере их перемещения. Грубо говоря, каждый раз, когда вы получаете новое местоположение для транспортного средства, вам нужно проверить, находится ли оно в новой ячейке, и если да, переиндексируйте его. Это означает, что вам нужно сохранить текущую ячейку для каждого транспортного средства либо в каждой записи транспортного средства, либо в отдельном индексе, а также ваш индекс транспортных средств на ячейку.