Можно ли сделать быстрый поиск по карте с 1 млн маркеров (MongoDb) и кластеризацией?

Доброго времени. Есть база (MongoDb) с 1 млн точек для карты. У клиента есть карта на которой отображаются эти маркеры. На сервер прилетают границы просматриваемой области клиента + зум.
1. Нужно эти данные кластеризовать на сервере
2. Нужно это делать максимально быстро
Уже долгое время пытаюсь придумать что с этим можно сделать и пока нет ответа.
Для понимания примерной картины:
1. Размеры
база данных в 1 млн, она еженедельно наполняется по 20-30к новыми данными, т.е. в теории через год-два, она может достигать 2-3 млн.
2. Пользователи
На сайте каждый час находится 200-600 пользователей которые обращаются к карте при каждом перемещении.
3. Скорость
В идеале обойтись вообще без фильтрации данных по типу A < B < C, что бы запрос просто целенаправелнно доставал нужную область карты. Было бы круто достичь 0.005с на запрос (если это реально).

Пишу вопрос потому что пробую различные варианты, и это займет много времени, может кто сталкивался с подобным и огородит от граблей и кучи потраченного времени.

Что пробовал:
1. Пробовал реализовать QuadTree, но я так понимаю он хорошо работает только если все держать в памяти, иначе я не придумал как QuadTree реализовать для MongoDb. Он отрабатывает за 0.005с, но нужно держать в памяти всю коллекцию маркеров.
2. Пробовал каждому маркеру присваивать QuadKey. Т.е. делить карту на квадранты, на 4 части, и так до 23 уровня глубины, QuadKey относился к своему тайлу на карте, и по идее если сделать поиск по QuadKey + группировка, получается отличная кластеризация, но запрос идет 0.8с на большом зуме тип 14-17, и 1-2с на маленьком, когда много объектов попадают под область видимости. Пробовал по разному с ним играться, искать подстроки в QuadKey, преобразовывать QuadKey в uint и делать запросы типа A < B < C. Но это все сводилось к 0.8с до 3с. Все это с учетом индексации в монге.
3. Пробовал делать 2d индекс в монге по положению маркеров, и делать поиск через $geoWithin, но такой запрос отрабатывает за 0.8-0.9с.

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

Сами вопросы:
Может кто-то сталкивался с подобной задачей и знает как лучше всего кластеризовать маркеры? Какой алгоритм более эффективен?
Каким образом реализовать поиск по 1млн маркеров, что бы это занимало как можно меньше времени?
Имеет смысл тут делать кэш?
Может кто знает как работают на стороне сервера сервисы типа яндекс.карт, гугл.карт?
Может есть готовые решения для C#?

Буду благодарен за любую ссылку, личный опыт или полезную информацию
  • Вопрос задан
  • 309 просмотров
Пригласить эксперта
Ответы на вопрос 3
mayton2019
@mayton2019
Bigdata Engineer
Почти все гео-поисковые системы для хранения геометрии используют либо quad-tree либо R-tree. К чему здесь Mongo - вообще непонятно. Это бд другого типа. Для документов.

Бери деревья и используй. Мало памяти - ну решай это быстрыми дисками или просто покупай больше узлов для параллельных поисков.
Ответ написан
firedragon
@firedragon
Не джун-мидл-сеньор, а трус-балбес-бывалый.
1 миллион маркеров пусть они занимают килобайт каждый
Гигабайт памяти? Пусть это корявый яваскрипт и он дает оверхед х3
3 гига

Пусть будет расширение в 3 раза.
9 гигов
Не очень большой сервер с 16 гигами оперативки.

Это если в лоб. Если поставить какой нибуть Redis то память сократится до 3 гигов в самом жестком варианте.
Ответ написан
2ord
@2ord
Попробуйте PostGIS для хранения данных. В ней эти алгоритмы уже реализованы и данные получаются при помощи обычных SQL запросов.
Для скорости пробуйте построить таблицу соответствий между входными параметрами и искомой областью. Скажем, определить longitude, latitude и тогда можно быстро доставать нужную область. С кэшированием координат часто запрашиваемых областей еще более ускорится.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы