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

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

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


Pages:     | 1 | 2 ||

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

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

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

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

Yакт 2 X акт (3.3) В реальности длина хранимых в БД последовательностей элементов не бесконечна, и крайние элементы последовательностей обязательно существуют.

Пусть m – средняя длина индексируемых последовательностей. В крайних положениях разделитель будет порождать только один граничный элемент вместо двух. Таким образом, учитывая, что крайних положений всего два, вероятность того, что разделитель породит один граничный элемент, будет равна. Тогда m вероятность того, что разделитель породит два граничных элемента, будет m составлять. Таким образом, получаем уточненную зависимость Yакт от Xакт:

m m Yакт X акт 2 X акт, (3.4) m m 2 (m 1 ) Yакт X акт (3.5) m Подставив полученное выражение (3.5) в формулу (3.2), получим:

2 (m 1 ) X акт X акт 1, (3.6) m m X акт (3.7) 3 m Получили зависимость актуальной доли разделителей от средней длины индексируемых последовательностей. Как видно из выражения (3.7), актуальная доля разделителей при достаточно больших значениях m стремится к одной трети.

lim X акт 1 (3.8) m Таким образом, разрабатываемый этап анализа индексируемых последовательностей должен формировать набор разделителей таким образом, чтобы доля разделителей была как можно ближе к актуальному значению, вычисленному по формуле (3.8). По сути, это является ограничением на длину набора разделителей.

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

K граничных _ при _ разделител _ k ях Yk (3.9) K всех _ элементов Чем больше Yk, тем больше значение k подходит на роль разделителя на конкретном содержимом БД.

Естественно, что при использовании нескольких разделителей одновременно, доля граничных элементов Y будет несколько ниже суммы значений Yk для всех значений-разделителей. Это объясняется взаимовлиянием между различными значениями-разделителями. Во-первых, разделители с разными значениями могут быть соседними друг с другом, не порождая с одной своей стороны граничного элемента. Во-вторых, разделители с разными значениями могут отстоять друг от друга только на один элемент, порождая при этом один граничный элемент на двоих. Чем больше набор разделителей фреймов, тем меньше итоговая доля граничных элементов Y. Учесть подобное взаимовлияние разных значений-разделителей крайне затруднительно. Кроме того, как правило, на реальных данных длина актуального набора разделителей невелика (около 10 значений элементов). Поэтому взаимовлиянием разных значений разделителей можно пренебречь.

Таким образом, величина Yk является единственным и достаточным критерием отнесения конкретного значения k к разделителям.

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

Обход таблицы БД, пока есть последовательности Для каждого значения элементов расчет критерия Yk Обход таблицы БД Сортировка списка значений по убыванию Yk Выбор из вершины списка столько значений, чтобы общая доля разделителей соответствовала (3.8) Рисунок 3.8 – Алгоритм анализа данных для формирования актуальных разделителей фреймов Алгоритм состоит в следующем:

1. Для каждого встречающегося в БД значения элементов рассчитывается величина критерия Yk.

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

3. Из вершины полученного списка выбирается столько значений элементов, чтобы общая доля разделителей соответствовала критерию (3.8), т.е.

была как можно ближе к одной трети.

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

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

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

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

русскоязычный текст – 1%, англоязычный текст – 4%, числовые массивы – 6%.

Следовательно, на этапе анализа вовсе не обязательно обходить всю таблицу целиком, достаточно в произвольном порядке обойти не более 10% записей. Оценка времени построения индекса показала, что такой этап анализа данных занимает около 11% от общего времени построения индекса. При такой эффективности этап анализа данных применим для коллекций последовательностей размером несколько десятков гигабайт, которые являются объектом диссертационного исследования.

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

3.2.2 Экспериментальная проверка корректности формирования актуальных разделителей фреймов Для того чтобы проверить работоспособность разработанного алгоритма для формирования актуального набора разделителей фреймов экспериментально на различных данных установим следующее: при какой доле разделителей создается максимальное количество граничных элементов. При этом разделители будут выбираться согласно разработанному алгоритму анализа данных (рисунок 3.8), только без проверки соответствия выражению (3.8). Согласно критерию (3.8) актуальная доля разделителей должна быть равна одной трети, проверим это экспериментально.

Как в предыдущих экспериментах, используем следующее содержимое БД:

русскоязычный текст;

англоязычный текст;

числовые массивы в виде бинарного программного кода.

Размер БД во всех трех случаях равен одному миллиону записей. Такого объема данных вполне достаточно для качественной проверки разработанного алгоритма.

На каждом содержимом БД произведены замеры долей граничных элементов Y, для различных наборов разделителей фреймов, соответствующих долям X от 10% до 90%. Экспериментальные результаты сведены в таблицы 3.3, 3.4 и 3.5.

Таблица 3.3 – Доли граничных элементов для разных долей разделителей на русскоязычном тексте Процент Процент граничных Набор разделителей разделителей элементов 13,53 "" 17, " о" 20,19 23, " оеа" 31,57 31, " оеаит" 41,18 31, " оеаитнрс" 51,9 25, " оеаитнрслвпм" 61,76 19, " оеаитнрслвпмкдыяу" 70,35 13, " оеаитнрслвпмкдыяузбь,Eчйг.цe" 80,06 9, " оеаитнрслвпмкдыяузбь,Eчйг.цe 6, жAхRSюL-TOCtNraonфщIis1" Таблица 3.4 – Доли граничных элементов для разных долей разделителей на англоязычном тексте Процент Процент граничных Набор разделителей разделителей элементов 14,15 "" 24, 23,28 " e" 32, 36 " eta" 35, 40,91 " etao" 37, 50,63 " etaoni" 33, 62,39 " etaonisrc" 24, 71,74 " etaonisrclhdu" 16, 80,12 " etaonisrclhdumpfgbE" 11, 90,64 " etaonisrclhdumpfgbEyATS.R_w,OvLI" 7, Таблица 3.5 – Доли граничных элементов для разных долей разделителей на числовых массивах Процент Процент граничных Набор разделителей разделителей элементов 12,23 32 14, 20,38 32,139,65 21, 30,87 32,139,65,36,255,4,131 23, 40,7 32,139,65,36,255,4,131,21,45,141,68,64 24, перечисленные выше и:

51,22 21, 1,8,80,104,137, перечисленные выше и:

60,22 19, 100,86,199,16,204,48,94,194, перечисленные выше и:

70,15 161,232,76,67,198,51,44,106,128,6,192, 14, 81,12,69, перечисленные выше и:

80,12 132,241,117,195,236,3,66,40,89,208,87, 11, 20,77,235,170,252,124, перечисленные выше и:

207,140,168,126,133,70,254,163,43,206, 90,28 6, 59,95,72,24,246,114,233,83,85,84,248, 5,56,184,5,144,200,217,224, Графики зависимостей Y от X, построенные по экспериментальным результатам, приведены на рисунке 3.9.

Рисунок 3.9 – Зависимость доли граничных элементов от доли разделителей Как видно из графиков, на различных данных максимальное количество граничных символов создается при доле разделителей в диапазоне 30-40%.

Данный результат подтверждает корректность критерия (3.8), согласно которому для достаточно больших размеров индексируемых последовательностей X акт 1. Следовательно, подтверждается корректность всего алгоритма формирования актуального набора разделителей в целом.

3.2.3 Экспериментальная проверка эффективности поиска с использованием доработанного алгоритма построения RD-дерева В данном разделе проверяется, каким образом доработка алгоритма построения RD-дерева сказывается на эффективности поиска фрагментов в последовательностях. То есть экспериментально доказывается, что использование выбранных на этапе анализа БД разделителей фреймов эффективнее использования фиксированного набора разделителей, как это было сделано в разделе 3.1.3.

Как в предыдущих экспериментах, используем следующее содержимое БД:

1. русскоязычный текст, 2. англоязычный текст, 3. числовые массивы в виде бинарного программного кода.

Это позволит в полной мере убедиться в универсальности этапа анализа БД при построении RD-дерева применительно к произвольному содержимому БД.

В качестве искомых фрагментов на каждом содержимом БД выбраны различные последовательности элементов, содержащие наиболее часто используемые разделители (см. таблицы 3.3 – 3.5). Для текстовых данных использовались различные слова, для бинарного кода – последовательности машинных кодов команд процессора.

При этом используется БД размером один миллион записей. Зависимость эффективности поиска от размера БД выполнена ранее в разделе 3.1.4. Поэтому в данном эксперименте исследовать зависимость от размера БД не требуется.

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

Рисунок 3.10 - Результаты поиска после доработки алгоритма построения RD-дерева Экспериментальные результаты проверки скорости поиска показывают, что эффективность поиска различных фрагментов на различных данных после добавления этапа анализа в алгоритм построения индекса возросла на 10-40% относительно уже трижды модифицированной структуры R-дерева. Это обусловлено правильным выбором элементов в качестве разделителей для конкретного содержимого БД.

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

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

3.3 Оценка степени применимости выполненной модификации RD-деревьев к различным искомым данным Выполненные модификации структуры и алгоритмов работы с RD деревьями (три этапа модификации структуры и доработанный алгоритм построения) применимы для поиска не любых искомых фрагментов, а только для определенных их типов:

С повторениями (любыми) – применим первый этап, С соседними повторениями – применимы первый и второй этапы, С фреймами – применим третий этап.

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

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

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

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

1. Обходятся все хранимые в БД последовательности элементов, 2. Для каждой последовательности анализируются все возможные искомые фрагменты заданной длины, которые она содержит, 3. Для каждого фрагмента, содержащегося в текущей последовательности, анализируется применимость выполненных модификаций: наличие повторений (в том числе соседних) и фреймов, 4. После обхода всех последовательностей среди всех рассмотренных фрагментов рассчитываются доли тех, к которым применимы три этапа модификации структуры RD-дерева. Данные доли фрагментов отражают степень применимости модификаций к поиску в рассмотренной БД.

Для оценки используется собственная программная реализация (на языке C++ [44]). Алгоритм работы программы приведен на рисунке Б.1 в приложении Б.

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

Результаты следующие:

1. Степень применимости первого этапа модификации (фрагменты с любыми повторениями) растет с увеличением длины искомых фрагментов и при достаточно большой длине превышает 80%.

2. Степень применимости второго этапа модификации (фрагменты с соседними повторениями) растет с увеличением длины искомых фрагментов и при достаточно большой длине достигает 20%.

3. Степень применимости третьего этапа модификации (фрагменты с фреймами) растет с увеличением длины искомых фрагментов и при достаточно большой длине достигает 90%.

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

Аналогичная экспериментальная оценка была выполнена для сгенерированных случайных данных (параметры аналогичны тем, что были использованы в разделе 3.1.2). Экспериментальные результаты сведены в диаграмму на рисунке 3.12.

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

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

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

Сигнатурный элемент увеличен с одного бита до одного байта;

Этап 1 – сигнатурный элемент стал интерпретироваться, как двоичное представление количества элементов с соответствующим значением, а не как признак;

Этап 2 – один из битов сигнатурного элемента стал использоваться, как признак повторений подряд, элементов с данным значением;

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

Кроме того, доработанный алгоритм построения RD-дерева предполагает анализ 10% записей в произвольном порядке.

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

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

Использовалась БД размером один миллион записей, что достаточно для оценки влияния модификаций на размер индекса.

На рисунке 3.13 приведена диаграмма изменения времени построения RD дерева по мере внесения изменений в его структуру.

Рисунок 3.13 – Влияние выполненной модификации на время построения RD-дерева Видим, что время построения индекса даже после реализации всех изменений структуры и алгоритмов работы с деревом увеличилось приблизительно на 25%. Данное увеличение времени построения RD-дерева не является критичным.

Таким образом, произведенная модификация индексов на основе RD деревьев незначительно замедляет построение/обновление индекса.

Оценка влияния выполненных модификаций RD-деревьев на размер индекса выполнена в четвертой главе на реальной СУБД (PostgreSQL).

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

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

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

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

Рисунок 3.14 – Зависимость эффективности построения RD-дерева от размера БД Как видим, экспериментальная зависимость времени построения индекса достаточно близка к теоретической зависимости. Это доказывает, что выполненные модификации RD-деревьев не влияют на асимптотику построения индекса, а лишь увеличивают абсолютное значение сложности построения.

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

Для фрагментов, к которым применим первый этап модификации, скорость поиска возросла на 65%. Для фрагментов, к которым применимы первые два этапа – более чем на порядок (до 30 раз). Для фрагментов, к которым применимы все три этапа модификации – в несколько десятков раз (до 80 раз). При поиске же фрагментов, к которым не применима модификация, снижение эффективности не превышает 3%.

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

3. Доработан алгоритм построения RD-дерева, в который добавлен этап анализа индексируемых данных с целью формирования актуального набора разделителей фреймов. В результате эффективность поиска фрагментов с фреймами возросла на 10-40% по сравнению с использованием фиксированного набора разделителей. Кроме того, данная доработка избавляет от задания разделителей при построении индекса, что было бы достаточно неудобно. Данная доработка алгоритма построения увеличивает время построения на 11%.

4. Экспериментально установлено, что степень применимости выполненных модификаций структуры RD-дерева и алгоритмов работы с ним достаточно высока и растет с увеличением длины искомых фрагментов. Для фрагментов длиной 7 и более элементов степень применимости модификаций близка к 100%.

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

ГЛАВА 4. Применение полученных результатов для практических задач В предыдущих главах предложены модификации структуры и алгоритмов работы с которые изначально были предложены Дж.

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

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

Кроме того, разработан индекс на основе модифицированных RD-деревьев для СУБД PostgreSQL, благодаря чему:

подтверждены экспериментальные оценки, полученные в третьей главе;

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

4.1 Применение модифицированных RD-деревьев для поиска по фрагменту в числовых массивах Постановка этой задачи приведена в главе 1 (раздел 1.1.1).

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

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

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

Как сказано при постановке задачи в первой главе, достаточно часто применимость индексов для числовых массивов, отражающих хронологические события, бывает невозможной вследствие нормализации данных в реляционных СУБД [35,41,54]. В результате поисковые запросы, аналогичные по смыслу поиску фрагмента в числовых массивах, сложно формулируются и долго выполняются. Для этого, как правило, требуются вложенные запросы и такие SQL операторы, как IN, EXISTS, OR и т.п., которые медленно выполняются на современных СУБД. При использовании денормализованных таблиц БД, содержащих отдельный столбец для хранения числовых массивов, даже полный перебор с поиском по фрагменту часто будет выполняться быстрее, чем вложенные запросы с SQL операторами IN, EXISTS, OR. Использование же индекса на основе модифицированных RD-деревьев по такому столбцу денормализованной таблицы позволит существенно ускорить подобные поисковые запросы.

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

