Неоднократно доводилось слышать мнение, что из всех заметающих кривых. именно кривая Гильберта наиболее перспективна для пространственной индексации. Мотивируется это тем, что она не содержит разрывов и потому в некотором смысле “хорошо устроена”. Так ли это на самом деле и при чем здесь пространственная индексация, разберёмся под катом.Читать полностью »
Под катом будем разбираться нужен ли для индексации интервалов специальный индекс, как быть с многомерными интервалами, правда ли что с 2-мерным прямоугольником можно обращаться как с 4-мерной точкой и т.д. Всё это на примере PostgreSQL.
Читать полностью »
Под катом будет небольшая заметка о применении пространственного индекса
на основе zcurve для индексации точечных данных, расположенных на сфере.
А так же bencmark-и для PostgreSQL и сравнение с таким же (но совсем другим)
индексом на R-дереве.
Читать полностью »
Ранее (1, 2) мы обосновали и продемонстрировали возможность существования
пространственного индекса, обладающего всеми плюсами обычного B-Tree — индекса и
не уступающего по производительности индексу на основе R-Tree.
Под катом обобщение алгоритма на трёхмерное пространство, оптимизации и бенчмарки.
Читать полностью »
В прошлый раз мы пришли к выводу, что для эффективной работы пространственного индекса на основе Z-order необходимо сделать 2 вещи:
Вот именно этим мы и займёмся под катом.
Читать полностью »
Индекс на основе Z-order кривой в сравнении с R-деревом имеет массу преимуществ, он:
Впрочем, у индексов на основе Z-order есть и недостаток — сравнительно низкая производительность :). Под катом мы попробуем разобраться с чем связан этот недостаток и можно ли что-то с этим сделать.
Читать полностью »
«Давным-давно, кажется, в прошлую пятницу» автору попалась на глаза статья, в которой сравниваются разные популярные методы индексации небесных объектов. По причине неровного дыхания к этой теме пришлось разбираться в тонкостях и делать выводы.
Вы спросите: «Кому вообще интересны эти небесные объекты?» и даже: «Ну и при чём здесь 2ГИС?» и будете отчасти правы. Ведь методы пространственного индексирования являются универсальной ценностью.
Обычно, имея дело с геоданными, мы работаем с локальной проекцией на плоскость и тем самым отмахиваемся от искажений. В масштабах планеты это сделать труднее — начинают выпирать астрономические проблемы.
Что касается объёмов данных, уже сейчас в OSM более 4 млрд точек и 300 млн дорог. Это соизмеримо с масштабами, характерными для звёздных объектов. Да и помимо всего прочего, звёздные атласы — отличный стенд для разработки и отладки пространственных алгоритмов.
Обещанные тонкости и выводы под катом.
Читать полностью »
Даже не являясь навигатором, 2ГИС собирает и показывает информацию о пробках. Во-первых, это необходимо для построения оптимальных маршрутов, а во-вторых — такие данные очень нужны пользователям в больших городах.
В 2ГИС сервис пробок появился в сентябре 2011 года и сегодня работает в пяти городах (Новосибирск, Санкт-Петербург, Красноярск, Уфа, Казань). В планах на ближайшее будущее — запустить пробки во всех городах-миллионниках.
Под катом история про то, с какими проблемами мы столкнулись и как их решили.
Читать полностью »
Данная статья написана в продолжение серии, повествующей о прототипировании простого и производительного динамического web map сервера. Ранее рассказывалось о том, как в нем устроены пространственные индексы, а так же о том, как можно просто так вот взять и нарисовать пространственный слой. Сейчас мы сделаем это чуть изящнее.
Читать полностью »
Мне всегда нравилось, когда заголовок однозначно говорит о том, что будет дальше, например, «Техасская резня бензопилой». Поэтому под катом мы действительно будем добавлять пространственный поиск к СУБД, в которой его изначально не было.
Читать полностью »
