Быстрый способ поиска миллионов координат по расстоянию

Question

У меня есть набор данных около 20 миллионов координат.Я хочу иметь возможность проходить по широте, долготе и расстоянию в милях и возвращать все координаты, которые находятся в пределах мили от заданных мной координат.Мне нужно, чтобы время отклика в идеале составляло менее 50 мс.

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

Этот метод возвращает результаты примерно через 2 секунды.Какой подход был бы хорош для увеличения скорости результатов?Я открыт для любых предложений.

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

Answer 1

Я думаю, что это больше проблема структуры данных.Хороший способ хранения больших наборов геопространственных координат - это R-дерево .Он обеспечивает лог _n M поиска.У меня ограниченные знания о Go, но я использовал R-Tree для эффективного использования наборов данных аналогичного размера в аналогичном сценарии использования в приложении JS.Из быстрого поиска кажется, что существует хотя бы пара реализаций Go R-Tree.

Answer 2

MongoDB имеет различные географические поиски. $ GeoNear позволит вам искать точки на определенном расстоянии от точки или в пределах фигуры.

https://docs.mongodb.com/manual/reference/operator/aggregation/geoNear/

PostGIS для Postgres имеет нечто подобное, но я не слишком знаком с этим.

Answer 3

Идея заключалась бы в том, чтобы иметь «сетку», которая разделяет координаты, поэтому, когда вам нужно выполнить поиск, вы можете безопасно вернуть все координаты в конкретной ячейке, не возвращать какие-либо из ячеек, находящихся слишком далеко от цели, иСравнение по координатам выполняется только для тех координат, которые находятся в ячейках, которые содержат некоторые координаты на расстоянии, а некоторые - на расстоянии.

Упрощенно до 1D:

Координаты от 1 до 100

Вы делите на 5 блоков по 20

Когда кто-то ищет все координаты на расстоянии 25из 47 вы возвращаете все координаты в блоках [30,39], [40,49], [50,59], [60,69], а затем после выполнения анализа по координатам для блоков [20,29] и [70,79] вы дополнительно возвращаете 22,23,24,25,26,27,28,29, 70,71,72.

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