1. Последовательности состояний/операций искомых объектов, хранимые в отдельных связанных таблицах БД, преобразуются в числовые массивы;

2. В таблицу БД, где хранятся искомые объекты, добавляется новый столбец, в котором сохраняются полученные числовые массивы состояний/операций;

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

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

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

К примеру, в свободно распространяемой СУБД PostgreSQL для решения подобных задач поиска разработан специальный тип данных intarray, представляющий собой целочисленный массив с поддержкой индексного доступа.

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

Задача поиска фрагментов в числовых массивах востребована в различных предметных областях, например:

кредитные договоры и операции, произведенные с ними, студенты и сданные ими экзамены, сотрудники организации и их должности, и т.п.

Проверка в реальных условиях реализации поиска по фрагменту в числовых массивах выполнялась в компании R-Style Softlab (ЗАО «Эр-Стайл Софтлаб»). В подсистеме «Кредитование» ИБС RS-Bank была реализована возможность эффективного поиска кредитных договоров по фрагменту истории выполненных по ними операций. При реализации использовалась сформулированная выше методика. При этом числовыми массивами отражались операции по кредиту. Для хранения этих массивов был добавлен новый столбец в таблицу кредитных договоров. В результате была получена возможность эффективного поиска кредитных договоров по фрагменту кредитных операций, например, «найти все договоры, по которым после выдачи кредита было не менее пяти погашений подряд», либо «найти все договоры, по которым было несколько просрочек подряд» и т.п. Подобного рода поисковые запросы являются достаточно востребованными в подсистеме «Кредитование» ИБС RS-Bank. На специально подготовленной БД, содержащей свыше двухсот тысяч кредитных договоров, запросы на поиск последних по фрагменту массива выполненных операций ускорились в несколько раз с нескольких секунд до нескольких десятых секунды по сравнению со средствами и алгоритмами поиска, используемыми ранее.

Проверка выполнялась на сервере с конфигурацией Intel Dual Core 3Гц, гигабайта оперативной памяти.

4.2 Применение модифицированных RD-деревьев для текстового поиска по подстроке Постановка данной задачи приведена в главе 1 (раздел 1.1.2).

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

Для решения задачи эффективного поиска подстроки в тексте существуют различные индексные МД. В последнее время для этой задачи часто используются суффиксные поисковые структуры данных. Так, например, в работе Андрианова И.А. [16] для этой цели используются (не только для поиска подстроки, а вообще для поиска по регулярным выражениям) так называемые обобщенные суффиксные деревья и предложен ряд их усовершенствований.

В одной из последних работ на эту тему – работе Айткулова П.Г. [14] – используется другая разновидность суффиксных поисковых структур – суффиксные массивы. Данный тип индексов позволяет эффективно решать задачу поиска подстроки, но у него есть серьезные недостатки, которые детально рассмотрены в первой главе. Во-первых, у них очень большие требования к памяти (индекс в десятки раз превышает по размеру исходные данные). Во вторых, даже небольшое изменение данных (вставка, обновление, удаление) приводит к серьезной перестройке суффиксной структуры [14]. Поэтому индексы на основе суффиксных структур применимы только для небольших коллекций статичных данных.

Другой способ индексации текстовых данных, позволяющий эффективно решать задачу поиска подстроки – так называемые строковые B-деревья. Суть данного индексного МД в том, что в B-дерево вставляются все суффиксы индексируемых строк, начиная с самых длинных, и добавляются дополнительные связи между узлами. При этом временная сложность поиска подстроки в наихудшем случае составляет O(log(n)), как и для обычных B-деревьев. Однако сложность вставки в строковое B-дерево, по сравнению с обычным, снижается с O(log(n)) до O(m·log(n+m)), где n – количество проиндексированных строк, m – длина вставляемой строки. Следовательно, время построения такого индекса значительно больше, чем у обычных B-деревьев и сильно зависит от длины индексируемых строк. Кроме того, хотя требования к памяти и неизменные по сравнению с обычными B-деревьями – O(n), фактический размер индекса многократно превышает размер исходных данных (аналогично суффиксным структурам).

Использование же для поиска подстроки модифицированных RD-деревьев лишено данных недостатков. Хотя асимптотика расходования памяти у них та же, что для суффиксных структур – O(n), где n – количество индексируемых строк, фактически RD-дерево имеет многократно меньший размер. Как будет выяснено в этой главе далее, размер модифицированного RD-дерева соизмерим с размером исходных данных. Обновление при вставке/удалении записи для RD-дерева выполняется быстро – за O(log(n)), где n – длина индексируемого текста [58].

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

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

Проверка в реальных условиях реализации поиска текстовых данных по подстроке выполнялась в компании R-Style Softlab (ЗАО «Эр-Стайл Софтлаб») и ВоГУ.

В подсистеме «Расчетный банк» ИБС RS-Bank была существенно ускорена системная процедура проверки клиентов банка на причастность к террорестическим организациям. В данной процедуре основное время занимает поиск банковских документов и клиентов банка, используя различные подстроки.

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

Для экспериментальной проверки использовалась специально подготовленная БД, содержащая свыше 10 тысяч банковских документов (за определенный период, проверяемый процедурой) и более 3 тысяч клиентов. Длительность процедуры проверки на причастность к террорестическим организациям снизилась с пяти минут до порядка 30 секунд. Проверка выполнялась на сервере с конфигурацией Intel Dual Core 3Гц, 2 гигабайта оперативной памяти.

В ВоГУ на кафедре автоматики и вычислительной техники модифицированные RD-деревья использованы для реализации поиска по программному коду решений студентов в системе дистанционного лабораторного практикума по программированию. За годы работы практикума накопились достаточно большие объемы программного кода (несколько гигабайт), поиск в котором по подстроке является очень востребованной задачей. Реализация позволила автоматизировать и многократно ускорить поиск в архиве программного кода решений студентов по сравнению с традиционными способами. Результаты показали, что поиск различных подстрок во всем архиве решений выполняется менее пяти секунд для низкоселективных запросов и порядка полминуты для высокоселективных запросов. Данные результаты являются вполне приемлемыми, учитывая большое количество накопленных в архиве решений. Проверка выполнялась на сервере с конфигурацией AMD Athlon X2 2,8Гц, 1 гигабайт оперативной памяти. Кроме того, результаты работы используются при преподавании курсов «Построение и анализ алгоритмов», «Алгоритмы и структуры данных» и на занятиях научного кружка «Программист».

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

коллекции текстовых документов, содержащих десятки и сотни слов, а не коллекции отдельных строк. Это также соответствует объекту диссертационного исследования.

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

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

Примером индексов, основанных на RD-деревьях, для полнотекстового поиска с использованием хеширования слов в числовые значения может служить модуль tsearch2 для СУБД PostgreSQL [18]. Для полной интеграции с базой данных в модуле tsearch2 создан новый тип данных txtidx. Для работы с числовыми массивами идентификаторов слов используется специальный тип intarray. Пример запроса, выполняющего полнотекстовый поиск с использованием модуля tsearch2, приведен на рисунке 4.1.

