Стоимость выполнения ок. поиск ближайшего соседа в пропущенном квадри

10

ПРИМЕЧАНИЕ : вопрос был переформулирован в моих ответах: Предполагая теперь, что мы можем найти самых низких предков родного брата за время , может ли ANN действительно выполняться за ?O(1)O(logn)


Квадро - эффективные пространственные показатели. У меня есть головоломка с реализацией поиска ближайшего соседа в сжатой структуре дерева квадрантов, как описано в [2]. (Не вдаваясь в детали, поиск идет сверху вниз по так называемым эквидистантным квадратам, заканчивающимся в хвостовом узле эквидистантного пути. На прикрепленном изображении это может быть любой из узлов на юго-востоке, заполненный точками.)

Чтобы их алгоритм работал, необходимо поддерживать для каждого узла - квадрат с как минимум двумя непустыми квадрантами - указатели для каждого самого нижнего (самого близкого в иерархии) узла-предка в каждом из четырех направлений (север, запад, юг). , восток). Они обозначены зелеными стрелками для западного предка узлов (стрелка указывает на центр квадрата предка).

В документе утверждается, что эти указатели могут обновляться в O (1) во время вставки и удаления точек. Однако, глядя на вставку зеленой точки, мне кажется, мне нужно обновить любое произвольное количество указателей, в данном случае шесть из них.

Я надеюсь на хитрость, чтобы сделать это обновление указателя в постоянное время. Может быть, существует форма косвенного обращения, которую можно использовать?

дерево до (слева) и после (справа) точки вставки

РЕДАКТИРОВАТЬ:

Соответствующий раздел из статьи 6.3, где он гласит: «Если путь имеет изгибы, то в дополнение к самым низким предкам , мы должны также рассмотреть для каждого из направлений самое низкое предок который идет в этом направлении [...] Найти эти квадраты из можно за раз на квадрат, если мы дополнительные указателей с каждым квадратом в указывающем на его ближайших предков для каждого направления . Эти указатели также могут обновляться в раз во время вставки или удаления точки. "log(c/ε)q2dqqO(1)2dQ0O(1)

[2]: Эппштейн Д., Гудрич, М.Т. и Сан, Дж. З. «Квадратное дерево пропуска: простая динамическая структура данных для многомерных данных», в материалах двадцать первого ежегодного симпозиума по вычислительной геометрии, с. 296—305. , 2005.

0__
источник
2
Прошло какое-то время, поэтому я точно не помню, но, перечитывая газету сегодня утром (как в архиве, так и в журнальной версии), я не смог найти, где написано, что мы держим указатели, которые, по вашему мнению, нам нужны. Я думал, что мы сохраняем только указатели родитель-ребенок и перекрестные выборки. Поэтому, возможно, вы могли бы более точно указать на текст в документе, который говорит, что вы говорите, он делает.
Дэвид Эппштейн
2
Привет, Дэвид, спасибо, что заглянул. Поиск ANN является последним разделом (6). Проблема обозначена на рис. 7 (b), что примерно соответствует графику, представленному выше, если q где-то слева внизу. Я отредактировал вопрос, включив в него конкретную часть текста из раздела 6.3. У меня есть некоторые идеи о том, как я могу быть расслаблен с определением equistabbing возможно, но я не уверен, что смогу доказать, что любой альтернативный подсчет не нарушает целевую производительность ...
0__
2
Хорошо, это похоже на проблему. Я обсуждаю это с Гудричем (мы потеряли связь с Sun, который сделал большинство деталей здесь). В настоящее время мы считаем, что на самом деле нам не нужны эти дополнительные указатели (они нам не нужны для приблизительных диапазонов, почему приблизительные значения соседей могут различаться, и алгоритм запроса должен помнить предков, которые он видел на вниз, а не с помощью указателей, чтобы искать их), но мы свяжемся с вами, когда будем немного более уверены в деталях здесь.
Дэвид Эппштейн
2
Отлично! Спасибо большое. По причинам количества символов и расположения я добавлю ответ, который набросает мою «интуитивную идею», может быть, это отправная точка.
0

Ответы:

11

Как и Дэвид, я не знаю, почему Джонатан добавил это замечание о 2-х указателях. Они не нужны. Как упомянул Дэвид выше, существенным свойством является то, что когда мы делаем точечное местоположение для листа v в Q_0, достаточно вспомнить узлы-братья (и их блоки) в дереве пропуска. Когда мы обрабатываем блок из P, мы делаем точку расположения для листового блока, ближайшего к нашей точке запроса, вставляя родственные блоки по мере того, как мы спускаемся. Похоже, это будет примерно таким же, как ваш ответ. Кроме того, эта процедура очень похожа, например, на то, как приблизительное расположение точек делается в следующей статье: Арья, Сунил и Маунт, Дэвид М. и Нетаньяху, Натан С. и Сильверман, Рут и Ву, Анжела Ю., «Оптимальный алгоритм для приближенного поиска ближайшего соседа с фиксированными размерами», JACM, 1998. Действительно,

Майкл Гудрич
источник
Это хорошие новости! Я просто не был уверен, изменит ли добавление братьев и сестер во время шага понижения границу общей стоимости наихудшего случая или нет, но я полагаю, нет. Я просмотрел статью Арьи и др., Но нашел ее гораздо менее доступной, чем ваша газета Quadtree :)
0
5
Вот Это Да! Добро пожаловать в cstheory.SE!
Сянь-Чи Чан 之 之
5

