Как стать автором
Обновить

Комментарии 37

1. Конкретно этот quadkey — Morton code.
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, жаль что до нужных людей мои презентации не доходят :(
А где можно увидеть Ваши презентации?
Последняя — 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. И это самая простая кривая — их на любой взыскательный вкус напридумывали.
Да действительно, ваша презентация была как раз одним из источников. Еще на HighLoad 2014 девушка из яндекс карт рассказывала по этой теме.
Отлично, мого полезной информации. Спасибо. Когда искал что-то подобное найти было сложновато и наткнулся только на обрывки информации.
А на счет ленивого клиента — это был выбран просто самый быстрый способ реализации. Естественно в дальнейшем от него надо уходить.
На самом деле, лично использую quad коды в основном для выборки обьектов, а не для кластеризации. Это так — приятный бонус, да и не все кластеризуется. Да и на клиенте можно поработать немного :)
В частности Z коды используются не только для загрузки данных из базы — именно они (лично у меня) используются для передачи команды на сервер.
В первый раз такой подход был замечен на wikimapia, я его активно перенял. С тех пор особо популярен он не стал — если и грузят по тайловой сетке, то в обычных x,y,z координатах.
Нам удалось еще использовать их для посика кластеров с определенными тегами маркеров.
ммм а чем квадкоды отличаются от геохэшей?
А почему не используют K-Means кластеризацию? Или это дорого на сервере?

Это ведь суперлениво для клиента — посылаешь на сервер область видимости и максимальное желаемое количество результирующих кластеров и получаешь ответ.
Честно говоря в тот момент положились на опыт Яндекса, они в докладах утверждали что рассматривали другие варианты кластеризации но наиболее приемлимой оказалась данная.
K-means достаточно долгий, в CPU, вариант, но для многих бэкендеров нет ничего проще, чем нагрузить кластер спарков его расчетом…
Но применимость k-means на картах просто низка. У него есть проблема — он не «стабильный».
Например вы смотрите на Москву. Запрашиваете данные только для Москвы. Но… вы должны произвести кластеризацию всех обьектов по всему миру на 10ом зуме. Чтобы при сдвиге у вас не изменился набор исходных данных и все «взрывообразно» не перекластеризовалось.
Потом приходит необходимость делать иеархический k-means, и ты понимаешь что это того не стоит.
Потом приходит необходимость делать иеархический k-means, и ты понимаешь что это того не стоит.

сделали, жалеем)
расскажите подробности
Что сказать, медленно работает, агргегация данных для 6000 объектов занимает пару минут. Через k-means определяли кластера элементов для 21 уровня зума, и хоть и удалось уменьшить чуть количество итераций сложность всеравно остается O(N^2). Так как объектов планируется много — не подходит.

В итоге перевели агрегацию на ElasticSearch + плагин geocluster-facet, который использует алгоритм с меньшим временем выполнения + оптимизирован за счет отсутствия сложной математики, все сводится к вычислению геохэшей один раз и побитовым операциям, что-то очень напоминающие приведенные в статье квадкоды.
А до какого примерно количества объектов этот метод дает приемлемые результаты?
В смысле? Что считать приемлимым результатом. На больших объемах резальтаты не плохие, но по времени кластеризации выходит накладно, и алгоритм не позволяет перестраивать данные только частично. По точности проблем особо небыло, проблемы у него те же что и у остальных (пересчет пиксальных расстояний в физические координаты), так что тут все весьма стандартно. Но выборка по фасетам выдает примерно схожий по точности результат за гораздо меньшее время. Ну то есть по фасетам точность выборки самостовима с k-means, выше чем у гридов.
Я имел в виду именно время. На каких примерно объемах оно ещё работает достаточно быстро.