select title from titles where titleidx ## 'patch&gist' Рисунок 4.1 – Пример полнотекстового поискового запроса с использованием модуля tsearch2 в СУБД PostgreSQL Здесь таблица titles содержит колонку title (тип text) и соответствующую ей колонку titleidx (тип txtidx). Используется индекс по полю titleidx. Запрос означает «найти все заголовки, содержащие слова 'patch' и 'gist'». При этом операция ## означает, что будут найдены все формы слов (используется морфология) [18].

Таким образом, разработанный индекс на основе RD-деревьев, применительно к полнотекстовому поиску, может быть успешно применен в модуле tsearch2 для СУБД PostgreSQL. В модуле tsearch2 реализованы несколько индексов для числовых массивов идентификаторов слов: на базе структуры GIST, а также на базе структуры GIN (Generalized Inverted Index, обобщенный обратный индекс). Доработанная в данной диссертации структура RD-деревьев может быть достаточно просто применена для индексов на основе структуры GIST, т.к. в ее основе лежат R-деревья – прародители RD-деревьев. Индексы же на основе структуры GIN предназначены главным образом для статических коллекций документов, т.к. эта структура медленно обновляется при вставке/удалении записи [65].

4.3 Реализация индекса на основе модифицированных RD-деревьев для СУБД PostgreSQL Современные реляционные СУБД реализуют поддержку различных типов индексов для ускорения поиска данных. При этом механизмы СУБД, реализующие работу с конкретным типом индексов, образуют индексный метод доступа. МД, как правило, включает в себя следующие процедуры:

создание нового индекса, вставка, обновление и удаление записей из него;

выполнение одного или нескольких видов поиска;

и некоторые другие.

В современных СУБД наиболее распространены индексы, основанные на модификациях B-деревьев, и хеш-индексы. СУБД, поддерживающие работу с геометрическими объектами (например, географическими), активно используют R-деревья [58] (стандарт де-факто для таких данных) и их модификации, а также QD-деревья [55]. Для поддержки полнотекстового поиска, как правило, используются индексы на основе инвертированных, сигнатурных файлов [21,52] и др.

В данной диссертационной работе реализуется индекс, основанный на модифицированных RD-деревьях, для СУБД PostgreSQL [45,65] – СУБД с открытой и расширяемой архитектурой, позволяющей специалистам в конкретной области знаний создавать новые методы доступа, не будучи при этом экспертами разработчиками ядра СУБД [17].

4.3.1 Выбор встроенного в СУБД индекса для его модификации Как было сказано при решении первой практической задачи в разделе 4.1.1, в СУБД существует специальный тип данных intarray, PostgreSQL представляющий собой целочисленный массив. Для этого типа данных в составе СУБД есть целый ряд встроенных индексов. Один из них основан на обобщенном поисковом дереве – GIST [19,20,59]. GIST – это не конкретный индекс, а обобщенный индексный МД для создания пользовательских индексов для различных типов данных. В основе обобщенного поискового дерева в PostgreSQL лежат R-деревья, но абстрагированные от геометрических данных с наличием обобщенного программного интерфейса. Данный интерфейс позволяет с помощью нескольких функций управлять операциями вставки, обновления и удаления из индекса [20]. При этом разработчик сам определяет, какая информация будет храниться в узлах R-дерева (в нашем случае это блюмовские фильтры), как ее нужно обрабатывать и использовать при поиске.

Для данной работы интерес представляет встроенный в СУБД PostgreSQL индекс на основе GIST для числовых массивов, имеющих тип intarray. Этот индекс входит в состав встроенного в PostgreSQL одноименного расширения (extension) – intarray.

Определение 4.1 Расширение (extension) – именованный, версионированный набор взаимосвязанных SQL операторов для внесения в систему крупных изменений как единое целое, т.е. атомарно (аналогично транзакциям). Это является расширением языка SQL, используемом в SQL-диалекте СУБД PostgreSQL.

В основе встроенного индекса для числовых массивов intarray лежит классическое RD-дерево [60]. То есть в качестве сигнатур используются блюмовские фильтры, в которых каждому значению элементов массива соответствует один бит – признак наличия. В данной диссертационной работе разработана модификация именно такой структуры индекса, поэтому апробацию выполненных доработок структур и алгоритмов на СУБД PostgreSQL удобно выполнить, используя данный встроенный индекс.

4.3.2 Доработка операторов сравнения числовых массивов для учета порядка элементов Модифицируемый индекс для числовых массивов из расширения intarray используется для ускорения работы следующих операторов [65]:

1. && (пересечение левого и правого операндов), 2. = (равенство левого и правого операндов), 3. @ (вхождение правого операнда в левый операнд), 4. @ (вхождение левого операнда в правый операнд), 5. @@ (соответствие массива в левом операнде регулярному выражению определенного вида в правом операнде).

В рамках данной работы нас интересуют только операторы @ и @ для определения вхождения массивов друг в друга, поскольку с помощью данных операторов выполняется поиск фрагментов в числовых массивах.

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

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

1. @@ (вхождение правого операнда в левый операнд – аналог @), 2. @@ (вхождение левого операнда в правый операнд – аналог @).

Реализация используемого алгоритма определения вхождения одного массива в другой на языке C++ [44] приведена в приложении В. Данные операторы будут использоваться СУБД автоматически при поиске в случае отсутствия индекса (последовательным перебором), а также для фильтрации «ложных попаданий» при использовании индекса.

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

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

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

Добавленный этап анализа индексируемых данных в алгоритме построения RD-дерева реализуется посредством следующих SQL запросов:

1. SELECT COUNT(*) FROM intarraytable;

Оценка количества записей в индексируемой таблице. Согласно результатам третьей главы достаточно проанализировать не более 10%.

2. SELECT * FROM intarraytable ORDER BY RANDOM() LIMIT (10% зап.);

Выбор случайных 10% записей для анализа и формирования актуального набора разделителей фреймов.

Полученный набор актуальных разделителей фреймов используется уже при построении индекса SQL оператором CREATE INDEX.

Для построения индекса с описанным добавленным этапом анализа данных использована собственная программная реализация на языке C++, использующая программный интерфейс libpq СУБД PostgreSQL [65], для выполнения SQL запросов к данной СУБД.

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

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

4.3.4 Использование сигнатур переменной длины в узлах RD-дерева Согласно оригинальной структуре предложенной RD-деревьев, Хеллерстейном [60] и взятой за основу в данной диссертационной работе, сигнатуры имеют фиксированную длину. При этом единственная хеш-функция, используемая для построения блюмовских фильтров в узлах дерева, выбирает позицию для конкретного значения элементов из предопределенного диапазона битов. Это приводит к тому, что сигнатуры достаточно часто содержат некоторое количество неиспользуемых младших и старших битов, заполненных нулями. Это происходит, когда последовательность содержит только такие значения элементов, которым соответствуют средние биты сигнатуры. Хранить такие пустые «концы» сигнатур слишком расточительно, особенно при использовании однобайтовых сигнатурных элементов. В данном разделе предлагается подход, предполагающий использование сигнатур переменной длины в узлах RD-дерева, исключив из блюмовских фильтров неиспользуемые младшие и старшие сигнатурные элементы.

Рассмотрим построение сигнатур в модифицируемом RD-дерева встроенном в PostgreSQL индексе более детально:

