Pull to refresh

Comments 23

UFO just landed and posted this here
Про 200 тыс в основном. То что они лежали в Hive, определяло только выбор инструмента в целом.
А использование одного из платных сервисов не рассматривалось? Вижу вот у гугла 5$ за 1000, возможно есть и подешевле
Во-первых, за 200000 точек это будет уже $10000, во-вторых, это скорее всего будет медленный REST.

Но самое главное — у нас интранет, где нет никакого гугля :)

ArcGIS судя по всему просто использует модуль PostGIS, т.е. можно было бы просто загнать данные карт в локальный постгрес и потом выбирать напрямую из него по координатам с помощью ST_Intersects, ST_CoveredBy, ST_Within и тд. Эта схема относительно легко масштабируется.

ArcGIS в нашем случае живет на Oracle, так что использовать PostGIS точно не может :)

Но вообще вариант взять координаты из базы ArcGIS рассматривался, и был отброшен, потому что наша база не обновляется — денег не заплатили.
Кстати, Spatial Framework for Hadoop включает в себя все те же функции, ST_Contains например, потому что их набор — стандарт OGC. Хотя да, spatial индексы, как PostGIS, оно само для нас не построит, поэтому если тупо применить ST_Contains — скорее всего будет медленно.

Не совсем понял, что мешает залить в базу тот же OpenStreetMap, придется конечно немного поразбиратся, куда без этого. Сейчас многие БД предоставляют возможности работать с гео данными, даже SQLite можно поднять в памяти с соотв. расширением. Вопрос сводится к следующему, будет ли реализация реверс геокодинга на хадупе/спарке, быстрее/проще/лучше, чем аналогичная (и уже готовая) реализация в одной из таких БД? Причем сама БД статическая, скопировал на вторую машину запустил и получил гарантированный х2 перформанс.

>чем аналогичная (и уже готовая) реализация в одной из таких БД?
Сможете назвать парочку готовых?

>Причем сама БД статическая
Вообще-то нет. База адресов и POI вовсе не статическая, и процесс ее периодического обновления далеко не такая простая вещь, как может показаться. Особенно если вы берете данные из OSM — в этом случае очень желательно свои данные туда же и возвращать.

>быстрее/проще/лучше, чем аналогичная
Описывал я это все вовсе не как готовое решение, которое проще или лучше (хотя оно и сильно быстрее многих), а как подход, позволяющий быстро реализовать такое самостоятельно. Цели сделать лучше не ставилось, и далеко не очевидно, что именно тут считать лучшим.

Развертывание нескольких машин с Postgres вполне возможно, но мне не кажется решением без недостатков. Основной из которых в том, что если задачи геокодирования это лишь малая часть задач кластера (а у нас именно так), то отдельный Postgres — это отдельная немаленькая морока по администрированию. Он либо работает постоянно, потребляя ресурсы когда не нужен, либо надо как-то организовать его запуск по требованию. А так да, вполне себе решение. У нас были планы развертывания ArcGIS с его базой внутри кластера, для этих целей — и в частности по этим же причинам они не реализованы (там еще и лицензии примешиваются).

>Не совсем понял, что мешает залить в базу тот же OpenStreetMap, придется конечно немного поразбиратся, куда без этого.
Ничего не мешает. Про это — следующий пост, который уже ждет своей очереди.
Lucene — это не спортивно :)

В смысле, я пока рассказал идею, как это сделать вручную самому, в 400 строк своего кода на Spark. Про то, что есть другие инструменты, в том числе пригодные для применения в кластере — возможно расскажу в следующий постах.
А в чем спорт?

С Lucene заранее например индексируем точки городов мира отсюда, а потом загружаем на каждом Executor в Spark и опрашиваем.

Поиск в радиусе на индексе из ~3 млн точек и точности в ~1 метр берет окоро 2 мс на запрос. А вот поиск топ ближайших городов работает значительно медленнее 700-1000 мс на запрос, т.к. индекс по всей видимости не используется.
>А в чем спорт?
В том, чтобы сделать обратный геокодер в виде примерно 400 строк кода. Я никого не убеждаю, что надо делать именно так, это просто был пример проблем, которые приносит с собой масштаб, и как их можно быстро решить.

