Устойчивость канонического эффекта по отношению к е-расширению запроса

е-расширение задачи поиска идентичных объектов.

В данном разделе исследуется задача поиска идентичных объектов в ее геометрической интерпретации, т. е. мы будем рассматривать случай, когда X = Y = [0,1] и отношение поиска pid есть отношение равенства действительных чисел.

Пусть е — действительное число. Через p_d обозначим бинарное отношение на [0,1) х [0,1], определяемое следующим соотношением:

Тип

где вероятностная мера Р задается функцией плотности вероятности р (х), назовем типом ерасширения поиска идентичных объектов. Пусть.

Теорема 54. Пусть I = {[0,1], V, p*_d) — задача типа где V = ⁼⁼ {уь • •., у к} — библиотека, упорядоченная по возрастанию записей, Т — базовое множество, определяемое соотношениями (5.1) —(5.7), т — натуральное число, с — такая константа, чтор (х) ^ с, ?2 (О — функция, определяемая соотношением (2.17),.

тах (1,г (б, V)) ^ ЩГМсМт)) ^.

max (l, г (е, V)) < T (/, JF) < 1 + г (е, V)

при к —У оо. Кроме того, для ИГ U 6 на котором достига

ется верхняя оценка,.

Доказательство. Пусть у' = y;-f е (i = 1, к). Если y'_k ^ 1, то пусть к' = А;, в противном случае пусть к' минимальный номер, при котором у'_к, > 1. Теперь если у_к, > 1, примем у_к, = 1. Пусть V — {yj,…, у*,}.

Пусть т —некоторый натуральный параметр.

Возьмем ИГ Uпостроенный для библиотеки V, описание которого можно найти в доказательстве теоремы 19, т. е. ИГ U^ разрешает первую задачу о близости /' = ([0,1], Vp_near)•.

Обозначим лист, которому приписана запись у (i = 1, к')_у через а. Для каждого i = 1, к' уберем нагрузку с листа а', объявим а. обычной вершиной и выпустим из ребро, которому припишем предикат Конец этого ребра обозначим а, объявим а, листом и припишем ему запись у".

Теперь для каждого г = 1, k^f — 1 если yi+i — yi ^ 2е, то выпустим из листа от" в лист ori+i ребро, которому припишем предикат /^,_у<+1-_с;

Если к¹ < то выпустим из листа а& цепочку из к — к¹ ребер, и для каждого j = 1, к — к' j-му ребру цепочки припишем предикат /^_ty_fc/+i__e, конец j-го ребра объявим листом и припишем ему запись yk'+j-

Полученный ИГ обозначим U_m.

Покажем, что U_m разрешает ЗИП I.

Возьмем произвольный запрос i G [0,1].

Предположим, что х — е > у к- В этом случае к' = к и х > у_к. Поскольку ИГ разрешает первую задачу о близости /' =.

= ([0,1], Vpneari), то запрос х не пройдет ни в одну из вершин.

(г = 1, А:'), и, следовательно,.

Предположим теперь, что х — е ^ у*, т. е. х ^ у_к их ^ у_к,. Тогда поскольку ИГ разрешает первую задачу о близости Г = = ([0,1], V⁷, Pneari), то запрос х пройдет в такую вершину а-, что запись у[ — ближайшая сверху к числу х, или, что-то же самое, запись yi — ближайшая сверху к числу х — е. Далее, если f^_)yi-e (^x) = т. е. если х+е ^ у*, то запрос пройдет в лист а* и запись у* попадет в ответ. Если из листа а* не исходит ребро, то либо % = к, либо y^+i — Ух> 2е, и, значит, уц. 1 нс должна попасть в ответ. Если из листа а* исходит ребро, то мы пройдем в листу а*+| только если ж+е ^ Vi+u и так далее вдоль цепочки, ведущей от листа к листу. Таким образом, и в этом случае

Откуда в силу произвольности х следует, что U_m разрешает ЗИП 7. Подсчитаем объем ИГ U_m.

Понятно, что если d (V) > 2е, то Q (U_mU^_l) = к, и если d (V) ^ 2е, то Q{U_m и^) a* 2fc — 1, откуда.

Подсчитаем сложность ИГ U_m:

Возьмем произвольный запрос х? [0,1]. Как мы показали выше, помимо ребер из U]^ мы просматриваем не более чем Ji (x) 4−1 ребер, причем если d (V) > 2е_} то мы просматриваем не более 1 ребра. Отсюда следует, что.

причем если d (V) > 2е, то T (U_m U^ 1. Следовательно, T (U_m) = = T (U}_n) + r (e, V), откуда с учетом результатов теоремы 19 получаем требуемые оценки для T (U_m) — Нижние оценки следуют из теоремы 4.

Осталось оценить В-сложность ИГ U_m. Поскольку для любого х € G [0,1] T (U_m, x) ^ Т^х) + 1 + Мх)|, то.

Теорема доказана.

Следствием теоремы 54 является следующее утверждение.

Утверждение 3. Канонический эффекта устойчив по отношению к е-расширению запроса для задачи поиска идентичных объектов.