1. Количество сигнатурных элементов фиксировано и составляет 2016;

2. Для определения позиции сигнатурного элемента в блюмовском фильтре для конкретного числового значения используется хеш-функция «остаток от деления» (на размер сигнатуры, 2016).

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

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

Рисунок 4.2 – Изменение узла RD-дерева при использовании сигнатур переменной длины При этом вместо использования хеш-функции «остаток от деления» для связи числового значения массива с позицией сигнатурного элемента используется динамически заполняемая хеш-таблица [42]. При первом запросе на получение позиции сигнатурного элемента для конкретного числового значения в хеш-таблицу добавляется пара позиция в сигнатуре}, которая {число, используется при последующих обращениях к хешу для этого числового значения. Таким образом, хеш-таблица представляет собой ассоциативную коллекцию с быстрым поиском по ключу (реализация основана на B-дереве).

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

Начало Да Число присутствует в хеш-таблице?

Нет Да Размер хеш-таблицы меньше 2016?

Нет В хеш-таблицу добавляется очередная пара {число, позиция} Позиция получается Берется Используется добавленная посредством хеш-функции позиция из позиция «остаток от деления» на 2016 хеш-таблицы Конец Рисунок 4.3 – Алгоритм определения позиции сигнатурного элемента для числа Достоинства предложенного алгоритма, основанного на динамически заполняемой хеш-таблице, по сравнению с оригинальной хеш-функцией «остаток от деления»:

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

2. Снижается количество коллизий при использовании отрицательных чисел и чисел, превышающих 2016. Дело в том, что использование хеш-функции «остаток от деления» в этих случаях приводит к коллизиям. Например, позиция сигнатурного элемента для чисел 3, -253, и 2019 одна и та же – 3. Подобного рода коллизии – одна из причин «ложных попаданий». Таким образом, хеш-функция стала более совершенной. Теперь подобные коллизии могут быть только при превышении максимального размера динамической хеш-таблицы.

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


Экспериментальная проверка на реальных данных эффективности расходования памяти при таком подходе выполнена далее.

4.3.5 Анализ экспериментальных результатов В данном разделе выполним экспериментальную проверку временной эффективности поиска и построения RD-дерева с помощью индекса для СУБД PostgreSQL, основанного на модифицированных RD-деревьях. Кроме того, выполним экспериментальную оценку расходования памяти под индекс.

Экспериментальная проверка выполняется на реальных данных. В качестве таковых использованы числовые массивы в виде бинарного программного кода.

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

Проверка выполнена на коллекции из 10 миллионов числовых последовательностей. Общий объем индексируемых данных при этом составил 2,164 гигабайта.

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

Анализ эффективности построения индекса для PostgreSQL Запросы на языке SQL, необходимые для построения индекса, приведены на рисунке 4.4.

dis_db=# \timing Секундомер включен.

dis_db=# SELECT COUNT(*) FROM intarraytable;

count -------- Время: 1524,177 мс dis_db=# EXPLAIN ANALYZE SELECT * FROM intarraytable dis_db-# ORDER BY RANDOM() LIMIT (1000000);

...

Время: 47281,913 мс dis_db=# CREATE INDEX intarray_modgist_idx ON intarraytable dis_db-# USING gist (intarrayfld gist_modint_ops);

CREATE INDEX Время: 1322692,535 мс // ~22 минуты Рисунок 4.4 – SQL запросы, используемые при построении индекса Как видим, в сумме три необходимых SQL запроса требуют 22,858 минуты.

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

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

По сравнению со встроенным в PostgreSQL индексом время построения модифицированного индекса возросло не более чем на 15%.

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

Для высокоселективного запроса использование индекса не дат существенных преимуществ по сравнению со встроенным в СУБД индексом (не более чем на несколько десятков процентов). На рисунке 4.5 приведен пример высокоселективного поискового запроса с использованием встроенного в СУБД индекса, а также с использованием модифицированного индекса.

Встроенный в СУБД индекс:

dis_db=# EXPLAIN ANALYZE SELECT * FROM intarraytable dis_db-# WHERE intarrayfld @@ '{32,100,97,116,97}';

QUERY PLAN --------------------------------------------------------------- Bitmap Heap Scan on intarraytable (cost=2673.85..36563. rows=10000 width=193) (actual time=5475.272..59956. rows=576380 loops=1) Recheck Cond: (intarrayfld @@ '{32,100,97,116,97}'::integer[]) Rows Removed by Index Recheck: - Bitmap Index Scan on intarray_gist_idx...

Total runtime: 60064.258 ms Модифицированный индекс:

dis_db=# EXPLAIN ANALYZE SELECT * FROM intarraytable dis_db-# WHERE intarrayfld @@ '{32,100,97,116,97}';

QUERY PLAN --------------------------------------------------------------- Bitmap Heap Scan on intarraytable (cost=786.03..34653. rows=10000 width=193) (actual time=2754.926..49252. rows=576380 loops=1) Recheck Cond: (intarrayfld @@ '{32,100,97,116,97}'::integer[]) Rows Removed by Index Recheck: - Bitmap Index Scan on intarray_modgist_idx...

Total runtime: 49318.906 ms // ускорение лишь на 18% Рисунок 4.5 – Эффективность поиска по сравнению со встроенным в СУБД индексом на высокоселективном запросе Из рисунка 4.5 видно, что с использованием индексов отобраны те же 576380 записей, при этом ложных попаданий при использовании обоих индексов было порядка трех миллионов. В результате модифицированный индекс ускорил поиск лишь на 18% по сравнению со встроенным индексом.

Однако для низкоселективных запросов модифицированный индекс существенно ускоряет поиск – до десяти раз (на используемых индексируемых данных). На рисунке 4.6 приведен пример низкоселективного запроса на поиск фрагмента с соседними повторениями и фреймами с использованием встроенного в СУБД индекса, а также с использованием модифицированного индекса.

Встроенный в СУБД индекс:

dis_db=# EXPLAIN ANALYZE SELECT * FROM intarraytable dis_db-# WHERE intarrayfld @@ ' {97,115,32,115,111,111,110,32, 97,115}';

QUERY PLAN --------------------------------------------------------------- Bitmap Heap Scan on intarraytable (cost=2671.38..36562. rows=10000 width=192) (actual time=7049.997..18935. rows=960 loops=1) Recheck Cond: (intarrayfld @@ '{97,115,32,115,111,111,110,32, 97,115}'::integer[]) Rows Removed by Index Recheck: - Bitmap Index Scan on intarray_gist_idx...

Total runtime: 18953.707 ms Модифицированный индекс:

dis_db=# EXPLAIN ANALYZE SELECT * FROM intarraytable dis_db-# WHERE intarrayfld @@ '{97,115,32,115,111,111,110,32, 97,115}';

QUERY PLAN --------------------------------------------------------------- Bitmap Heap Scan on intarraytable (cost=821.42..34713. rows=10000 width=192) (actual time=1576.127..1845. rows=960 loops=1) Recheck Cond: (intarrayfld @@ '{97,115,32,115,111,111,110,32, 97,115}'::integer[]) Rows Removed by Index Recheck: - Bitmap Index Scan on intarray_modgist_idx...

Total runtime: 1859.354 ms // быстрее в 10 раз Рисунок 4.6 – Эффективность поиска по сравнению со встроенным в СУБД индексом на низкоселективном запросе При поиске же фрагментов, на которые распространяются не все три этапа модификации структуры RD-дерева, выигрыш в эффективности несколько меньше, что согласуется с результатами, полученными в третьей главе на собственной программной реализации.

На СУБД PostgreSQL ускорение поиска не на столько существенное по сравнению с оригинальными RD-деревьями, как при использовании собственной программной реализации. Как видно примера запроса, приведенного на рисунке 4.6, снижение количества «ложных попаданий» не так значительно влияет на ускорение поиска, как это было при использовании собственной программной реализации. То есть исключение «ложных попаданий» в СУБД PostgreSQL реализовано более эффективно. Это объясняется тем, что при исключении «ложных попаданий» страницы внешней памяти, к которым приходится обращаться (8 КБ для PostgreSQL) кэшируются в основной памяти [65]. В результате не каждый раз при исключении «ложных попаданий» приходится физически обращаться к внешней памяти, если проверяемая последовательность находится на той же странице, что и предыдущая. В целом же результаты эффективности поиска согласуются с результатами, полученными в третьей главе, но с меньшим эффектом.

Анализ размера индекса для PostgreSQL Для рассмотренной таблицы БД размером 2,164 гигабайта, содержащей миллионов записей, размер встроенного в СУБД индекса составил 4, гигабайта, а размер модифицированного индекса – 1,256 гигабайт. Как видим, в модифицированном индексе удалось не только полностью компенсировать увеличение сигнатурного элемента с одного бита до одного байта, но и уменьшить общий размер индекса почти в четыре раза. Данный результат достигнут благодаря использованию сигнатур переменной длины в узлах RD дерева, что доказывает высокую эффективность такого подхода. Таким образом, размер индекса почти в два раза меньше индексируемых данных.

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

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

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


2. Индекс на основе модифицированных RD-деревьев для поиска текста по подстроке в коллекциях динамических данных размером до нескольких десятков гигабайт является более привлекательным по сравнению с другими типами индексов:

a. RD-деревья во много раз компактнее других индексов, позволяющих искать подстроки в тексте (размер соизмерим с исходными данными).

b. RD-деревья быстро строятся и обновляются, в отличие от других альтернативных типов индексов для данной поисковой задачи.

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

4. Разработан индекс, на основе модифицированных RD-деревьев, для СУБД PostgreSQL. За основу взят встроенный в СУБД индекс, основанный на классических RD-деревьях. Экспериментальная проверка показала:

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

b. Индекс на высокоселективных поисковых запросах не дает существенных преимуществ по сравнению со встроенным индексом.

c. На низкоселективных запросах индекс существенно ускоряет поиск по сравнению со встроенным индексом (до 10 раз).

d. Удалось полностью компенсировать увеличение размера индекса и даже снизить его в несколько раз.

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

ЗАКЛЮЧЕНИЕ В диссертационной работе разработана модификация структуры RD деревьев, алгоритмов их построения и использования применительно к поиску последовательностей по фрагменту. Можно выделить следующие основные выводы и результаты:

1. Временная сложность построения для RD-деревьев n последовательностей элементов составляет O(n·log(n)) [43] и не зависит от длины последовательностей. При этом RD-деревья очень компактные, при асимптотике расходования памяти O(n) их фактический размер соизмерим с размером исходных данных. Однако RD-деревья не гарантируют приемлемой временной n сложности поиска: в наихудшем случае – O(n), в среднем случае – O( ). При log( n) этом они хорошо работают на реальных данных. В разработанной модификации RD-деревьев в значительной степени устранена причина неточности поиска – «ложные попадания». В результате существенно ускоряется поиск последовательностей по фрагменту без изменения асимптотических характеристик RD-дерева.

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

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

3. Экспериментально доказана высокая степень применимости выполненных модификаций. Доля перечисленных выше типов искомых фрагментов от общего количества всех возможных фрагментов близка к 100% при достаточно большой длине фрагментов (7 и более). На более коротких искомых фрагментах применимость модификации несколько меньше.

4. Доработан алгоритм построения RD-дерева посредством добавления в него этапа анализа индексируемых данных. Для этого выработаны необходимые критерии и разработан вспомогательный алгоритм для формирования набора разделителей фреймов, актуального для содержимого БД. Время анализа при этом составляет около 11% от общего времени построения RD-дерева. Использование актуального для содержимого БД набора разделителей фреймов при построении индекса дополнительно ускоряет поиск на 10-40%.

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

6. В несколько раз уменьшен размер индекса, основанного на RD-дереве, благодаря использованию сигнатур переменной длины в узлах дерева. Этого удалось добиться, несмотря на добавление в узлы RD-дерева новых данных.

7. Разработан и внедрен новый индекс для конкретной СУБД с открытым исходным кодом для ускорения поиска последовательностей по фрагменту.

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

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

СПИСОК ЛИТЕРАТУРЫ 1. Чернов, А.Ф. Ускорение поиска в индексах на основе R-деревьев // Программные продукты и системы, 2012. №2 (98), С. 46 - 50.

2. Чернов, А.Ф., Андрианов И.А. Оптимизация разбиения данных в индексах на основе R-деревьев // Системы управления и информационные технологии, 2011.

№4 (46), С. 18 - 22.

3. Чернов, А.Ф. Модификация индексов на основе R-деревьев для ускорения поиска // Информационные системы и технологии, 2011. №6 (68), С. 10 - 18.

4. Андрианов, И.А. Индексирование и поиск в последовательностях для больших баз данных: монография / И.А. Андрианов, А.Ф. Чернов. – Вологда, ВоГУ, 2013. – 165 с.

5. Чернов, А.Ф. Сравнение обобщенных методов доступа к данным на основе GIST и GIN индексов / А.Ф. Чернов // Вузовская наука региону: материалы седьмой Всерос. науч.-техн. конф. В 2-х т., г. Вологда, 27 февраля 2009 г. – Вологда, 2009. – Т. 1. – С. 103 - 105.

6. Чернов, А.Ф. Ускорение поиска пространственных данных с использованием индексов на основе R-деревьев / А.Ф. Чернов // Молодые исследователи – регионам: материалы Всерос. науч. конф. студентов и аспирантов. В 2-х т., г.

Вологда, 16-18 апреля 2009 г. – Вологда, 2009. – Т. 1. – С. 110 - 111.

7. Чернов, А.Ф. Использование сигнатур переменной длины в индексах на основе R-деревьев / А.Ф. Чернов // материалы III ежегод. смотров-сессий аспирантов и молодых ученых по отраслям наук: в 2-х т., г. Вологда, 18-19 ноября 2009 г. – Вологда, 2009. – Т. 2.: Экономические науки. – С. 264 - 268.

8. Чернов, А.Ф. Модификация сигнатур в индексах на основе R-деревьев / А.Ф.

Чернов // Молодые исследователи – регионам: материалы Всерос. науч. конф. В 2 х т., г. Вологда, 22-23 апреля 2010 г. – Вологда, 2010. – Т. 1. – С. 149 - 151.

9. Чернов, А.Ф. Ускорение поиска в индексах на основе R-деревьев с помощью разбиения индексируемых данных / А.Ф. Чернов // материалы IV ежегод.

смотров-сессий аспирантов и молодых ученых по отраслям наук: Технические науки. Экономические науки., г. Вологда, 15-16 декабря 2010 г. – Вологда, 2010. – С. 79 - 84.

10. Чернов, А.Ф. Оптимизация использования разбиения данных для ускорения поиска в индексах на основе R-деревьев / А.Ф. Чернов // Молодые исследователи – регионам: материалы Всерос. науч. конф. В 2-х т., г. Вологда, 21-22 апреля г. – Вологда, 2011. – Т. 1. – С. 109 - 111.

Чернов, А.Ф. Математический анализ эффективности поиска с 11.

использованием индексов на основе R-деревьев / А.Ф. Чернов // Автоматизация и энергосбережение машиностроительного и металлургического производств, технология и надежность машин, приборов и оборудования: материалы седьмой Междунар. науч.-техн. конф., г. Вологда, 13-15 марта 2012 г. – Вологда, 2012. – С.

352 - 355.

12. Чернов, А.Ф. Доработка разбиения данных в индексах на основе R-деревьев для достижения универсальности / А.Ф. Чернов // Вопросы образования и науки в XXI веке: материалы Междунар. науч.-практ. конф. В 11 ч., г. Тамбов, 29 апреля 2013 г. – Тамбов, 2013. – Ч. 11. – С. 116 - 119.

13. Чернов, А.Ф. Оптимизация размера сигнатур GIST индекса в СУБД PostgreSQL / А.Ф. Чернов // Современное общество, образование и наука:

материалы Междунар. науч.-практ. конф. В 5 ч., г. Тамбов, 31 июля 2013 г. – Тамбов, 2013. – Ч. 4. – С. 140 - 142.

14. Айткулов П.Г. Исследование и разработка методов и алгоритмов обработки символьных массивов в базах данных / П.Г. Айткулов;

дис. … канд. техн. наук. – Москва: Институт проблем управления им. В. А. Трапезникова РАН, 2010. – 97 с.

15. Андерсон, Дж. Дискретная математика и комбинаторика / Дж. Андерсон;

пер.

с англ. – М.: Изд-во «Вильямс», 2004. – 960 с.

16. Андрианов И.А. Анализ и разработка способов индексирования текстов на основе обобщенных и неплотных суффиксных деревьев / И.А. Андрианов;

дис. … канд. техн. наук. – СПб.: Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина), 2005. – 138 с.

