Анатомия KD-Деревьев

[Azone]

Очень интересная статья. Всё ясно и понятно)

[Dark_Daiver]

А можете подробней рассказать про то, как народ борется с случаями когда нужно найти ближайшую точку к точке которая сильно удалена от множества точек для которых построено дерево? (Тот самый случай когда O(N) или около того)

[IvanKamynin]

На счет KD-Дерева, надо хорошенько подумать, что можно такого сделать чтобы улучшить ситуацию. Но, отмечу: KD-Дерево, одна из многих структур данных, которая позволяет решить задачу поиска ближнего. Существуют еще, например, VP-Деревья. Наверное, я опишу подробно и этот вид деревьев(статьи так через две, ведь еще на подходе возможное описание реализации KD-Tree GPU) и проведу сравнительный анализ. Пока подумаю над вашим вопросом.

[Dark_Daiver]

Окей, спасибо!
Просто меня интересуют случаи когда точек несколько миллионов, и поисков примерно столько же и искать и строить дерево нужно довольно быстро. Желательно не тратя много памяти. Как я понимаю, KD-tree для таких случаев подходит довольно хорошо (за вычетом случая описанного выше)

[eiennohito]

Можно по исходному множеству построить диаграмму Вороного (n log n). Тогда попадание в одну из областей будет значить близость к соответствующей этой области точке. Дальше задача сводится как найти многоугольник, в который «упала» наша точка. Если разбить диаграмму вертикальными и горизонтальными линиями на сегменты (n), то бинарным поиском можно будет найти эту подобласть (log n).

[IvanKamynin]

Иногда мне кажется, что мои мысли читают. В данном случае, чтение заключается в том, что я тружусь над описанием одного из алгоритмов построения диаграммы Вороного(на Хабрахабре рассказывалось только лишь о алгоритме Форчуна, а он — не шибко хорошо параллелится)

[eiennohito]

Ну здесь, как говорится мопед не мой. Этот алгоритм нам рассказывал на паре по вычислительной геометрии препод.

[Dark_Daiver]

Из того что я слышал про диаграммы Вороного (сам я не пытался разобраться), они могут в некоторых случаях требовать довольно много памяти, и построение такой диаграммы на 1 000 000 — 10 000 000 точек может занимать по полминуты. Для меня это довольно много.
Если я ошибаюсь, то буду рад об этом узнать =)

[oYASo]

Отличная статья!

Стоит, наверное, еще упомянуть про R-деревья, которые решают схожую проблему, но несколько другим способом (не пространство разбивают на прямоугольники, а объекты распределяются по прямоугольникам, возможно, пересекающимися). Так как они сбалансированы, при часто меняющихся данных (добавление дополнительных объектов) не нужно перестраивать все дерево, что очень положительно влияет на скорость.

Хорошая реализация R-деревьев лежит в boost.

[IvanKamynin]

Я постараюсь рассказать обо всех типах деревьев и сравнить полученные результаты. Тут проблема в том, что конечно, нужно не только писать теорию, но еще писать и код., тестировать его и фиксить баги :)
// Не люблю теорию без практики.

[oYASo]

Тема очень нужная и актуальная, так что будем ждать!

Сразу скажу, что не обращайте внимание на довольно низкие хабро оценки статей — с техническими статьями, увы, всегда так. Зато теперь, если вбить в гугле «kd-деревья», ваша статья в ТОП-5, и по ней скоро натурально будут учиться новые разработчики.