Кстати, насчет пересчета координат пиксели/градусы — это да. Не могу до конца понять, как это сделать правильнее всего — мешают нелинейности проекции Мерктора. Если смотреть в масштабе одного города, то ими можно пренебречь, но если целый континент — уже нет.
Скажем так, при том количестве айтемов которое дает адекватное время обработки это все можно и на клиенте кластеризовать. Потому лучше взять что-то более интересное.
Не понятно какая задача решается:
если нужно правильно хранить, то лучше взять хранилище с поддержкой геометрических индексов. Они есть уже и в SQL и в noSQL решениях. C MySQL не работал, поэтому не могу сказать, что есть в нём, но в среде открытых есть PostGIS.
если нужна именно кластеризация, то грид быстрый, и самый не красивый из всех алгоритмов. Когда данных много, пины кластеров образуют практически регулярную сетку. Это хорошо заметно на скрине Яндекса в статье. Раз кластеры считаются на сервере, то можно выбрать более ресурсоёмкий алгоритм с красивым результатом.
Если посмотреть на скрины того «что получилось»: алгоритм выбора репрезентативной точки выбран не удачно. Например, маркер который, видимо, должен принадлежать Кубе просто висит над морем.
Задача решалась реализовать выбранный способ кластеризации.
Да, в других БД есть поддержка хранения гео данных, но вот на счет кластеризации я не уверен. И здесь просто вырезки из большого проекта где используется MySQL.
Естественно что алгоритм не идеален, понятно что мы находим средную координату в квадрате и она может посать и на вершину горы и в другю страну и в озеро и в море. Все эти недостатки можно устранить в будущем.
Самый простой вариант — под конечной координатой выбирайте некую реальную координату в бд, близкую к средней.
Да, это очень простой вариант, так мы всегда попадем в реальную точку.
Если не секрет… Где вы использовали данную технологию? Какие задачи решали?
Использовали в одном гео-сервисе, название сказать не могу(посчитают пиаром).
Задача была размещать на карте большое количество маркеров( миллионы), и отображать это пользователям без проблем с производительностью.
Не посчитают, не боись.
Так где же?
Demo версия карты fociapp.com/map. Там же есть ссылка на приложение. А вообще планируетс статья по этому проекту в разделе «Я пиаруюсь».
Немного хромает реализация — тут и метки «мигают» при сдвиге карты и кластеризация немного подтупливает.
Я бы с сервера отдавал бы больше точек — еще бы на один уровень маску группировки сдвинул бы и «докластеризовывал» бы на клиенте.
Ну и лимиты при выборке из базы увеличил бы (или совсем убрал) — количество данных регулируется кластеризацией.
Сейчас реально бывают «дырки» — в европе данные есть, в Австралии — нет. Убираем европу, и внезапно точки появляются. От этого еще хорошо разбиение запроса на тайлы лечит.
Согласен, уже обдумывал эти правки, но пока немного не хватает времени. Сама клиентская часть еще достаточно срая.
Очень хочу увидеть сравнение этого приложения с Postgresql/PostGIS и идекса типа R-tree. Что быстрее?

Просто в MySQL вся поддержка геоданных сделана по остаточному принципу и to be implemented. В PostGIS она полноценная и работает очень хорошо.
Сделать сравнение было бы доастаочно интересно, попробую найти на это время :)
В MySQL рассматривал Spatial Data, но там насколько помню они еще не готовы к полноценному использованию.
Вот я в 2009 их пробовал, тоже не были готовы. :)
Из опробованных решений еще стоит упоминуть ElasticSearch и плагин geocluster-facet. Ну и эластика умеет агрегацию по сетке делать из коробки (использую геохэши).
Кстати на практике оказалось что использование 50% медианы куда лучше выглядит чем среднее арифметическое.
Возможно, надо будет попробовать.
Сделали кластеризацию этим же методом bookingtroll.com
В процессе реализации возникло ряд проблем: на стыках сетки (особенно экватор, 180 меридиан, 41-й меридиан) работает не очень хорошо.
Если область карты далека от квадрата, то лучше разбивать ее на два или больше квадратных кластеров и получать данные для них отдельно.
Да, с такими проблемама тоже сталкивался, и решение прирено такое же)
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.