17. Бартунов, О. С. Специализированные типы данных для цифровых библиотек / О. С. Бартунов // http://www.sai.msu.su/~megera/postgres/talks/RCDL2007.oleg.pdf 18. Бартунов, О.С., Сигаев Т.Г. Tsearch2 - full text extension for PostgreSQL / О.С.

Бартунов, Т.Г. Сигаев // http://www.sai.msu.su/~megera/postgres/gist/tsearch/V2/ 19. Бартунов, О.С., Сигаев, Т.Г. Научная сеть: алгоритмы и структуры данных / О.С. Бартунов, Т.Г. Сигаев // http://www.sai.msu.su/~megera/postgres/gist/doc/algo.shtml 20. Бартунов, О.С., Сигаев, Т.Г. Написание расширений для PostgreSQL с использованием GiST / О.С. Бартунов, Т.Г. Сигаев // http://www.sai.msu.su/~megera/postgres/talks/gist_tutorial.html Бойцов Л.М. Синтез системы автоматической коррекции, индексации и 21.

поиска текстовой информации / Л.М. Бойцов;

дис. … канд. техн. наук. – М.:

Московская академия рынка труда и информационных технологий, 2003. – 144 с.

22. Гречкосий, Г. Индексы. Теоретические основы. / Г. Гречкосий // http://www.sql.ru/articles/mssql/03013101indexes.shtml# 23. Еманов, Д. Firebird: методы доступа к данным / Д. Еманов // http://www.ibase.ru/devinfo/dataaccesspaths.htm#root 24. Кантор, И. Б, Б+ и Б++ деревья / И. Кантор // http://algolist.ncstu.ru/ds/s_btr.php 25. Кантор, И Хеш-таблицы / И. Кантор // http://algolist.manual.ru/ds/s_has.php Каратаев, Е. Битмап индекс (bitmap / Е. Каратаев 26. index) // http://karataev.nm.ru/ind/bitmap.html 27. Каратаев, Е. Хеш-индекс / Е. Каратаев // http://karataev.nm.ru/ind/hash.html 28. Ключаев, А.А., Матьяш, В.А., Щекин, С.В. Структуры и алгоритмы обработки данных: учебное пособие / А.А. Ключаев, В.А. Матьяш, С.В. Щекин – СПб.:

СПбГУАП, 2003. – 172 с.

29. Кнут, Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы / Д. Кнут;

пер. с англ. – М.: Изд-во "Вильямс", 2000. - 720 c.

30. Кнут, Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы / Д. Кнут;

пер. с англ. – М.: Изд-во "Вильямс", 2000. - 500 c.

31. Кнут, Д. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск / Д.

Кнут;

пер. с англ. – М.: Изд-во "Вильямс", 2000. - 832 c.

32. Колесов Д.А. Приближенный поиск в базах данных на основе метрических деревьев / Д.А. Колесов;

дис. … канд. техн. наук. – Казань: Казанский государственный технический университет им. А. Н. Туполева, 2006. – 142 с.

33. Колмогоров, А.Н., Журбенко, И.Г., Прохоров, А.В. Введение в теорию вероятностей. 2-е изд. / А.Н. Колмогоров, И.Г. Журбенко, А.В. Прохоров – М.:

Физматлит, 1995. – 176 с.

34. Кормен, Т. Алгоритмы: построение и анализ. 3-е изд. / Т. Кормен, Ч.

Лейзерсон, Р. Ривест, К. Штайн;

пер. с англ. - М.: Изд-во "Вильямс", 2013. - с.

35. Крнке Д. Теория и практика построения баз данных. 8-е изд. / Д. Крнке – СПб.: Питер, 2003. – 800 с.

36. Кузнецов, С.Д. Методы сортировки и поиска / С.Д. Кузнецов // http://citforum.ru/programming/theory/sorting/sorting1.shtml 37. Льюис, Д. Понимание индексов на основе битовых карт / Д. Льюис // http://www.s-networks.ru/index-674.htm 38. Льюис, Д. Разбираемся с индексами на основе битовых карт / Д. Льюис // http://citforum.ru/database/oracle/bitmap_index/ 39. Малайка, С., Никола М. Пересмотр взглядов на нормализацию данных: Часть 1. История бизнес-записей / С. Малайка, М. Никола // https://www.ibm.com/developerworks/ru/library/dm-1112normalization/ 40. Малайка, С., Никола М. Пересмотр взглядов на нормализацию данных: Часть 2. Бизнес-записи в 21 веке / С. Малайка, М. Никола // https://www.ibm.com/developerworks/ru/library/dm-1201normalizationpart2/ 41. Райордан, Р. Основы реляционных баз данных / Р. Райордан;

Пер. с англ. – М.:

Издательско-торговый дом «Русская Редакция», 2001. – 384 с.

42. Седжвик, Р. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск. Часть 1-4 / Р. Седжвик: пер. с англ. – К.: Издательство «ДиаСофт», 2002 - 688.

43. Скворцов, А.В. Глобальные алгоритмы построения R-деревьев / А.В.