Что до точек — то в моем понимании с точками все сильно проще. Расчет расстояния между точками — это константное время, ну может чуть-чуть сложнее, чем на плоскости. Уже для улиц это не так. Ваш пример вполне применим для домов, например, если считать их точками (в реальности в OSM далеко не все дома точки, но построить некий центр для дома вполне можно заранее).
Кстати, хорошая статья.

Мы реально смотрели в сторону Solr, но скорее для задачи прямого геокодирования, там это нужнее.
Ага, статья грамотная. Я собираюсь с автором кстати пообщаться в ближайшее время. Есть у меня к нему ряд вопросов.
А геоспарк не пробовали? Вполне неплохо себя показывает. Если индекс а-ля геохэш запилить, то и вообще отлично. Мы вот юзаем, не жалуемся. У нас порядка миллионов точек на одну карту, карты считаются на потоке.
Я тут описал историю в том виде, как она развивалась в жизни. На тот момент — нет, не пробовали. Потом уже дозрели, что нужно внедрять что-то готовое. Смотрели на GeoSpark, и еще на GeoMesa и семейство продуктов от тех же авторов, которые в тоже время и авторы JTS.

Собственно, главный вывод из этой истории состоял в том, что нужно попытаться построить spatial индекс в том или ином виде, а иначе будет плохо. Ну и как бы GeoSpark это умеет. В целом же нам GeoMesa чуть больше понравилась, хотя порог входа наверное чуть выше.

И да, геохеш на самом деле я зря не упомянул, потому что это по сути одна из альтернатив quad tree.
Ну мы как-то сразу с MR, который дёргает st_чегоНибудь() из PostgreSQL с PostGIS, перешли на геоспарк с индексами по геохешу, без промежуточных шагов. Меньше чем за полгода техпроцесс перевели, а итоговое ускорение расчёта получилось в пару сотен раз. На изначальном стеке расчёт карты по десятку тысяч точек был тем ещё предприятием, теперь бывает до сотен миллионов обсчитываем в приемлемое время на кластере из пяти нод среднего размера.

Довольно здорово дела упрощает ещё алгоритмическая сетка — заказчик был из Токио, там у них есть такая Japan Mesh. Она иерархическая, зависит только от координат, и её можно использовать сразу как индекс. В будущем планируем заюзать что-то такое же, только для всего мира.
Дело в том, что собственно геометрии у нас в основном вторичны. А большая часть логики завязана на адреса, а адреса — это уже совсем не ST_..., а совсем другая логика.
Почему другая? Адрес — это разве не метаданные аутлайна?
Ну если коротко — то нет. Ну или вернее, там все сильно сложнее. Во-первых, OSM не хранит в тэгах (по большей части) все компоненты адреса, так что для определения скажем города вам придется решать геометрическую задачу, и только дом и корпус к примеру прописан тэгом (причем далеко не очевидно, на чем именно он будет стоять). И это рекомендованное поведение — почему-то кое-кто считает, что геометрические отношения для этого применять правильнее.

А во-вторых, что важнее, там слишком много вариаций записи, и если обратное геокодирование делается достаточно примитивно, то прямое — это уже ужас-ужас.
Хм. Ну, в наших задачах чаще попадается либо сопоставление с postcode/zip/почтовым индексом (это всегда мозаика из аутлайнов конкретных участков, вплоть до 1 дома), либо в сильно ограниченной области, где не только город, но и район города заранее точно известен.

Или дата аналитик как-то сам подготавливает портянку аутлайнов в geojson с метаданными по адресам, или ячейками грида, или чем-то другим, что нужно для текущей карты. Откуда он их берёт, кроме OSM, я, если честно, не интересовался.

Ваша задача звучит посложнее.
>Откуда он их берёт, кроме OSM, я, если честно, не интересовался
Ну, у нас есть похожий проект в другом департаменте, связанный с оценкой стоимости недвижимости, если его совсем просто описать. При этом резонно считается, что стоимость объекта очень сильно зависит от локации, и эта локация — примерно квартал. Ну и что вы думаете — сидят люди, и руками эти самые кварталы рисуют, потому что нигде их нет, ни на одной карте. Теоретически можно попытаться построить их по улицам, например, но эта задачка как минимум уровня построения маршрутов, и я пока слабо себе представляю, как ее решать.

А наша задачка — она не то что сложнее, она просто другая. Прямое геокодирование, если его делать по уму, включает приличный объем NLP. И это совсем не геометрия.
Sign up to leave a comment.

Articles