Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ
Посмотреть оригинал

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

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

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

Пусть е — действительное число. Через pd обозначим бинарное отношение на [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], Vpnear)•

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

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

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

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

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

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

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

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

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

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

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

Понятно, что если d(V) > 2е, то Q(UmU^l) = к, и если d(V) ^ 2е, то Q{Um и^) a* 2fc - 1, откуда

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

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

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

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

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

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

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

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы