авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 |

«Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный электротехнический ...»

-- [ Страница 2 ] --

a. Основной проблемой индексов, основанных на RD-деревьях, является неточность поиска.

b. При поиске последовательностей по фрагменту с использованием RD деревьев не учитывается порядок следования элементов.

c. Почему возникают «ложные попадания» при поиске по RD-дереву?

Как можно уменьшить их количество? Изучение причин «ложных попаданий» необходимо для разработки мер их минимизации.

ГЛАВА 2. Разработка модификации структуры RD-деревьев и эффективных алгоритмов поиска с ней 2.1 Асимптотический анализ алгоритмов работы с RD-деревом Как было сказано выше, для достижения цели диссертационной работы используются индексы на основе RD-деревьев, предложенных Д. Хеллерстейном в работе [60] и представляющих собой разновидность R-деревьев [58], адаптированную для поиска наборов элементов.

В работе Гуттмана [58], где впервые была предложена структура R-деревьев для индексации пространственных данных, было предложено несколько алгоритмов обновления дерева за O(log(n)) обращений к внешней памяти, где n – количество индексируемых объектов. Такая же сложность обновления присуща и RD-деревьям. В работе Скворцова [43] доказано, что временная сложность построения R-дерева (а значит и RD-дерева) в наихудшем случае для n индексируемых элементов составляет:

T = O(n·log(n)) (2.1) Данная оценка совпадает с временной сложностью построения B-деревьев в виду похожей древовидной структуры.

Требования к памяти у RD-деревьев тоже такие же, как у B- и R-деревьев, и составляют O(n).

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

Однако в 2008 году появилась модификация R-деревьев – PR-деревья, обладающая не только быстрым поиском на реальных пространственных данных, но и обладающая хорошей асимптотикой алгоритма поиска в наихудшем случае [50]. В узлах PR-деревьев по-прежнему хранятся охватывающие прямоугольники для хранимых геометрических объектов, но, в отличие от классических R деревьев, PR-деревья еще содержат так называемые приоритетные листовые узлы, которые располагаются на всех уровнях дерева, а не только на самом нижнем. В этих приоритетных «листьях» хранятся экстремальные прямоугольники – те, что находятся в непосредственной близости к четырем границам (верхней, нижней, правой и левой) прямоугольника родительского узла.

Используя эти приоритетные листовые узлы PR-дерева, авторам работы [50] удалось добиться следующей временной сложности поиска в наихудшем случае:

T O(n11 / d ), (2.2) где n – количество индексируемых объектов, d – размерность прямоугольников, хранимых в узлах PR-дерева.

К сожалению, подобная модификация R-деревьев неприменима к RD деревьям, поскольку при индексации последовательностей элементов нет аналогов экстремальным прямоугольникам, хранимым в приоритетных листовых узлах.

2.1.1 Анализ сложности поиска фрагмента в последовательностях по RD дереву для среднего случая Временная сложность поиска по RD-дереву, в наихудшем случае составляющая O(n), плохо отражает работу индекса на реальных данных. В существующих работах по RD-деревьям нет оценок сложности поиска для среднего случая, поэтому такой анализ выполнен в данном разделе.

Чтобы лучше представить работу алгоритма поиска фрагмента в последовательностях по RD-дереву, следует обратиться к его блок-схеме, приведенной в приложении А. Из алгоритма видно, что асимптотика O(n) обусловлена тем, что в худшем случае придется обойти все узлы RD-дерева.

Предполагается, что вероятность «ложных попаданий» при поиске равна единице, т.е. условие включения сигнатур друг в друга, указанное на рисунке А.1, будет всегда выполняться. Алгоритм проверки этого условия приведен на рисунке 2.1. В среднем же случае на реальных данных вероятность «ложных попаданий», конечно же, на много меньше единицы.

Сигнатуры фрагмента (SF), и узла дерева (Si) Обход битов из SF, пока не закончились Да Бит в SF = 1, а бит в Si = 0?

Синатура SF не Нет включена в Si Обход битов из SF Синатура SF включена в Si Рисунок 2.1 – Условие включения сигнатур друг в друга Лемма 2.1 Для поиска фрагмента в последовательностях с использованием n RD-дерева в среднем случае требуется O( ) операций обращения к внешней log( n) памяти.

Доказательство. Пусть имеется построенное для RD-дерево, n последовательностей элементов. Рассматривается низкоселективный поисковый запрос фрагмента, т.е. количество успешных результатов поиска невелико и ограничено константой. Все остальные индексируемые последовательности потенциально могут иметь такие сигнатуры, которые приведут к обращению к ним в результате «ложных попаданий», т.е. лишних спусков по узлам RD-дерева.

Таким образом, сложность поиска ограничена сверху количеством «ложных попаданий», которое в свою очередь ограничено количеством узлов дерева.

Узлы RD-дерева, как и R-дерева, соответствуют страницам внешней памяти [43]. Следовательно, переходы между узлами дерева соответствуют обращениям к внешней памяти. Каждый внутренний узел RD-дерева содержит определенное константное количество ссылок на поддеревья, а каждый листовой узел – константное количество ссылок на строки таблицы БД. Поэтому в асимптотике получаем, что количество узлов в дереве составляет O(n), и этой величиной ограничено максимальное количество «ложных попаданий».

Однако вероятность «ложного попадания» P при поиске на реальных данных меньше единицы и равна определенному значению, зависимому от n.

Получаем, что асимптотика сложности поиска составляет:

T = O(P·n) (2.3) Каждый внутренний узел в RD-дереве при срабатывании в нем условия исключения поддерева из поиска, исключит такое количество «ложных попаданий», которое смогут исключить в сумме все потомки данного узла.

Отметим, что для всех этих потомков исключаемое ими количество «ложных попаданий» будет одинаковое в виду сбалансированности RD-дерева по высоте.

Сигнатура каждого узла RD-дерева является неким объединением сигнатур его потомков (побитовое сложение сигнатур, основанных на блюмовских фильтрах). Алгоритмы построения RD-дерева обеспечивают минимальную степень взаимного пересечения сигнатур узлов одного уровня [43], которую можно считать константой. Следовательно, можно допустить, что «вес»

сигнатуры узла равен сумме «весов» сигнатур дочерних узлов. Очевидно, что данный «вес» сигнатуры – величина обратная вероятности исключения соответствующего поддерева из поиска.

Учитывая, что количество потомков какого-либо внутреннего узла RD дерева равно p (порядок дерева), получаем, что срабатывание условия исключения поддерева из поиска с одной стороны в p раз маловероятнее, чем для дочерних узлов, но при этом во столько же раз больше исключает «ложных попаданий». Таким образом, каждый уровень в структуре RD-дерева вносит одинаковый вклад в исключение «ложных попаданий». Следовательно, вероятность ложных попаданий P линейно зависит от количества уровней в RD дереве (зависимость обратная). Поскольку количество уровней в дереве ограничено величиной O(log(n)), то P будет ограничено обратной величиной:

P O( ) (2.4) log( n) Используя выражение (2.3), получаем, что временная сложность поиска фрагмента в последовательностях с использованием RD-дерева в среднем случае составляет:

n T O( ) (2.5) log( n) Лемма доказана.

Данная асимптотическая оценка для среднего случая более точно отражает сложность поиска по RD-дереву на реальных данных, хотя вс же данная оценка несколько завышена.

2.2 Анализ причин «ложных попаданий» при поиске по RD-дереву При анализе структуры индексов на основе RD-деревьев было сказано, что «ложные попадания» при поиске являются следствием коллизий хеширования при построении узлов дерева. В результате чего для различных последовательностей элементов могут быть одинаковые сигнатуры, что приводит к ошибочному чтению узлов дерева, т.е. страниц внешней памяти. Кроме того, для исключения «ложных попаданий» требуются дополнительные чтения страниц внешней памяти для получения сохраненных в БД последовательностей и их сравнения с искомым фрагментом. Таким образом, на существенных объемах данных количество «ложных попаданий» может быть настолько большим, что сделает скорость поиска по индексу неприемлемо низкой.

Проанализируем причины «ложных попаданий» более подробно, учитывая особенности блюмовских фильтров, хранимых в сигнатурах узлов RD-дерева. В сигнатурах каждому значению элементов индексируемых последовательностей соответствует 1 бит – признак наличия элементов с соответствующим значением. Фактически это означает, что последовательности будут иметь различные сигнатуры, только если они различаются составом элементов. Если же состав элементов одинаковый, то сигнатуры последовательностей будут равны, даже если последовательности имеют разное количество элементов и/или различное их расположение. Например, числовые последовательности {1,2,3} и {3,1,2,2,1,3,1} будут иметь одинаковую сигнатуру, в которой установлены биты для значений 1, 2 и 3. Очевидно, что на реальных данных таких «совпадений»

будет огромное количество.

Таким образом, в результате анализа было выяснено, что к наиболее весомым причинам ложных попаданий при поиске фрагментов в последовательностях с использованием RD-деревьев относятся следующие:

1. Не учитывается количество одинаковых элементов в индексируемых последовательностях.

2. Не учитывается порядок расположения элементов.

Такая структура узлов RD-деревьев интуитивно понятна. Назначение сигнатур в том, чтобы превратить наборы элементов различной длины в битовые массивы фиксированной длины, тем самым сократив размер индекса и достигнув линейной асимптотики расходования памяти O(n). Поэтому простое добавление в сигнатуры всей недостающей информации будет непременно означать увеличение размера RD-дерева. В данной работе предложен способ добавления в сигнатуры узлов RD-дерева дополнительной информации, не увеличивая при этом размер индекса.

2.3 Математическая оценка количества «ложных попаданий» при поиске по RD-дереву В разделе 2.1.1 было сказано, что «ложные попадания» происходят с определенной вероятностью, а также была получена асимптотика сложности n поиска по RD-дереву для среднего случая, которая составила O( ). Однако log( n) данная оценка все же несколько завышена.

Чтобы точнее учесть количество «ложных попаданий», возникающих на реальных данных, в данном разделе рассчитаем теоретическое относительное количество «ложных попадании» при поиске по RD-дереву, т.е. количество «ложных попаданий» в расчете на один успешный результат поиска. Данное количество «ложных попаданий» будем определять следующим образом:

Pчтения _ стр K ложн _ попадании_ на _ 1 _ успех 1, (2.6) Pпопадания где Pчтения_стр - вероятность чтения страницы внешней памяти в листовом узле дерева для проверки результата поиска и возможного исключения «ложного попадания», Pпопадания - вероятность успешного исхода поиска (попадания).

В выражении (2.6) учитывается следующее соображение. Во сколько раз вероятность чтения страницы в листе больше, чем вероятность успешного результата поиска, столько потребуется обращений к внешней памяти для нахождения одной последовательности. Из этого количества обращений только одно «полезное», т.е. то, которое действительно приведет к нахождению последовательности на считанной странице, а все остальные обращения – это «ложные попадания». Например, отсутствие «ложных попаданий» согласно (2.6) будет в том случае, когда Pчтения_стр равна Pпопадания, что соответствует действительности.

Таким образом, для определения теоретического относительного количества «ложных попаданий» необходимо вычислить значения вероятностей Pчтения_стр и Pпопадания.

Для выполнения такой оценки количества «ложных попаданий»

математически смоделируем реальные данные для среднего случая. Данный результат поможет оценить масштаб проблемы, а также значимость выполненной в данной главе модификации структуры RD-дерева.

2.3.1 Вычисление количества комбинаций последовательностей с повторяющимися элементами Поскольку объектом данного диссертационного исследования являются последовательности, в которых важен порядок расположения элементов, то для их формализации воспользуемся соответствующими комбинаторными соединениями – размещениями без повторений [15,47].

Определение 2.1 Размещения без повторений – комбинаторные соединения, составленные из m элементов, каждый из которых может принимать k возможных значений. При этом два соединения считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.

m Количество размещений без повторений обозначается Ak, произносится «а из k по m», и рассчитывается по формуле:

k!

Ak m (2.7) (k m)!

Однако последовательности на реальных данных могут иметь повторения, но их количество, как правило, ограничено. Поэтому для корректности математической модели реальным данным будем учитывать определенное ограниченное количество повторений в последовательностях.

Пусть имеются произвольные последовательности элементов длиной m.

Каждый элемент может принимать k возможных значений. В каждой последовательности могут присутствовать повторения. Для упрощения оценки принимаем допущение, что в последовательностях может повторяться только одно какое-либо значение в среднем раз на каждую (в разных r последовательностях может повторяться разное значение). Например, для числовой последовательности {32,54,12,45,54,6,1,54,9,0} длина m равна 10, а величина r (для элемента 54) равна 3. Определим, сколько можно составить различных последовательностей (комбинаторных соединений), удовлетворяющих данным условиям. Рассмотрим отдельно случай, когда все повторяющиеся элементы не являются соседними, т.к. это потребуется нам далее. Для искомой величины введем обозначение Ak, r, а для случая только отдельно стоящих m * повторений – Ak,r.

m Выделяются два различных случая: k m и k m.

Рассмотрим первый случай, когда количество возможных значений элементов строго меньше длины последовательностей (k m). В таком случае все возможные комбинации обязательно будут содержать повторения, минимальное количество которых назовем естественным количеством повторений и обозначим r` (эр штрих).

r` m k 1 (2.8) Для упрощения оценки в рассматриваемом случае введем ограничение, что r не может быть меньше r`, то есть r r`. Это означает, что разница m-k не может превышать значение r-1. Данное ограничение считаем допустимым, т.к. на реальных данных количество возможных значений k, как правило, не может быть намного меньше длины индексируемых последовательностей m.

В данном случае, учитывая введенное ограничение, получаем, что во всех последовательностях один из элементов обязательно повторяется r раз.

Обозначим количество таких комбинаций AП k, r, а для случая только отдельно m * стоящих повторений – AП k,r. Данным величинам будут равны искомые m величины в рассматриваемом случае k m, то есть:

Аk, r АПk, r, m m (2.9) * * Аk, r АПk, r m m (2.10) * Величины АПk, r и AП k,r равны произведению следующих величин:

m m Количество размещений без повторений для оставшейся части элементов, кроме r, длинной m-r элементов, принимающих k-1 возможных значений.

m Используя выражение (2.7), получаем, что данное количество равно Ak 1r.

Количество различных вариантов расположения r повторяющихся элементов в последовательности из m элементов. Обозначим данную величину * V m, r, а для случая только отдельно стоящих повторений – V m,r.

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

Таким образом, количество комбинаций с обязательными r повторениями равно:

АПk, r Ak r V m, r k, m m (2.11) * * АПk, r Ak r V m, r k m m (2.12) * Теперь вычислим величины V m, r и V m,r. Количество вариантов расположения r различных элементов по m позициям равно:

V m, r m (m-1 ) (m-2 ) … (m-(r-1 )) (2.13) То есть для первого элемента количество вариантов расположения равно m, для следующего – m-1, и так далее. Однако, выражение (2.13) учитывает то, что все r элементов разные. Необходимо же рассчитать количество различных вариантов расположения одинаковых элементов. Используя (2.13) для одинаковых элементов, некоторые варианты будут идентичны. Следовательно, выражение (2.13) необходимо адаптировать для одинаковых элементов. На рисунке 2.2 приведен пример всех способов расположения повторений согласно (2.13), где вычеркнуты повторяющиеся варианты расположения элементов.

k= 1 m=4 1 2 r= 1 r` = 2 1 2 2 1 2 2 Рисунок 2.2 – Пример всех способов расположения повторений Экспериментальным путем было установлено, что при увеличении количества повторяющихся элементов r на 1 количество различных вариантов расположения повторений, рассчитанное по формуле (2.13), снижается в r раз за счет появления повторяющихся расположений. Таким образом, уточненное выражение для V m, r примет вид:

1 1 V m, r m (m-1 ) (m-2 ) … (m-(r-1 )), (2.14) 2 3 r r ( (m i)) m, r (2.15) V i i Теперь учтем случай отдельно стоящих повторений. Учитывая, что максимальная длина группы повторяющихся элементов равна r (все повторения расположены подряд), то для того чтобы все повторения были расположены отдельно друг от друга, достаточно в каждую последовательность добавить r- дополнительных элементов, которые бы «разбивали» группы повторений на части. Другими словами, количество различных вариантов раздельного расположения повторений, равно количеству различных вариантов любого расположения повторений в последовательностях, длина которых на r-1 меньше.

* V m, r V m (r 1),r (2.16) Отметим, что варианты раздельного расположения повторений возможны только при выполнении условия m-r r-1, т.е. когда длина оставшейся уникальной части последовательностей не меньше минимального количества элементов, необходимого для разбиения группы повторений длиной r на отдельно стоящие повторения. Например, для последовательностей, имеющих длину m = 6, не может быть ни одного варианта расположения четырех повторений (r = 4), в которых бы все четыре повторяющихся элемента были расположены отдельно.

* Таким образом, получаем итоговое выражение для V m,r :

V m ( r 1),r, если (m r r 1) m, r *, (2.17) V 0, если (m r r 1) В результате подстановки полученных выражений (2.15) и (2.17) в формулы (2.11) и (2.12), а те в свою очередь в (2.9) и (2.10), получаем итоговые выражения * для искомых величин Аk, r и Ak,r в рассматриваемом случае k m:

m m m Аk, r Ak 1r V m, r k, m (2.18) * * Аk, r Ak r V m, r k, m m (2.19) m где Аk - количество размещений без повторений, рассчитываемое по формуле (2.7), V m, r - количество различных вариантов расположения повторений, рассчитываемое по формуле (2.15), * V m,r - количество различных вариантов расположения не соседних повторений, рассчитываемое по формуле (2.17).

Рассмотрим второй случай, когда количество возможных значений элементов не меньше длины последовательностей (k m).

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

Количество размещений без повторений длиной элементов, m m принимающих k возможных значений ( Аk ).

Количество комбинаций, в которых один из элементов обязательно * повторяется r раз ( АПk, r и AП k,r ). Данное количество комбинаций вычислено m m при рассмотрении предыдущего случая.

Таким образом, получаем итоговые выражения для искомых величин Аk, r m * и Ak,r в рассматриваемом случае k m:

m m Аk, r Аm Ak 1r V m, r k, m (2.20) k * * Аk, r Аm Ak r V m, r k, m m (2.21) k Для учета рассмотренного выше первого случая k m, когда первое m слагаемое отсутствует, введем дополнительную величину Ak («а из k по m шрих»), которая равна:

Ak, если (k m) m m Аk (2.22) 0, если (k m) В результате получили итоговые выражения для искомых величин Аk, r и m * Ak,r для любых значений k и m:

m m Аk, r Аk Ak r V m, r k, m m (2.23) m m* * Аk, r Аk Ak r V m, r k, m (2.24) m где Аk - количество размещений без повторений, рассчитываемое по формуле (2.7), m m Аk - количество размещений без повторений Аk, либо 0, рассчитываемое по формуле (2.22), V m, r - количество различных вариантов расположения повторений, рассчитываемое по формуле (2.15), * V m,r - количество различных вариантов расположения не соседних повторений, рассчитываемое по формуле (2.17).

Полученная математическая модель реальных данных принимается, как адекватная и применимая для теоретической оценки количества «ложных попаданий» при поиске по RD-дереву, поскольку она сравнительно хорошо соотносится с реальными данными.

2.3.2 Оценка количества «ложных попаданий» при поиске по RD-дереву В данном разделе вычислим относительное количество «ложных попаданий» при поиске фрагмента в последовательностях по RD-дереву, используя смоделированные в предыдущем разделе реальные данные.

Рассмотрим поиск фрагмента из f различных элементов в текстовом поле БД со следующими типовыми параметрами:

средняя длина индексируемых последовательностей m = 50, количество возможных значений элементов k = 60 (например, это может быть русский алфавит в двух регистрах, кроме заглавных Ь, Ъ, и т.д.), среднее количество возможных повторений какого-либо значения r = (например, это может быть два слова с удвоенным символом).

Оценку выполним для поиска фрагмента из трех элементов (f = 3), что является достаточно частым случаем при поиске по фрагменту.

Для вычисления количества «ложных попаданий» в расчете на один успешный результат поиска рассчитаем вероятность чтения страницы внешней памяти в листовом узле Pчтения_стр и вероятность успешного исхода поиска Pпопадания.

Вначале определим количество возможных последовательностей элементов, которые удовлетворяют параметрам рассматриваемого поиска. Обозначим это количество как Kпопаданий. Это количество последовательностей, в которых обязательно содержится заданный искомый фрагмент длиной f. При определении Kпопаданий учитываем следующие аспекты:

1. Искомый фрагмент не содержит одинаковых элементов (по условию).

2. Фрагмент попадает либо в последовательность с повторениями, либо в последовательность без повторений.

3. Если фрагмент попадает в последовательность с повторениями, то с вероятностью f / k один из его элементов будет иметь то же значение, что и группа повторяющихся элементов, а с вероятностью (k - f) / k искомый фрагмент не будет иметь значения, равного повторяющимся элементам.

4. Количество возможных расположений искомого фрагмента длиной f в последовательностях длиной m равно m - f + 1.

Общее количество последовательностей вычисляется по формуле (2.23) и равно Аk, r. Для рассматриваемого примера поиска данное количество будет m равно 3,100362 1077, из них количество последовательностей с повторениями 3,077432 1077. Определим АПk, r, вычисленное по форме (2.11) равно m вероятности попадания искомого фрагмента в последовательности с повторениями (обозначим как Pс_повт) и в последовательности без повторений (обозначим Pбез_повт). В данном случае сумма этих вероятностей равна 1.

АПk, r m Pс _ повт, (2.25) Аk, r m Аk, r АПk, r m m Pбез _ повт (2.26) Аk, r m Если допустить, что фрагмент попадает в последовательности с повторениями, то количество последовательностей, удовлетворяющих поисковым параметрам, будет равно:

k f f АПk ff, r 1 АПk ff, r ) m m K попаданий_ с _ повт ( (2.27) k k (m f 1 ) Если же допустить, что фрагмент попадает в последовательности без повторений, то количество последовательностей, удовлетворяющих поисковым параметрам, будет равно:

m K попаданий_ без _ повт An f f (m f 1 ) (2.28) Таким образом, общее количество возможных последовательностей, удовлетворяющих параметрам рассматриваемого поиска, будет равно:

K попаданий Pс _ повт K попаданий_ с _ повт (2.29) Pбез _ повт K попаданий_ без _ повт В рассмотренном примере поиска данное количество будет равно 5,581505 1073. Таким образом, можно вычислим вероятность положительного исхода поиска.

K попаданий Pпопадания (2.30) Аk, r m Для рассмотренного примера поиска Pпопадания 0,00018003.

Теперь определим для поиска этого же фрагмента вероятность чтения страницы внешней памяти в листовом узле (Pчтения_стр), т.е. вероятность успешного прохождения сигнатурных проверок на уровне листа RD-дерева.

Сигнатуры в узлах листового уровня построены непосредственно для хранимых в БД последовательностей, имеющих длину m. Если фрагмент пройдет проверку сигнатуры на листовом уровне, то проверки на всех предыдущих уровнях он гарантированно пройдет (благодаря иерархичности сигнатур), и это приведет к обращению к внешней памяти. Так как сигнатуры хранят только признак присутствия/отсутствия для каждого значения элементов отображаемых ими последовательностей, то фактически нужно определить вероятность нахождения f элементов с конкретными различными значениями в индексируемых последовательностях. Для этого применим теорему умножения вероятностей:

[33] P(1 2... f) P(1 ) P ( 2 ) P 2( 3 )... P 2... f 1(f) (2.31) 1 1 Учитывая, что вероятность нахождения элемента с конкретным значением в последовательности длиной m различных элементов, принимающих k возможных значений, равна m / k, то, используя (2.31), получаем вероятность нахождения f различных элементов в такой последовательности:

f mi k i Pkm ( f ) (2.32) i При определении вероятности чтения страницы в листовом узле RD-дерева учитываем следующее:

1. Искомый фрагмент обязательно попадает либо в последовательность с повторениями, либо в последовательность без повторений.

2. Если фрагмент попадает в последовательность с повторениями, то с вероятностью f / k один из его элементов будет иметь то же значение, что и группа повторяющихся элементов, а с вероятностью (k - f) / k искомый фрагмент не будет иметь значения, равного повторяющимся элементам.

3. Если один из элементов искомого фрагмента пересекается с группой повторяющихся элементов, то вероятность нахождения такого элемента в сигнатуре равна 1.

Если допустить, что фрагмент попадает в последовательности с повторениями, то вероятность обращения к странице будет равна:

k f f Pkm r 1 ( f 1) 1 Pkm r 1 ( f ) Pчтения _ стр _ с _ повт (2.33) k k Если же допустить, что фрагмент попадает в последовательности без повторений, то вероятность обращения к странице будет равна:

Pчтения _ стр _ без _ повт Pnm ( f ) (2.34) Таким образом, итоговая вероятность чтения страницы внешней памяти в листовом узле RD-дерева равняется:

Pчтения _ стр Pс _ повт Pчтения _ стр _ с _ повт (2.35) Pбез _ повт Pчтения _ стр _ без _ повт В рассмотренном примере поиска Pчтения _ стр 0,48137113.

Таким образом, используя формулу (2.6), получаем, что при поиске фрагмента в последовательностях по RD-дереву относительное количество «ложных попаданий» в расчете на один успешный результат поиска для рассматриваемого примера поиска равно K ложн _ попадании_ на _ 1 _ успех 2672. При расчете использована математическая модель реальных данных, описанная в предыдущем разделе.

2.4 Модификация структуры для минимизации «ложных RD-дерева попаданий»

В разделе 2.2 в результате анализа причин «ложных попаданий» при поиске последовательностей по RD-дереву были выявлены две основные причины:

1. Не учитывается количество одинаковых элементов.

2. Не учитывается порядок расположения элементов.

Для устранения этих причин в данном разделе внесены изменения в структуру сигнатур RD-деревьев.

В ходе модификации структуры узлов RD-деревьев выполнено увеличение той части сигнатуры, которая приходится на каждое значение элементов последовательностей (1 бит). Из соображений удобства программной реализации, данная часть увеличена с одного бита до одного байта. Таким образом, в битовом массиве (блюмовском фильтре), который представляет собой сигнатура, для каждого значения элементов индексируемых последовательностей будет храниться 8 бит. Это позволят использовать несколько хеш-функций при построении блюмовских фильтров вместо одной, что приведет к более полному описанию сигнатурами индексируемых данных, а, следовательно, к снижению количества «ложных попаданий». Для удобства обозначения данной однобайтовой части сигнатуры введем следующее определение.

Определение 2.2 Сигнатурный элемент – однобайтовая часть сигнатуры, хранящая необходимую информацию для одного значения элементов последовательности, отображаемой сигнатурой.

На рисунке 2.3 показано изменение узла RD-дерева, вызванное увеличением размера сигнатурного элемента.

Рисунок 2.3 – Изменение узла RD-дерева после увеличения сигнатурного элемента Такое изменение структуры сигнатур не изменяет алгоритмов работы с RD деревом. Отличие касается только модификации единственной хеш-функции, которая вместо установки 1 бита в случае принадлежности элемента последовательности будет устанавливать 8 бит. Таким образом, предложенная модификация не изменяет асимптотических характеристик поиска и построения RD-дерева, она призвана снизить вероятность «ложных попаданий» при поиске.

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

Хеллерстейном [60] при разработке RD-деревьев. Данный алгоритм предполагает использование в сигнатурах битовых массивов фиксированной длины и соответствующего предопределенного диапазона позиций битов. Из данного диапазона хеш-функция выбирает позицию для конкретного значения элемента.

Это приводит к тому, что сигнатуры достаточно часто содержат определенное количество неиспользуемых младших и старших битов. Предложенный в данной диссертационной работе подход предполагает использование сигнатур переменной длины в узлах RD-дерева, исключив из блюмовских фильтров неиспользуемые младшие и старшие биты. Предложенный подход применен для уменьшения размера RD-дерева в четвертой главе при реализации индекса для СУБД PostgreSQL. В результате удалось не только полностью компенсировать увеличение размера индекса, но даже его уменьшить.

Для удобства обозначения сигнатур введем следующий синтаксис:

{(Значение1,Сигн.элемент1)…(Значениеq,Сигн.элементq)} Данный синтаксис избавляет от технических подробностей использования хеш-функций, связывающих значения элементов с сигнатурными элементами.

2.4.1 Этап 1: добавление в индекс информации о количестве одинаковых элементов в последовательностях Для устранения первой причины «ложных попаданий» в сигнатуры RD деревьев добавляется информация о количестве одинаковых элементов в индексируемых последовательностях.

Для каждого значения элементов в сигнатуре вместо признака присутствия будет храниться количество элементов с соответствующим значением. При этом 8-ми битовый сигнатурный элемент будет интерпретироваться, как двоичное представление количества, а не как признак. Таким образом, максимальное учитываемое количество одинаковых элементов в последовательности будет равно 28, т.е. 256. Такого максимального количества одинаковых элементов будет вполне достаточно для индексации последовательностей среднего размера (текстовые поля в БД, числовые массивы и т.п.), поскольку в реальных данных количество повторяющихся элементов в последовательностях меньше, чем 256.

Структура сигнатурного элемента при такой модификации приведена на рисунке 2.4.

7 6 5 4 3 2 1 Двоичное представление количества элементов с данным значением Рисунок 2.4 – Структура сигнатурного элемента после первого этапа модификации Данная модификация сигнатур означает, что мы заменили хеш-функцию, с помощью которой строятся блюмовские фильтры для последовательностей элементов. Теперь данная единственная хеш-функция устанавливает 8 бит для каждого значения элементов в соответствии с количеством таких элементов в отображаемой последовательности.

На рисунке 2.5 приведен пример RD-дерева с модифицированными сигнатурами для индексации числовых последовательностей.

Числовые последовательности 1) 225,225,227,164, 2) 172,160,172, {(225,2)(227,1)(164,1)(160,2)(172,2)} {(162,1)(32,1)(171,1)(165,1)(225,1)(226,1)} 3) 162,32,171,165, Ссылка на поддерево 1 Ссылка на поддерево 4) 225,162,165, Сигнатура {(225,2)(227,1)(164,1)(160,1)} {(172,2)(160,2)} {(162,1)(32,1)(171,1)(165,1)(225,1)} {(225,1)(162,1)(165,1)(226,1)} Ссылка на 225,225,227,164,160 Ссылка на 162,32,171,165,225 Ссылка на 225,162,165, Ссылка на 172,160,172, Рисунок 2.5 – Пример RD-дерева после первого этапа модификации При внесении таких изменений в структуру сигнатур RD-дерева соответствующим образом изменился алгоритм проверки сигнатур при поиске.

Теперь он заключается не просто в проверке признака наличия каждого значения элементов, а в анализе количества каждого значения. Измененный алгоритм проверки включения сигнатур друг в друга, отмеченный в общем алгоритме поиска по RD-дереву в приложении А, приведен на рисунке 2.6.

В результате данная модификация RD-деревьев увеличивает скорость поиска фрагментов с повторениями, например, {225,225,227,164,160} или {172,160,172,160}. Из поиска в таких случаях исключаются поддеревья, в сигнатурах которых для какого-либо значения элементов количество меньше, чем в сигнатуре искомого фрагмента.

Например, при поиске фрагмента {1,2,3,1}, сигнатура которого равна {(1,2)(2,1)(3,1)}, будет исключено из рассмотрения поддерево, имеющее сигнатуру {(1,1)(2,1)(3,1)}, хотя все значения элементов там присутствуют. При хранении в сигнатурных элементах только признака данная проверка была бы пройдена, и в поиск попало бы поддерево, не удовлетворяющее поиску.

Сигнатуры фрагмента (SF), и узла дерева (Si) Обход сигнатурных элементов из SF, пока не закончились Да Количество в SF количества в Si?

Синатура SF не Нет включена в Si Обход сигнатурных элементов из SF Синатура SF включена в Si Рисунок 2.6 – Условие включения сигнатур друг в друга после первого этапа модификации Математическая оценка количества «ложных попаданий» после первого этапа модификации Выполним математическую оценку относительного количества «ложных попаданий» в расчете на один успешный результат поиска при использовании модифицированных сигнатур RD-дерева.

Рассмотрим поиск фрагмента из f элементов, который содержит rf повторений подряд, и оценим количество «ложных попаданий» при таком поиске.

Аналогично оценке, выполненной в разделе 2.3.2 для оригинальных RD-деревьев, рассматривать будем пример поиска в текстовом поле БД с типовыми параметрами:

средняя длина последовательностей m = 50, число возможных значений элементов k = 60, число возможных повторений в последовательностях r = 4.

При этом оценку выполним для поиска фрагмента из трех элементов (f = 3), что является достаточно частым случаем при поиске по фрагменту. Количество последовательных повторений элементов в искомом фрагменте rf = 2.

Для вычисления количества «ложных попаданий» в расчете на один успешный результат поиска рассчитаем вероятность чтения страницы внешней памяти в листовом узле Pчтения_стр и вероятность успешного исхода поиска Pпопадания.

Для определения Pпопадания учитываем следующие аспекты:

1. Фрагмент попадает только в последовательности, имеющие повторения.

2. Последовательности, в которые попадает фрагмент, содержат соседние повторения.

3. Фрагмент попадает только в последовательности, у которых повторяется то же значение элементов.

4. Оставшийся элемент искомого фрагмента (кроме повторений) содержится в последовательностях.

5. Количество возможных расположений искомого фрагмента длиной f в последовательностях длиной m равно m - f + 1.

Вероятность попадания искомого фрагмента в последовательность с повторениями (Pс_повт) рассчитывается по формуле (2.25).

Если допустить, что фрагмент попал в последовательность с повторениями, то вероятность того, что в этой последовательности есть соседние повторения, равна (используются формулы (2.11) и (2.12)):

* АПk, r АПk, r m m Pсоседн _ повт (2.36) АПk, r m В результате, вероятность успешного исхода поиска будет равна:

1 Pпопадания Pс _ повт Pсоседн _ повт Pkm r 1 ( f r f ), (2.37) m f k где Pkm ( f ) - вероятность нахождения f различных элементов в индексированных последовательностях (рассчитывается по формуле (2.32)).

Для рассматриваемого примера поиска данное значение будет равно 0,00006088.

Теперь определим для поиска этого же фрагмента вероятность чтения страницы внешней памяти в листовом узле (Pчтения_стр). Учитываем следующие аспекты:

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

2. Фрагмент пройдет сигнатурную проверку только для последовательностей, у которых повторяется то же значение элементов, что и у самого фрагмента.

3. Оставшийся элемент искомого фрагмента (кроме повторений) содержится в последовательностях.

С учетом всего перечисленного в рассматриваемом примере поиска вероятность обращения к странице внешней памяти в листовых узлах будет равна:

Pчтения _ стр Pс _ повт Pkm r 1 ( f r f ), (2.38) k где Pс _ повт - вероятность попадания фрагмента в последовательности с повторениями (рассчитывается по формуле (2.25)), Pkm ( f ) - вероятность нахождения f различных элементов в индексированных последовательностях (рассчитывается по формуле (2.32)).

В рассматриваемом примере поиска Pчтения_стр будет равна 0,012959.

Таким образом, используя формулу (2.6), получаем, что после первого этапа модификации при поиске фрагмента в последовательностях по RD-дереву относительное количество «ложных попаданий» для рассматриваемого примера K ложн _ попадании_ на _ 1 _ успех 211. При расчете использована поиска равно математическая модель реальных данных, описанная в разделе 2.3.1.

В результате, теоретическое относительное количество «ложных попаданий» на рассмотренном примере поиска уменьшилось более чем на порядок по сравнению с оригинальным RD-деревом (в разделе 2.3.2 было получено значение 2672 для аналогичного примера поиска). Однако, в отличие от предыдущего примера, в искомом фрагменте присутствовали одинаковые элементы, что для оригинальных RD-деревьев является еще более «сложным»

случаем поиска.

Таким образом, произведенная модификация сигнатур RD-деревьев существенно увеличивает скорость поиска фрагментов с повторениями. Если же искомый фрагмент не содержит повторений, то эффективность поиска будет неизменной, так как количество, хранимое в сигнатурных элементах, будет просто играть роль признака, как в сигнатурах оригинальных RD-деревьев.

2.4.2 Этап 2: добавление в индекс признаков повторения элементов подряд в последовательностях В предыдущем разделе устранена первая причина «ложных попаданий» при поиске фрагментов в последовательностях с использованием RD-деревьев (не учитывается количество одинаковых элементов). Вторая причина – не учитывается порядок расположения элементов – не менее важная. Ее устранению посвящены следующие два этапа в разработке модификации RD-деревьев. В данном разделе описан один из них.

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

Технически в сигнатуры добавляется 1 бит информации в качестве признака повторения подряд для каждого значения элементов, т.е. в каждый сигнатурный элемент. Установленный признак в каком-либо сигнатурном элементе означает, что в последовательности, отображаемой данной сигнатурой, элементы с соответствующим значением хотя бы раз повторяются подряд. Структура сигнатурного элемента после предложенной модификации приведена на рисунке 2.7.

7 6 5 4 3 2 1 Двоичное представление количества элементов с данным значением Признак повторения подряд Рисунок 2.7 – Структура сигнатурного элемента после второго этапа модификации Данная модификация сигнатур означает добавление второй хеш-функции для построения сигнатур, основанных на блюмовских фильтрах. Первая же хеш функция, устанавливающая количество, теперь заполняет только 7 младших бит каждого сигнатурного элемента. Добавленная хеш-функция взводит оставшийся старший бит, используя его как флаг.

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

На рисунке 2.8 приведен пример RD-дерева с модифицированными сигнатурами для индексации последовательностей чисел.

Числовые {(225,+2)(227,-1)(164,-1)(160,-2)(172,-2)} {(162,-1)(32,-1)(171,-1)(165,-1)(225,-1)(226,-1)} последовательности Ссылка на поддерево 1 Ссылка на поддерево 1) 225,225,227,164, Сигнатура 2) 172,160,172, 3) 162,32,171,165, 4) 225,162,165,226 {(162,-1)(32,-1)(171,-1)(165,-1)(225,-1)} {(225,-1)(162,-1)(165,-1)(226,-1)} Ссылка на 162,32,171,165,225 Ссылка на 225,162,165, {(225,+2)(227,-1)(164,-1)(160,-1)} {(172,-2)(160,-2)} Ссылка на 225,225,227,164,160 Ссылка на 172,160,172, Рисунок 2.8 – Пример RD-дерева после второго этапа модификации При внесении таких изменений в структуру сигнатур RD-дерева изменяется алгоритм проверки сигнатур при поиске. Теперь он заключается не только в анализе количества каждого значения элементов, но и в определенной обработке признака последовательных повторений. Следовательно, все достоинства использования первого этапа модификации сохраняются. Измененный алгоритм проверки включения сигнатур друг в друга, отмеченный в общем алгоритме поиска по RD-дереву в приложении А, приведен на рисунке 2.9.

В результате данная модификация RD-деревьев увеличивает скорость поиска фрагментов с соседними повторениями, например, {225,225,227,164,160}.

Из поиска в таких случаях исключаются поддеревья, в сигнатурах которых для какого-либо значения элементов сброшен бит повторения, в то время как в сигнатуре искомого фрагмента этот бит установлен.

Сигнатуры фрагмента (SF), и узла дерева (Si) Обход сигнатурных элементов из SF, пока не закончились Да Количество в SF количества в Si?

Нет Да Бит повторений в SF = 1, а в Si = 0?

Синатура SF не Нет включена в Si Обход сигнатурных элементов из SF Синатура SF включена в Si Рисунок 2.9 – Условие включения сигнатур друг в друга после второго этапа модификации Например, при поиске фрагмента {1,1,2,3}, сигнатура которого равна {(1,+2)(2,-1)(3,-1)}, будет исключено из рассмотрения поддерево, имеющее сигнатуру {(1,-2)(2,-1)(3,-1)}, хотя все значения элементов там присутствуют и не в меньшем количестве. Дело в том, что элемент «1» в поддереве никогда не повторяется подряд, а в искомом фрагменте повторяется. При использовании сигнатур, хранящих только количество элементов каждого значения (этап 1), данная проверка была бы пройдена, и в поиск попало бы поддерево, не удовлетворяющее поиску.

Математическая оценка количества «ложных попаданий» после второго этапа модификации Выполним математическую оценку относительного количества «ложных попаданий» в расчете на один успешный результат поиска при использовании сигнатур RD-дерева после второго этапа модификации.

Аналогично первому этапу модификации, рассмотрим поиск фрагмента из f элементов, который содержит rf повторений подряд, и оценим количество «ложных попаданий» при таком поиске. Аналогично оценке, выполненной в разделе 2.3.2 для оригинальных RD-деревьев, рассматривать будем пример поиска в текстовом поле БД с типовыми параметрами:

средняя длина последовательностей m = 50, число возможных значений элементов k = 60, число возможных повторений в последовательностях r = 4.

При этом оценку выполним для поиска фрагмента из трех элементов (f = 3) – достаточно частого случая поиска фрагмента. Количество повторений элементов в искомом фрагменте rf = 2.

Для вычисления количества «ложных попаданий» в расчете на один успешный результат поиска, согласно (2.6), требуется определить вероятность чтения страницы внешней памяти в листовом узле Pчтения_стр и вероятность успешного исхода поиска Pпопадания.

Вероятность Pпопадания определена при выполнении математической оценки после первого этапа модификации в предыдущем разделе, ее значение составило 0,00006088.

Определим для поиска этого же фрагмента вероятность чтения страницы внешней памяти в листовом узле (Pчтения_стр). Учитываем следующие аспекты:

1. Искомый фрагмент пройдет сигнатурную проверку только для последовательностей, имеющих повторения.

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

3. Фрагмент пройдет сигнатурную проверку только для последовательностей, у которых повторяется то же значение элементов, что и у самого фрагмента.

4. Оставшийся элемент искомого фрагмента (кроме повторений) содержится в последовательностях.

Для определения вероятности Pчтения_стр используем формулу (2.38), полученную при оценке первого этапа модификации RD-деревьев в предыдущем разделе. На данном этапе в эту формулу добавляется множитель Pсоседн_повт – вероятность того, что в последовательности, куда попадает искомый фрагмент, есть соседние повторения (рассчитывается по формуле (2.36), полученной также в предыдущем разделе). Таким образом, скорректированное для второго этапа модификации выражение для Pчтения_стр следующее:

Pчтения _ стр Pс _ повт Pсоседн _ повт Pkm r 1 ( f r f ), (2.39) k где Pс _ повт - вероятность попадания фрагмента в последовательности с повторениями (рассчитывается по формуле (2.25)), Pkm ( f ) - вероятность нахождения f различных элементов в индексированных последовательностях (рассчитывается по формуле (2.32)).

В рассматриваемом примере поиска Pчтения_стр будет равна 0,00292239.

Таким образом, используя формулу (2.6), получаем, что после второго этапа модификации при поиске фрагмента в последовательностях по RD-дереву относительное количество «ложных попаданий» для рассматриваемого примера K ложн _ попадании_ на _ 1 _ успех 47. При расчете использована поиска равно математическая модель реальных данных, описанная в разделе 2.3.1.

В результате, теоретическое относительное количество «ложных попаданий» на рассмотренном примере поиска уменьшилось более чем в 4 раза по сравнению с первым этапом модификации (в предыдущем разделе было получено значение 211 для аналогичного примера). По сравнению же с оригинальным RD деревом на рассмотренном примере поиска количество «ложных попаданий»

уменьшилось более чем в 50 раз (в разделе 2.3.2 было получено значение 2672 для аналогичного примера поиска).

Таким образом, произведенный второй этап модификации сигнатур RD деревьев существенно увеличивает скорость поиска фрагментов с соседними повторениями. Если же искомый фрагмент не содержит повторений подряд, то эффективность поиска будет неизменной по сравнению с первым этапом модификации, так как количество каждого значения элементов будет по прежнему использоваться для исключения поддеревьев из поиска.

2.4.3 Этап 3: использование разбиения последовательностей для учета порядка расположения элементов В данном разделе описан еще один этап в разработке модификации RD деревьев для устранения второй причины «ложных попаданий» – не учитывается порядок расположения элементов в сигнатурах.

На предыдущем этапе модификации в сигнатуры RD-деревьев был добавлен признак повторения элементов подряд в индексируемых последовательностях. В результате порядок расположения элементов теперь частично учтен в сигнатурах RD-дерева. Однако этого недостаточно, поскольку эффект от выполненного второго этапа модификации проявляется только при поиске фрагментов, содержащих соседние повторения. Подобные поисковые запросы встречаются не так часто, поэтому необходим более точный учет порядка элементов в последовательностях. Решению этой проблемы посвящен третий этап модификации сигнатур RD-деревьев.

На данном этапе для получения дополнительной информации о расположении элементов используется разбиение индексируемых последовательностей на части. Для этого некоторые значения элементов выбираются в качестве разделителей.

Определение 2.3 Фреймы – фрагменты индексируемых последовательностей, используемые для учета порядка расположения элементов. Деление последовательностей на фреймы осуществляется отдельными выбранными значениями элементов – разделителями.


Определение 2.4 Граничные элементы – элементы индексируемых последовательностей, являющиеся крайними элементами фреймов, образованных в результате разбиения. При этом разделители фреймов не являются граничными элементами, т.к. не входят в состав фреймов.

В результате разбиения индексируемых последовательностей на фреймы появляется информация о порядке расположения элементов, которая добавляется в сигнатуры узлов RD-дерева. А именно, для каждого значения элементов в соответствующий сигнатурный элемент добавляется признак того, что элементы с данным значением являлись граничными хотя бы раз в отображаемой последовательности. Данная информация делает описание сигнатурами хранимых последовательностей еще более полным, что приводит к снижению количества «ложных попаданий».

Технически в сигнатуры добавляется 1 бит информации в качестве признака наличия граничных элементов для каждого значения, т.е. в каждый сигнатурный элемент. Структура сигнатурного элемента после третьего этапа модификации приведена на рисунке 2.10.

7 6 5 4 3 2 1 Двоичное представление количества элементов с данным значением Признак граничных элементов Признак повторения подряд Рисунок 2.10 – Структура сигнатурного элемента после третьего этапа модификации С точки зрения построения сигнатур на основе блюмовских фильтров данная модификация означает добавление третьей хеш-функции. При этом первая хеш-функция, устанавливающая количество, теперь заполняет только 6 младших бит сигнатурного элемента. Вторая хеш-функция, устанавливающая признак повторения подряд, по-прежнему использует старший 7-ой бит. Третья же (новая) хеш-функция устанавливает 6-ой бит сигнатурного элемента, используя его как признак наличия граничных элементов с соответствующим значением.

Таким образом, максимальное учитываемое количество одинаковых элементов в последовательности будет равно 26, т.е. 64. Этого также будет достаточно для индексируемых последовательностей среднего размера (текстовые поля в БД, числовые массивы и т.п.), поскольку так часто элементы в последовательностях на реальных данных не повторяются. При превышении же максимального количества одинаковых элементов фактическое количество «обрезается» до максимально значения (до 63-х, т.к. нумерация с нуля). Таким образом, превышение максимального количества одинаковых элементов просто не будет приносить дальнейшего эффекта для ускорения поиска. Однако вероятность такого превышения достаточно мала.

На рисунке 2.11 приведен пример RD-дерева с модифицированными сигнатурами для индексации числовых последовательностей (значение выбрано в качестве разделителя).

Числовые {(225,+-2)(227,--1)(164,--1)(160,--2)(172,--2)} {(162,-+1)(32,--1)(171,-+1)(165,--1)(225,--1)(226,--1)} последовательности Ссылка на поддерево Ссылка на поддерево 1) 225,225,227,164, 2) 172,160,172, Сигнатура 3) 162,32,171,165, 4) 225,162,165, {(162,-+1)(32,--1)(171,-+1)(165,--1)(225,--1)} {(225,--1)(162,--1)(165,--1)(226,--1)} Ссылка на 162,32,171,165,225 Ссылка на 225,162,165, {(225,+-2)(227,--1)(164,--1)(160,--1)} {(172,--2)(160,--2)} Ссылка на 225,225,227,164,160 Ссылка на 172,160,172, Рисунок 2.11 – Пример RD-дерева после третьего этапа модификации При внесении таких изменений в структуру сигнатур RD-дерева изменяется алгоритм проверки сигнатур при поиске. В данную проверку добавляется определенная обработка признака граничных элементов. Все достоинства использования предыдущих двух этапов модификации сигнатур сохраняются.

Измененный алгоритм проверки включения сигнатур друг в друга, отмеченный в общем алгоритме поиска по RD-дереву в приложении А, приведен на рисунке 2.12.

В результате данная модификация RD-деревьев увеличивает скорость поиска фрагментов с граничными элементами, т.е. фрагментов с фреймами.

Например, {162,32,171,165,225} при использовании значения 32 в качестве разделителя (здесь элементы 162 и 171 являются граничными). Из поиска в таких случаях исключаются поддеревья, в сигнатурах которых для какого-либо значения элементов сброшен бит наличия граничных элементов, в то время как в сигнатуре искомого фрагмента этот бит установлен.

Сигнатуры фрагмента (SF), и узла дерева (Si) Обход сигнатурных элементов из SF, пока не закончились Да Количество в SF количества в Si?

Нет Да Бит повторений в SF = 1, а в Si = 0?

Нет Да Бит граничности в SF = 1, а в Si = 0?

Синатура SF не Нет включена в Si Обход сигнатурных элементов из SF Синатура SF включена в Si Рисунок 2.12 – Условие включения сигнатур друг в друга после третьего этапа модификации Например, для фрагмента {1,1,2,3}, используя в качестве разделителя значение «2», сигнатура будет равна {(1,++2)(2,--1)(3,-+1)}. При поиске такого фрагмента будет исключено из рассмотрения поддерево, имеющее сигнатуру {(1,+-2)(2,--1)(3,-+1)}, хотя все значения элементов там присутствуют не в меньшем количестве, и также элемент «1» повторяется подряд. Дело в том, что элемент «1» в поддереве никогда не располагается на границе фрейма, а в искомом фрагменте располагается. При использовании сигнатур после второго этапа модификации данная сигнатурная проверка была бы пройдена, и в поиск попало бы поддерево, не удовлетворяющее поиску.

Математическая оценка количества «ложных попаданий» после третьего этапа модификации Выполнить математическую оценку количества «ложных попаданий» при использовании модифицированных сигнатур RD-дерева на третьем этапе представляется затруднительным, так как данное количество напрямую зависит от выбранного набора разделителей фреймов. Ценность такой доработки для эффективности поиска доказывается эмпирически в последующих главах. Кроме того, в третьей главе предлагается доработка алгоритма построения RD-дерева, путем добавления в него этапа анализа индексируемых данных, на котором набор разделителей фреймов будет формироваться автоматически по содержимому БД, обеспечивая высокую эффективность третьего этапа модификации для любого конкретного содержимого БД.

Таким образом, произведенный третий этап модификации сигнатур RD деревьев увеличивает скорость поиска фрагментов с фреймами. Если же искомый фрагмент не содержит граничных элементов, то эффективность поиска будет неизменной по сравнению со вторым этапом модификации. Кроме того, важным достоинством предложенного способа модификации RD-деревьев является возможность адаптации к конкретному содержимому БД.

Выводы по главе 1. Асимптотический анализ алгоритмов показал, что RD-деревья имеют хорошую временную сложность построения, которая составляет O(n·log(n)), где n – количество индексируемых объектов. Кроме того, RD-деревья обладают небольшими требованиями к памяти – O(n). Однако не гарантируется приемлемая временная сложность поиска в наихудшем случае, хотя RD-деревья хорошо работают на реальных данных. Временная сложность поиска в наихудшем случае составляет O(n), при этом было доказано, что для среднего случая она составляет n O( ).

log( n) 2. Причины «ложных попаданий» при поиске фрагмента в последовательностях по RD-дереву следующие:

a. Не учитывается количество одинаковых элементов в индексируемых последовательностях, b. Не учитывается порядок расположения элементов.

3. Предложенные три этапа модификации RD-деревьев приводят к более полному описанию индексируемых последовательностей сигнатурами дерева, но не изменяют асимптотических характеристик поиска и построения RD-дерева. В результате снижена вероятность «ложных попаданий» при поиске следующих типов фрагментов:

a. Фрагментов с повторениями, b. Фрагментов с соседними повторениями, c. Фрагментов с фреймами.

4. Модификация структуры RD-дерева приводит к увеличению его размера.

В четвертой главе данное увеличение размера будет полностью скомпенсировано.

5. Для случая поиска, когда все-таки не нужно учитывать порядок расположения элементов, применим только первый этап модификации RD деревьев.

6. Для первых двух этапов модификации RD-деревьев доказано уменьшение теоретического количества «ложных попаданий»: для первого этапа более чем на порядок, для второго этапа – еще более чем в 4 раза.

7. На третьем этапе модификации RD-деревьев, связанном с разбиением последовательностей на фреймы, выполнить теоретическую оценку количества «ложных попаданий» представляется затруднительным. Его эффективность будет доказана экспериментально в третьей главе данной диссертационной работы.

Важным достоинством данного способа модификации является возможность адаптации к конкретному содержимому БД.

ГЛАВА 3. Выбор параметров алгоритмов построения и использования RD деревьев. Экспериментальная проверка эффективности В предыдущей главе выполнена разработка модификации структуры RD деревьев, включающая три этапа:

1. Добавление в индекс информации о количестве одинаковых элементов в последовательностях, 2. Добавление в индекс признаков повторения элементов подряд в последовательностях, 3. Использование разбиения последовательностей для учета порядка расположения элементов.

Каждый из этих этапов призван уменьшить количество «ложных попаданий», а, следовательно, увеличить эффективность поиска.

В данной главе производится экспериментальная проверка скорости поиска по индексу и эффективности построения индекса при использовании модифицированной структуры RD-дерева. Доработан алгоритм построения индекса, который непосредственно перед созданием RD-дерева подготавливает актуальные для содержимого БД разделители фреймов (для третьего этапа модификации). Выполняется оценка степени применимости выполненных модификаций.

3.1 Экспериментальная проверка эффективности поиска с использованием модифицированных RD-деревьев Как было сказано выше, RD-деревья не гарантируют приемлемой скорости поиска в наихудшем случае, но хорошо показывают себя на реальных данных.

Временная сложность поиска для среднего случая, полученная во второй главе и n составляющая O( ), где n – количество индексируемых объектов, все же log( n) несколько завышена. Поэтому для увеличения практической значимости результатов экспериментальная проверка выполняется на реальных данных:


1. Русскоязычный текст (техническая литература). Средняя длина хранимых строк – 54,58 символа.

2. Англоязычный текст (техническая литература). Средняя длина хранимых строк – 42,76 символа.

3. Числовые массивы в виде бинарного программного кода. Для индексации таких данных использовалось искусственное разбиение на части по байт.

Результаты поиска, полученные на таких данных, усредняются для получения итогового результата. Данный результат считаем адекватной оценкой эффективности поиска, распространяющейся на последовательности элементов произвольного типа.

3.1.1 Используемые средства для проверки эффективности Для проведения экспериментов использовалась собственная программная реализация на основе структуры RD-деревьев и алгоритмов, разработанных в предыдущей главе диссертации (реализация на языке C++ [44]).

Используются оригинальные алгоритмы построения RD-деревьев, унаследованные от R-деревьев и описанные в работе Гуттмана [58]. При этом минимизируется степень взаимного пересечения сигнатур узлов, благодаря расположению наиболее «похожих», близких по содержимому последовательностей по возможности в одно поддерево. Используются RD деревья первого порядка (p = 1). Следовательно, в каждом узле содержится не более 2p (т.е. двух) и не менее p (т.е. одного) элементов, т.е. ссылок на другие поддеревья либо на хранимые последовательности. Фактически, дерево получается не сильноветвящееся, а бинарное. В качестве хранимых в листовых узлах ссылок на индексируемые последовательности использованы следующие пары значений: ссылка на конкретный файл (текстовый или бинарный), позиция данных в файле. Таким образом сэмулированы обращения к внешней памяти в листовых узлах в том числе для исключения «ложных попаданий». В индексах на реальных СУБД ссылки на индексируемые данные являются указателями на страницы (блоки) определенного размера, с помощью которых происходит обмен с внешней памятью. В используемой реализации RD-дерево строится в оперативной памяти.

В узлы RD-дерева последовательно вносились изменения каждого из трех этапов модификации, предложенных во второй главе.

Поиск последовательностей элементов по фрагменту с использованием построенного выполняется по классическому алгоритму, RD-дерева приведенному в приложении А.

Таким образом, используемая программная реализация является достаточно адекватной моделью индексов на основе Следовательно, RD-деревьев.

полученные с ее помощью результаты считаем корректными и повторимыми в реальных информационных системах.

Экспериментальные оценки в данном разделе выполнены на компьютере с конфигурацией Intel Core i3 3,07 Гц, 4 гигабайта оперативной памяти.

3.1.2 Оценка количества «ложных попаданий» при поиске на случайных данных Перед выполнением экспериментов на реальных данных оценим количество «ложных попаданий» при поиске на сгенерированных случайных данных.

Полученные результаты сравним с теоретическими оценками количества «ложных попаданий» в расчете на один успешный результат поиска, полученными во второй главе.

В качестве случайных данных использованы строки, сгенерированные с теми же типовыми параметрами текстового поля БД, которые использовались при оценках во второй главе:

средняя длина последовательностей m = 50 (от сорока до шестидесяти), число возможных значений элементов k = 60:

«etaonisrclhdumpfgbEyATS.R_w,OvLICND-MP1UxkB2()0GHFV3:YQq45W/».

С такими параметрами сгенерировано один миллион записей, что достаточно для оценки количества «ложных попаданий» в расчете на один успешный результат поиска.

Для третьего этапа модификации в качестве разделителей фреймов случайным образом выбраны элементы: «aiQnse,4yG2o:t()51w».

При этом оценка выполняется для поиска фрагмента из трех элементов (f = 3) аналогично теоретическим оценкам во второй главе.

Результаты экспериментальной оценки количества «ложных попаданий»

приведены в таблице 3.1.

Таблица 3.1 – Экспериментальные результаты оценки количества «ложных попаданий» на случайных данных Ложных попаданий, шт.

Применимые Найдено, Тип фрагмента модификации шт. всего на 1 успех теоретически Без повторений и Оригинал 14 13394 955,71 фреймов С повторениями Этап 1 16 7252 452,25 С соседними Этапы 1, 2 10 535 53,5 повторениями С соседними повто Этапы 1, 2, 3 – 12 214 17, рениями и фреймами Из полученных экспериментальных результатов следует:

1. При поиске фрагментов без повторений и фреймов, на которые не распространяется выполненная модификация RD-деревьев, количество «ложных попаданий» на один успех в три раза ниже теоретической оценки. Объясняется тем, что в математической модели во второй главе количество повторений в одной последовательности было ограничено значением r = 4, причем повторяться в одной последовательности могло только одно значение элементов. На случайных же данных число повторений какого-либо значения в каждой последовательности может быть различным, и повторяться могут различные значения. Поэтому большую долю в последовательностях занимают повторяющиеся элементы, чем на математической модели. Следовательно, при поиске фрагментов без повторений для меньшего количества последовательностей проходят сигнатурные проверки в листовых узлах RD-дерева, что снижает количество «ложных попаданий».

2. При поиске фрагментов с повторениями, на которые распространяется только первый этап модификации RD-деревьев, количество «ложных попаданий» на один успех в два раза выше теоретической оценки.

Объясняется это теми же отличиями случайных данных от математической модели второй главы.

3. При поиске фрагментов с соседними повторениями, на которые распространяются первые два этапа модификации RD-деревьев, количество «ложных попаданий» на один успех незначительно отличается от теоретической оценки.

4. При поиске же фрагментов с соседними повторениями и фреймами, на которые распространяются все три этапа модификации RD-деревьев, количество «ложных попаданий» уменьшилось в 3 раза по сравнению с использованием только первых двух этапов. Это неплохой результат, учитывая адаптацию третьего этапа модификации к конкретному содержимому БД, выполненную далее. При этом полученное ускорение поиска не будет наблюдаться на любом содержимом БД.

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

3.1.3 Результаты экспериментальной проверки эффективности поиска Экспериментальная проверка скорости поиска, как сказано выше, выполняется на реальных данных с последующим усреднением результата.

При этом используется БД размером один миллион записей. Зависимость эффективности поиска от размера БД выполняется в следующем разделе. Цель данного раздела – исследовать влияние каждого из этапов модификации RD дерева на эффективность поиска.

Для текстовых данных в качестве разделителей фреймов используются следующие символы: «Space(){}[]'"?!.,:;

^+-*/\». При этом фреймы будут представлять собой, как правило, слова естественного языка.

Для числовых массивов в виде бинарного программного кода разделители фреймов выбраны случайным образом из часто встречающихся значений байтов.

Аналогично предыдущему разделу, в последовательностях выполняется поиск следующих типов фрагментов:

1. Без повторений и фреймов (не распространяется выполненная модификация RD-деревьев), 2. С повторениями (применим только первый этап модификации), 3. С соседними повторениями (применимы первые два этапа), 4. С соседними повторениями и фреймами (применимы все три этапа).

При этом экспериментальные результаты будут хорошо отражать вклад каждого из этапов модификации в ускорение поиска последовательностей по фрагменту.

Результаты экспериментальной проверки эффективности поиска и количества «ложных попаданий» сведены в таблицу 3.2.

Таблица 3.2 – Экспериментальные результаты проверки эффективности поиска на реальных данных Используемая Найдено, Ложных попаданий, шт tпоиска, Ускорен., Тип фрагмента модификация шт мс раз всего на 1 успех Оригинал 164 161 122,14 18 698 Этап 1 164 161 122,14 18 886 0, 1 1 Этап 2 164 161 122,14 18 973 0, Этап 3 164 161 122,14 19 032 0, Продолжение таблицы 3. Используемая Найдено, Ложных попаданий, шт tпоиска, Ускорен., Тип фрагмента модификация шт мс раз всего на 1 успех Оригинал 254 510 67,46 28 996 Этап 1 152 164 40,33 17 531 1, 2 3 Этап 2 152 164 40,33 17 546 1, Этап 3 152 164 40,33 17 722 1, Оригинал 327 146 270,59 36 597 Этап 1 159 671 132,07 18 066 2, 3 1 Этап 2 7 744 6,41 1 084 33, Этап 3 7 744 6,41 1 103 33, Оригинал 455 102 4 740,65 50 138 Этап 1 244 176 2543,5 27 049 1, 4 Этап 2 8 090 84,27 965 51, Этап 3 4 330 45,1 572 87, Как видно из таблицы 3.2, на реальных данных количество «ложных попаданий» на один успешный результат поиска существеннее отличается от теоретических оценок, полученных во второй главе, по сравнению со случайными данными. Причина заключается в объективных отличиях реальных данных от математической модели, использованной во второй главе. Но в целом результаты по количеству «ложных попаданий» все же соответствуют теоретическим оценкам, но с некоторыми погрешностями.

Из экспериментальных результатов проверки эффективности хорошо видно увеличение скорости поиска после реализации каждого из этапов модификации.

Для более детального анализа отдельно рассмотрим результаты, полученные для каждого типа искомых фрагментов.

Экспериментальные результаты поиска фрагментов без повторений и фреймов К данному типу искомых фрагментов не применима выполненная модификация RD-деревьев. Диаграммы изменения относительного количества «ложных попаданий» и скорости поиска на разных этапах модификации индекса приведены на рисунке 3.1.

Рисунок 3.1 – Результаты поиска фрагментов без повторений и фреймов Как и предполагалось, эффективность поиска таких фрагментов осталась практически неизменной. Наблюдается лишь незначительное снижение скорости поиска, которое после всех трех этапов модификации не превышает 3%. Данное уменьшение скорости поиска является причиной выполнения дополнительных сигнатурных проверок (см. рисунок 2.12).

Экспериментальные результаты поиска фрагментов с повторениями К данному типу искомых фрагментов применим только первый этап модификации RD-деревьев. Диаграммы изменения относительного количества «ложных попаданий» и скорости поиска на разных этапах модификации индекса приведены на рисунке 3.2.

Рисунок 3.2 – Результаты поиска фрагментов с повторениями Увеличение скорости поиска данного типа фрагментов после реализации первого этапа модификации сигнатур RD-деревьев составило около 65%. После реализации второго и третьего этапов модификации производительность незначительно уменьшилась за счет дополнительных сигнатурных проверок. Из рисунка 3.2 видно, что увеличение скорости поиска получено именно благодаря снижению количества «ложных попаданий».

Экспериментальные результаты поиска фрагментов с соседними повторениями К данному типу искомых фрагментов применимы первые два этапа модификации RD-деревьев. Диаграммы изменения относительного количества «ложных попаданий» и скорости поиска на разных этапах модификации индекса приведены на рисунке 3.3.

Скорость поиска данного типа фрагментов после реализации первого этапа модификации сигнатур RD-деревьев выросла примерно в 2 раза. После реализации второго этапа модификации поиск ускорился более чем на порядок (до 30 раз). После реализации третьего этапа модификации производительность незначительно уменьшилась за счет дополнительных сигнатурных проверок.

Рисунок 3.3 – Результаты поиска фрагментов с соседними повторениями Экспериментальные результаты поиска фрагментов с соседними повторениями и фреймами К данному типу искомых фрагментов применимы все три этапа модификации RD-деревьев. Диаграммы изменения относительного количества «ложных попаданий» и скорости поиска на разных этапах модификации индекса приведены на рисунке 3.4.

Рисунок 3.4 – Результаты поиска фрагментов с соседними повторениями и фреймами Скорость поиска данного типа фрагментов после реализации первого этапа модификации сигнатур RD-деревьев выросла на 85%. После реализации второго этапа модификации поиск ускорился более чем в 50 раз. А после реализации третьего этапа модификации скорость поиска выросла в несколько десятков раз (до 80 раз).

Выводы по экспериментальным результатам поиска По результатам экспериментальной проверки эффективности поиска на реальных данных можно сделать вывод, что каждый из выполненных трех этапов модификации RD-деревьев хорошо показывает себя на практике.

Отметим, что увеличение эффективности возникает только при поиске определенных типов фрагментов – тех, на которые распространяются выполненные этапы модификации RD-деревьев. Оценка в процентном отношении доли таких фрагментов в общей массе всех возможных искомых фрагментов выполнена далее в данной главе. Реализованные три этапа модификации индекса в своей совокупности распространяются на достаточно широкий круг поисковых запросов, при этом не производят практически никакого негативного эффекта на поиск фрагментов, не затронутых выполненными модификациями.

3.1.4 Оценка зависимости эффективности поиска от размера БД В предыдущем разделе экспериментальная проверка эффективности поиска фрагмента в последовательностях по RD-дереву выполнялась на фиксированном размере БД (один миллион записей). В данном разделе определим экспериментальную зависимость эффективности поиска от размера БД.

Для получения единого результата данные по разным типам искомых фрагментов усредняются.

Чтобы результат зависел только от размера БД, используется поиск только таких фрагментов, которые встречаются в одинаковом количестве на любом размере БД.

Получение экспериментальной зависимости скорости поиска от размера БД, выполняется на диапазоне от десяти тысяч до миллиона записей. Этого достаточно, чтобы проследить зависимость. График данной зависимости приведен на рисунке 3.5.

Рисунок 3.5 – Зависимость эффективности поиска от размера БД На графике пунктиром изображена теоретическая зависимость, соответствующая асимптотике для среднего случая, полученной во второй главе – n ). При этом видно, что экспериментальная зависимость, полученная на O( log( n) реальных данных, растет с увеличением размера БД значительно медленнее, чем теоретическая. Данный факт хорошо иллюстрирует и подтверждает известную особенность R- и RD-деревьев – высокая скорость поиска на реальных данных при отсутствии хорошей асимптотики, подтверждающей эффективность.

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

На рисунке 3.6 приведен график экспериментальной зависимости относительного количества «ложных попаданий» от размера БД.

Рисунок 3.6 – Зависимость количества «ложных попаданий» от размера БД Как и на предыдущем графике, пунктиром изображена теоретическая зависимость, в данном случае она соответствует второй составляющей асимптотики сложности поиска для среднего случая – O( ). Как видим, log( n) экспериментальная зависимость количества «ложных попаданий» достаточно близка к теоретической зависимости. На двухсот тысячах записей наблюдается пик «ложных попаданий» на один успех, после чего их количество снижается по зависимости, близкой к логарифмической. Данный факт подтверждает, во первых, корректность асимптотической оценки сложности поиска для среднего случая, выполненной во второй главе, во-вторых, соответствие экспериментальных результатов выполненной теоретической оценке.

3.2 Доработка алгоритма построения RD-дерева для эффективности разбиения последовательностей на фреймы Рассмотрим подробнее третий этап модификации сигнатур RD-деревьев.

Для разбиения индексируемых последовательностей на фреймы необходимо выбрать определенные значения элементов в качестве разделителей. В предыдущем разделе 3.1 при экспериментальной проверке скорости поиска для текстовых данных в качестве разделителей были выбраны следующие значения:

«Space(){}[]'"?!.,:;

^+-*/\». Для числовых массивов в виде бинарного кода разделители фреймов были выбраны случайным образом из часто встречающихся значений байтов.

Однако выбранные разделители могут не подходить для другого содержимого БД, а также для индексирования последовательностей элементов другого типа. Поэтому фиксированный набор разделителей фреймов обладает следующими недостатками:

Неудобен в использовании, поскольку его нужно каким-то образом задавать в зависимости от индексируемых данных, Не всегда эффективен при изменяющемся содержимом БД.

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

Таким образом, фиксированность набора разделителей – главный недостаток третьего этапа модификации сигнатур RD-деревьев.

Для устранения данного недостатка модифицированных RD-деревьев в данном разделе в алгоритм построения индекса добавлен этап анализа индексируемых данных непосредственно перед построением RD-дерева.

Назначение данного этапа – сформировать актуальный набор разделителей фреймов для текущего содержимого БД. В общем случае разделителем может быть любое значение, которое удобно использовать в качестве такового.

Доработанный алгоритм построения RD-деревьев после добавления нового этапа приведен на рисунке 3.7.

Начало Индексируемые данные Добавленный Анализ индексируемых этап анализа данных данных Актуальный набор разделителей фреймов Построение RD-дерева Построенное RD-дерево Конец Рисунок 3.7 – Доработанный алгоритм построения RD-деревьев 3.2.1 Разработка алгоритма анализа данных для формирования актуальных разделителей фреймов для содержимого БД Разработка добавленного в алгоритм построения RD-дерева этапа анализа индексируемых последовательностей для формирования актуальных разделителей фреймов выполняется в несколько шагов:

1. Выработка критерия актуальности набора разделителей для содержимого БД, 2. Выработка критерия для отнесения какого-либо значения элементов к разделителям фреймов, 3. Формулировка алгоритма формирования актуального набора разделителей.

Рассмотрим каждый из этих шагов подробнее.

Выработка критерия актуальности набора разделителей для БД Актуальность набора разделителей на конкретном содержимом БД удобно определять, исходя из доли разделителей в общем наборе элементов.

Пусть доля разделителей – X, доля граничных элементов – Y, а доля оставшихся символов – Z. Следовательно:

X Y Z 1 (3.1) Набор разделителей является актуальным для конкретного содержимого БД (с точки зрения разбиения на фреймы), когда количество граничных элементов будет максимальным. При этом максимальной будет вероятность нахождения в искомом фрагменте граничных элементов, учитывая, что искомые фрагменты соответствуют содержимому БД. Поскольку граничных элементов без разделителей быть не может, то из формулы (3.1) следует, что доля граничных элементов Y будет максимальна, когда Z0, т.е. когда все элементы в индексируемых последовательностях будут либо разделителями, либо граничными элементами. Таким образом, получаем:



Pages:     | 1 || 3 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.