Можно подумать о пропуске дерева квадрантов как о реализации списка пропущенных структур данных, хранящих точки в соответствии с их z-порядком. Это (возможно), по крайней мере, концептуально проще ...

Смотрите главу 2 здесь: http://goo.gl/pLiEO .

И да, предполагая, что вы можете выполнять некоторые базовые операции z-порядка за постоянное время, вы определенно можете выполнять ANN за логарифмическое время. Вышеупомянутая глава также показывает, что нет способа избежать причудливых операций, если кто-то хочет сжать квадри. Обратите внимание, что операция LCA не нужна ...

Сариэль Хар-Пелед
источник
3
Да, и детерминированные варианты очень похожи на 2-3 дерева для одного и того же z-порядка.
Дэвид Эппштейн
Спасибо за ссылку, я действительно видел вашу статью раньше. В любом случае, я не мог эмпирически проверить связь с данным алгоритмом. У меня есть ощущение, что ссылка на лемму 7, которая используется для ограничения числа раундов в теореме 13, может быть недопустимой, поскольку она принимает постоянный радиус , тогда как радиус поиска в ИНС постепенно изменяется, и поэтому множество критических квадратов. ? r
0
Радиус определенного сужается в процессе поиска. Я достаточно оптимистичен, аргумент верен.
Сариэль Хар-Пелед
1

Я также интуитивно чувствую, что можно жить без этих указателей, и, поскольку мне нужно в какой-то момент сохранить все узлы на жестком диске, любые сокращения указателей велики.

Моя идея примерно следующая: кроме точки наилучшего кандидата (листа) , мы также отслеживаем наихудшее расстояние в каждом раунде, . Наихудшее расстояние будет максимальным расстоянием всех углов узла до точки запроса , независимо от того, находится ли внутри квадрата или снаружи.lbestrmaxdist(v,q)qvv

Раунд выглядит так: если пусто, вернуть , если он был. В противном случае delete-min дает текущий в . Инициализируйте в (или установите его в если лучший кандидат еще не был замечен). Сначала проверьте каждый непустой дочерний в . Если этот дочерний элемент является листом, обновите и если необходимо. Если является узлом, вычислите и , причем последнее является наилучшим расстоянием: либо ноль, еслиPlbestp0Q0rmaxlbestp0Q0qlbestrmaxqdist(q,v)dist(q,v)v лежит внутри или кратчайшего расстояния из всех углов до .qqv

Если , забудьте , в противном случае сохраните его. Если число узлов хранятся в , раздвинуть эти узлы на . Конец раунда.dist(q,v)>rmaxq2P

В противном случае продолжайте аналогично исходному поиску: найдите , соответствующий узлу в максимально возможном , и начните с него: опять же, вместо того, чтобы просить равноудаленного потомка спуститься, протестируйте всех потомков в соответствии с предыдущей процедурой то есть пропускайте тех, чье наилучшее расстояние превышает . Если после этого теста ребенок остался, сходите к нему и повторите. Если ребенка не осталось, перейдите к и повторите. Если тест был выполнен в , раунд завершен.qp0QjrmaxQj1Q0

На данный момент я не знаю, гарантирует ли это найти ближайшего соседа в каждом возможном случае, и не работает ли он так же хорошо, как исходный алгоритм. Также, если инициализация достаточна или нет. А какой должен быть приоритет в - все-таки лучшая дистанция?rmaxP


РЕДАКТИРОВАТЬ (апрель 2013 г.)

Теперь я провел больше экспериментов с разъяснением вышеприведенного алгоритма, в котором вместо эквистабирующих узлов используется определение «равноправных» узлов, исходя из того, что при переходе к такому узлу не изменяется область, охватываемая текущей формой запроса экстента. .rmax

К сожалению, можно построить патологические случаи (см. Изображение ниже; точка запроса находится внизу в центре), где производительность снижается до циклов.O(n)

введите описание изображения здесь

0__
источник
0

Теперь я реализовал алгоритм на основе equistabbing, в котором младшие братья и сестры ищутся методом грубой силы (прежде чем пытаться найти вариант O (1)), чтобы проверить максимальное количество раундов, заявленное в теореме 13: .O(ϵ1d(logn+logϵ1))

Я использую «патологический» пример из моего предыдущего ответа. Двумерный корневой квадрат имеет длину стороны 512, где координата центра равна (256, 256). Координаты даны в целых числах, что приводит к прямому . Точки расположены на равном расстоянии по горизонтали через корневой квадрат, а точка запроса находится в точке (256, 511) (обратите внимание, что 512 уже находится за пределами корневого квадрата).ϵ=1v

На рисунке ниже показано полное дерево , и количество точек в этом примере равно 16. синим квадратом обозначают интересные квадраты, которые помещаются в очередь с приоритетами, а цифры в их центре указывают округленное число в которые они толкают. Найденные конечные точки также помечены круглым числом, в котором они учтены. Три прозрачных синих кружка указывают известный радиус NN после 1-го, 2-го и 7-го раунда (ближайший сосед впервые виден в 7-м раунде). Всего 12 раундов (последние 6 только попсовые квадраты из очереди, но не добавляют никаких новых квадратов).Q0

Я запустил этот пример с серией все более крупных корневых квадратов и количеством точек, где расстояние между точками не изменилось (32). Это подтвердило то, что уже интуитивно видно из иллюстрации: алгоритм требует раундов, тогда как теорема 13 с и утверждает, что потребуются только раундов.O(n)d=2ϵ=1O(logn)

Поэтому, если я не пропущу что-то важное, алгоритм не сможет достичь заявленной скорости. Есть комментарии или идеи?

пересечение

0__
источник