Комментарии 37
1. Конкретно этот quadkey — Morton code.
2. 16ый уровень разбиения, который можно сохранить в 32 битный uint описывает квадрат со стороной примерно 300 метров. Для предварительной кластеризации этого достаточно.
3. Ленивый клиент — это не самое умное решение, но за перевод в пиксельные координаты отдельное спасибо.
4. Маску лучше представлять как маску. Т.е. 03201203031012000000000/12.
В общем случае эта задача называется «понижением размерности» 2Д данных через использование какой либо spatial filling curve, которая сводит задачу к 1Д варианту. Люблю эту наркоманию.
2. 16ый уровень разбиения, который можно сохранить в 32 битный uint описывает квадрат со стороной примерно 300 метров. Для предварительной кластеризации этого достаточно.
3. Ленивый клиент — это не самое умное решение, но за перевод в пиксельные координаты отдельное спасибо.
4. Маску лучше представлять как маску. Т.е. 03201203031012000000000/12.
В общем случае эта задача называется «понижением размерности» 2Д данных через использование какой либо spatial filling curve, которая сводит задачу к 1Д варианту. Люблю эту наркоманию.
В статье W for Wikipedia, в разделе Z for Z-code есть чуть более техническое описание работы Z кривых, плюс ссылки на sql+php и mongo+js решения для серверной кластеризации.
Вообще об этой технологии я пытаюсь рассказывать уже лет 8, жаль что до нужных людей мои презентации не доходят :(
Вообще об этой технологии я пытаюсь рассказывать уже лет 8, жаль что до нужных людей мои презентации не доходят :(
А где можно увидеть Ваши презентации?
Последняя — events.yandex.ru/lib/talks/2354 — 2014 год, первая нормальная была 2012.codefest.ru/lecture/77 — 2012 год, даже примерчик на гитхаб выложил — github.com/theKashey/quadLoader.
В принципе «читабельно» в первый раз я описал Z и кластеризацию в статье про gdeetotdom(2010), которая сейчас уехала на geektimes. С тех пор в каждой второй статье на хабре я это дело упоминаю, так и или иначе — уж больно широкие применения у этих чтук.
Это не просто «число» — одновременно это nested set, B-tree индекс и материализация Linear quad-tree. И это самая простая кривая — их на любой взыскательный вкус напридумывали.
В принципе «читабельно» в первый раз я описал Z и кластеризацию в статье про gdeetotdom(2010), которая сейчас уехала на geektimes. С тех пор в каждой второй статье на хабре я это дело упоминаю, так и или иначе — уж больно широкие применения у этих чтук.
Это не просто «число» — одновременно это nested set, B-tree индекс и материализация Linear quad-tree. И это самая простая кривая — их на любой взыскательный вкус напридумывали.
Отлично, мого полезной информации. Спасибо. Когда искал что-то подобное найти было сложновато и наткнулся только на обрывки информации.
А на счет ленивого клиента — это был выбран просто самый быстрый способ реализации. Естественно в дальнейшем от него надо уходить.
А на счет ленивого клиента — это был выбран просто самый быстрый способ реализации. Естественно в дальнейшем от него надо уходить.
На самом деле, лично использую quad коды в основном для выборки обьектов, а не для кластеризации. Это так — приятный бонус, да и не все кластеризуется. Да и на клиенте можно поработать немного :)
В частности Z коды используются не только для загрузки данных из базы — именно они (лично у меня) используются для передачи команды на сервер.
В первый раз такой подход был замечен на wikimapia, я его активно перенял. С тех пор особо популярен он не стал — если и грузят по тайловой сетке, то в обычных x,y,z координатах.
В частности Z коды используются не только для загрузки данных из базы — именно они (лично у меня) используются для передачи команды на сервер.
В первый раз такой подход был замечен на wikimapia, я его активно перенял. С тех пор особо популярен он не стал — если и грузят по тайловой сетке, то в обычных x,y,z координатах.
ммм а чем квадкоды отличаются от геохэшей?
А почему не используют K-Means кластеризацию? Или это дорого на сервере?
Это ведь суперлениво для клиента — посылаешь на сервер область видимости и максимальное желаемое количество результирующих кластеров и получаешь ответ.
Это ведь суперлениво для клиента — посылаешь на сервер область видимости и максимальное желаемое количество результирующих кластеров и получаешь ответ.
Честно говоря в тот момент положились на опыт Яндекса, они в докладах утверждали что рассматривали другие варианты кластеризации но наиболее приемлимой оказалась данная.
K-means достаточно долгий, в CPU, вариант, но для многих бэкендеров нет ничего проще, чем нагрузить кластер спарков его расчетом…
Но применимость k-means на картах просто низка. У него есть проблема — он не «стабильный».
Например вы смотрите на Москву. Запрашиваете данные только для Москвы. Но… вы должны произвести кластеризацию всех обьектов по всему миру на 10ом зуме. Чтобы при сдвиге у вас не изменился набор исходных данных и все «взрывообразно» не перекластеризовалось.
Потом приходит необходимость делать иеархический k-means, и ты понимаешь что это того не стоит.
Но применимость k-means на картах просто низка. У него есть проблема — он не «стабильный».
Например вы смотрите на Москву. Запрашиваете данные только для Москвы. Но… вы должны произвести кластеризацию всех обьектов по всему миру на 10ом зуме. Чтобы при сдвиге у вас не изменился набор исходных данных и все «взрывообразно» не перекластеризовалось.
Потом приходит необходимость делать иеархический k-means, и ты понимаешь что это того не стоит.
Потом приходит необходимость делать иеархический k-means, и ты понимаешь что это того не стоит.
сделали, жалеем)
расскажите подробности
Что сказать, медленно работает, агргегация данных для 6000 объектов занимает пару минут. Через k-means определяли кластера элементов для 21 уровня зума, и хоть и удалось уменьшить чуть количество итераций сложность всеравно остается O(N^2). Так как объектов планируется много — не подходит.
В итоге перевели агрегацию на ElasticSearch + плагин geocluster-facet, который использует алгоритм с меньшим временем выполнения + оптимизирован за счет отсутствия сложной математики, все сводится к вычислению геохэшей один раз и побитовым операциям, что-то очень напоминающие приведенные в статье квадкоды.
В итоге перевели агрегацию на ElasticSearch + плагин geocluster-facet, который использует алгоритм с меньшим временем выполнения + оптимизирован за счет отсутствия сложной математики, все сводится к вычислению геохэшей один раз и побитовым операциям, что-то очень напоминающие приведенные в статье квадкоды.
А до какого примерно количества объектов этот метод дает приемлемые результаты?
В смысле? Что считать приемлимым результатом. На больших объемах резальтаты не плохие, но по времени кластеризации выходит накладно, и алгоритм не позволяет перестраивать данные только частично. По точности проблем особо небыло, проблемы у него те же что и у остальных (пересчет пиксальных расстояний в физические координаты), так что тут все весьма стандартно. Но выборка по фасетам выдает примерно схожий по точности результат за гораздо меньшее время. Ну то есть по фасетам точность выборки самостовима с k-means, выше чем у гридов.
Я имел в виду именно время. На каких примерно объемах оно ещё работает достаточно быстро.
Кстати, насчет пересчета координат пиксели/градусы — это да. Не могу до конца понять, как это сделать правильнее всего — мешают нелинейности проекции Мерктора. Если смотреть в масштабе одного города, то ими можно пренебречь, но если целый континент — уже нет.
Кстати, насчет пересчета координат пиксели/градусы — это да. Не могу до конца понять, как это сделать правильнее всего — мешают нелинейности проекции Мерктора. Если смотреть в масштабе одного города, то ими можно пренебречь, но если целый континент — уже нет.
Не понятно какая задача решается:
если нужно правильно хранить, то лучше взять хранилище с поддержкой геометрических индексов. Они есть уже и в SQL и в noSQL решениях. C MySQL не работал, поэтому не могу сказать, что есть в нём, но в среде открытых есть PostGIS.
если нужна именно кластеризация, то грид быстрый, и самый не красивый из всех алгоритмов. Когда данных много, пины кластеров образуют практически регулярную сетку. Это хорошо заметно на скрине Яндекса в статье. Раз кластеры считаются на сервере, то можно выбрать более ресурсоёмкий алгоритм с красивым результатом.
Если посмотреть на скрины того «что получилось»: алгоритм выбора репрезентативной точки выбран не удачно. Например, маркер который, видимо, должен принадлежать Кубе просто висит над морем.
если нужно правильно хранить, то лучше взять хранилище с поддержкой геометрических индексов. Они есть уже и в SQL и в noSQL решениях. C MySQL не работал, поэтому не могу сказать, что есть в нём, но в среде открытых есть PostGIS.
если нужна именно кластеризация, то грид быстрый, и самый не красивый из всех алгоритмов. Когда данных много, пины кластеров образуют практически регулярную сетку. Это хорошо заметно на скрине Яндекса в статье. Раз кластеры считаются на сервере, то можно выбрать более ресурсоёмкий алгоритм с красивым результатом.
Если посмотреть на скрины того «что получилось»: алгоритм выбора репрезентативной точки выбран не удачно. Например, маркер который, видимо, должен принадлежать Кубе просто висит над морем.
Задача решалась реализовать выбранный способ кластеризации.
Да, в других БД есть поддержка хранения гео данных, но вот на счет кластеризации я не уверен. И здесь просто вырезки из большого проекта где используется MySQL.
Естественно что алгоритм не идеален, понятно что мы находим средную координату в квадрате и она может посать и на вершину горы и в другю страну и в озеро и в море. Все эти недостатки можно устранить в будущем.
Да, в других БД есть поддержка хранения гео данных, но вот на счет кластеризации я не уверен. И здесь просто вырезки из большого проекта где используется MySQL.
Естественно что алгоритм не идеален, понятно что мы находим средную координату в квадрате и она может посать и на вершину горы и в другю страну и в озеро и в море. Все эти недостатки можно устранить в будущем.
Если не секрет… Где вы использовали данную технологию? Какие задачи решали?
Использовали в одном гео-сервисе, название сказать не могу(посчитают пиаром).
Задача была размещать на карте большое количество маркеров( миллионы), и отображать это пользователям без проблем с производительностью.
Задача была размещать на карте большое количество маркеров( миллионы), и отображать это пользователям без проблем с производительностью.
Не посчитают, не боись.
Так где же?
Так где же?
Demo версия карты fociapp.com/map. Там же есть ссылка на приложение. А вообще планируетс статья по этому проекту в разделе «Я пиаруюсь».
Немного хромает реализация — тут и метки «мигают» при сдвиге карты и кластеризация немного подтупливает.
Я бы с сервера отдавал бы больше точек — еще бы на один уровень маску группировки сдвинул бы и «докластеризовывал» бы на клиенте.
Ну и лимиты при выборке из базы увеличил бы (или совсем убрал) — количество данных регулируется кластеризацией.
Сейчас реально бывают «дырки» — в европе данные есть, в Австралии — нет. Убираем европу, и внезапно точки появляются. От этого еще хорошо разбиение запроса на тайлы лечит.
Я бы с сервера отдавал бы больше точек — еще бы на один уровень маску группировки сдвинул бы и «докластеризовывал» бы на клиенте.
Ну и лимиты при выборке из базы увеличил бы (или совсем убрал) — количество данных регулируется кластеризацией.
Сейчас реально бывают «дырки» — в европе данные есть, в Австралии — нет. Убираем европу, и внезапно точки появляются. От этого еще хорошо разбиение запроса на тайлы лечит.
Очень хочу увидеть сравнение этого приложения с Postgresql/PostGIS и идекса типа R-tree. Что быстрее?
Просто в MySQL вся поддержка геоданных сделана по остаточному принципу и to be implemented. В PostGIS она полноценная и работает очень хорошо.
Просто в MySQL вся поддержка геоданных сделана по остаточному принципу и to be implemented. В PostGIS она полноценная и работает очень хорошо.
Сделать сравнение было бы доастаочно интересно, попробую найти на это время :)
В MySQL рассматривал Spatial Data, но там насколько помню они еще не готовы к полноценному использованию.
В MySQL рассматривал Spatial Data, но там насколько помню они еще не готовы к полноценному использованию.
Из опробованных решений еще стоит упоминуть ElasticSearch и плагин geocluster-facet. Ну и эластика умеет агрегацию по сетке делать из коробки (использую геохэши).
Кстати на практике оказалось что использование 50% медианы куда лучше выглядит чем среднее арифметическое.
Сделали кластеризацию этим же методом bookingtroll.com
В процессе реализации возникло ряд проблем: на стыках сетки (особенно экватор, 180 меридиан, 41-й меридиан) работает не очень хорошо.
Если область карты далека от квадрата, то лучше разбивать ее на два или больше квадратных кластеров и получать данные для них отдельно.
В процессе реализации возникло ряд проблем: на стыках сетки (особенно экватор, 180 меридиан, 41-й меридиан) работает не очень хорошо.
Если область карты далека от квадрата, то лучше разбивать ее на два или больше квадратных кластеров и получать данные для них отдельно.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Публикации
Серверная кластеризация маркеров на карте. От теории к практике