Скворцов – Томск: Томский государственный университет, 1999. – 17 с.

44. Страуструп, Б. Язык программирования C++. Специальное издание. / Бьерн Страуструп;

пер. с англ. – СПб.: Невский диалект;

Бином, 2004. – 1104 с.

45. Уорсли, Дж. PostgreSQL. Для профессионалов (+CD-ROM) / Дж. Уорсли, Дж.

Дрейк;

Пер с англ. – СПб.: Питер, 2003. – 496 с.

46. Фридл, Дж. Регулярные выражения. 2-е изд. / Дж. Фридл. – СПб.: Питер, 2003.

– 464 с.

47. Холл, М. Комбинаторика / М. Холл;

пер. с англ. С.А. Широковой – М.: Изд-во «Мир», 1970. – 424 с.

Хусаинов, Б.С. Структуры и алгоритмы обработки данных. Примеры на 48.

языке Си / Б.С. Хусаинов – М: “Финансы и статистика”, 2004. – 464 c.

49. Antognini, C. Bloom Filters / C. Antognini // Trivadis AG, Zrich, Switzerland. 2008.

50. Arge, L. The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R Tree / L. Arge, M. De Berg, H. Haverkort, K. Yi // ACM Transactions on Algorithms Vol. 4. - 2008. - P. 165-194.

51. Bloom, Burton H. Space/time trade-offs in hash coding allowable errors / Burton H.

Bloom // Communications of the ACM Vol. 13. - 1970. - P. 422-426.

52. Blumer, A. Complete inverted files for efficient text retrieval and analysis / A.

Blumer, J. Blumer, D. Haussler, R. McConnell, D. Ehrenfeucht // J. ACM. - 1987. - P.

578-595.

53. Boytsov, L. Indexing methods for approximate dictionary searching: Comparative analysis / L. Boytsov // ACM Journal on Experimental Algorithmics Vol. 16. - 2011. 91 p.

54. Date, C. J. An Introduction to Database Systems, 8th Edition. / C.J. Date // Addison Wesley Longman, ISBN 0-321-19784-4. - 1999.

55. Finkel, Raphael A. Quad Trees: A Data Structure for Retrieval on Composite Keys / Raphael A. Finkel, Jon Louis Bentley // Acta Informatica Vol. 4. - 1974. - P. 1-9.

56. Garcia, Y.J. A greedy algorithm for bulk loading R-trees. / Y.J. Garcia, M.A. Lopez, S.T. Leutenegger // Proc. 6th ACM Symposium on Advances in GIS. - 1998. - P. 163 164.

57. Gennick, J. Oracle regular expressions pocket reference / J. Gennick, P. Linsley // O’Reilly. - 2003. - 64 p.

58. Guttman, A. R-trees: A Dynamic Index Structure For Spatial Searching / A.

Guttman // Proc. ACM SIGMOD Int. Conf. on Management of Data. - 1984. - P. 47-57.

59. Hellerstein, Joseph M. Generalized search trees for database systems / Joseph M.

Hellerstein, Jeffrey F. Naughton, Avi Pfeffer // Morgan Kaufmann Publishers Inc.

Morgan Kaufmann Series In Data Management Systems. Readings in database systems (3rd ed.). - 1998. - P. 101-112.

60. Hellerstein, Joseph M. The RD-tree: an index structure for sets / Joseph M.

Hellerstein // University of Wisconsin at Madison. Technical Report №1252. -1994.

61. ISO/IEC 9075-1:2008. Information technology – Database languages – SQL – Part 1: Framework (SQL/Framework), 2008.

62. Kamel, I. Hilbert R-tree: An Improved R-tree using Fractals / I. Kamel, C. Faloutsos // Proc. 20th ACM Int. Conf. on Very Large Data Bases. - 1994. - P. 500-509.

63. Maab, M. Suffix Trees and their Applications / M. Maab // Technische Universi at Munchen. - 1999.

64. Manning, С., Schutze, H. Foundations of Statistical Natural Language Processing / С. Manning, H. Schutze // MIT Press. - 1999.

65. PostgreSQL documentation // http://www.postgresql.org/docs/ Приложение А (обязательное) Алгоритм поиска фрагмента в последовательностях по RD-дереву Алгоритм поиска приведен на рисунке А.1.

Искомый Начало фрагмент F Построение сигнатуры фрагмента SF Для внутренних узлов Считывание корневого узла (под)дерева ссылки на поддеревья потомки, для листьев – Обход ссылок на хранимые после узла, пока не довательности.

закончились Условие включения Получение сигнатуры сигнатур друг в друга текущей ссылки Si Нет SF включена в Si? Да Да Нет Считывание Ссылаемся на последовательности Qi поддерево?

Включение найденной Да F содержится последовательности Qi в Qi?

в результат поиска Нет Обход ссылок узла Нет Обход был для корня?

Да Конец Рисунок А.1 – Алгоритм поиска фрагмента в последовательностях по RD-дереву Приложение Б (справочное) Алгоритм программы для определения степени применимости модификаций RD-дерева Собственная программная реализация на языке C++ выполнена для экспериментальной оценки степени применимости выполненных модификаций RD-деревьев к всевозможным искомым фрагментам в последовательностях.

Алгоритм работы программы приведен на рисунке Б.1.

Последователь Начало ности в БД Ввод длины искомых фрагментов L Обход таблицы БД, пока есть последовательности Q Взятие фрагмента F длиной L от начала последовательности F содержит Да Нет F помещается фреймы или в Qi?

повторения?

Нет Да F не учитывается F учитывается Обход таблицы БД в результате в результате Расчет долей фрагментов, к которым применимы три Сдвиг F на 1 влево в Qi этапа модификации Доли фрагментов, отража ющие степень примени- Конец мости модификаций Рисунок Б.1 – Алгоритм для определения степени применимости модификаций RD дерева Приложение B (справочное) Реализация определения вхождения числовых массивов друг в друга, учитывающая порядок элементов Вхождение одного числового массива в другой согласно разделу 4.3.1 – алгоритм на языке программирования C++ для определения вхождения одного числового массива в другой, учитывая порядок расположения элементов. Используется в реализации новых операторов @@ и @@ в СУБД PostgreSQL, для ускорения работы которых разработан индекс на основе RD-деревьев.

Входные данные:

arr1 – указатель на начало объемлющего массива, arr1Size – размер объемлющего массива, arr2 – указатель на начало внутреннего массива, arr2Size – размер внутреннего массива.

Выходные данные:

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

static bool Arr1EqualArr2SameNotZeroSize(int4 *arr1, int4 *arr2, uint32 notZeroArrSize) { for (uint32 i = 0;

i notZeroArrSize;

++i) if (arr1[i] != arr2[i]) return false;

return true;

} bool Arr1ContainsArr2(int4 *arr1, uint32 arr1Size, int4 *arr2, uint32 arr2Size) { if (!arr2Size) return true;

if (arr1Size arr2Size) return false;

if (arr1Size == arr2Size) return Arr1EqualArr2SameNotZeroSize(arr1, arr2, arr1Size);

// arr1Size arr2Size for (uint32 i = 0;

i = arr1Size-arr2Size;

++i) if (Arr1EqualArr2SameNotZeroSize(arr1 + i, arr2, arr2Size)) return true;

return false;

}

Pages:     | 1 | 2 ||
 





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

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