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

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

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


Pages:   || 2 | 3 |
-- [ Страница 1 ] --

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Санкт-Петербургский государственный электротехнический

университет «ЛЭТИ» им. В.И. Ульянова (Ленина)»

На правах рукописи

Чернов Андрей Федорович

АНАЛИЗ И РАЗРАБОТКА ИНДЕКСА

ДЛЯ ПОИСКА ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЭЛЕМЕНТОВ ПРОИЗВОЛЬНОГО ТИПА ПО ИХ ФРАГМЕНТАМ В РЕЛЯЦИОННЫХ БАЗАХ ДАННЫХ 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель:

Кандидат технических наук, Доцент, Андрианов Игорь Александрович Санкт-Петербург – ОГЛАВЛЕНИЕ Список сокращений.................................................................................................. ВВЕДЕНИЕ................................................................................................................. ГЛАВА 1. Постановка задач исследования. Анализ способов индексации данных. Выбор структур и алгоритмов....................................... 1.1 Постановка решаемых прикладных задач........................................................ 1.1.1 Задача поиска по фрагменту в числовых массивах.................................. 1.1.2 Задача текстового поиска по подстроке.................................................... 1.2 Анализ способов индексации данных и выбор типа индекса для последовательностей элементов.............................................................................. 1.2.1 Индексы на основе битовых карт............................................................... 1.2.2 Hash-индексы................................................................................................ 1.2.3 Индексы на основе B-деревьев................................................................... 1.2.4 Индексы на основе B+-деревьев................................................................. 1.2.5 Индексы на основе суффиксных структур данных.................................. 1.2.6 Индексы на основе R-деревьев................................................................... 1.2.7 Индексы на основе RD-деревьев................................................................ 1.2.8 Выбор структуры индекса для индексации последовательностей......... 1.3 Постановка задач дальнейшего исследования................................................. Выводы по главе 1..................................................................................................... ГЛАВА 2. Разработка модификации структуры RD-деревьев и эффективных алгоритмов поиска с ней............................................................. 2.1 Асимптотический анализ алгоритмов работы с RD-деревом........................ 2.1.1 Анализ сложности поиска фрагмента в последовательностях по RD-дереву для среднего случая........................................................................... 2.2 Анализ причин «ложных попаданий» при поиске по RD-дереву.................. 2.3 Математическая оценка количества «ложных попаданий» при поиске по RD-дереву............................................................................................................. 2.3.1 Вычисление количества комбинаций последовательностей с повторяющимися элементами............................................................................. 2.3.2 Оценка количества «ложных попаданий» при поиске по RD дереву..................................................................................................................... 2.4 Модификация структуры RD-дерева для минимизации «ложных попаданий»................................................................................................................. 2.4.1 Этап 1: добавление в индекс информации о количестве одинаковых элементов в последовательностях................................................. 2.4.2 Этап 2: добавление в индекс признаков повторения элементов подряд в последовательностях............................................................................. 2.4.3 Этап 3: использование разбиения последовательностей для учета порядка расположения элементов....................................................................... Выводы по главе 2..................................................................................................... ГЛАВА 3. Выбор параметров алгоритмов построения и использования RD-деревьев. Экспериментальная проверка эффективности....................... 3.1 Экспериментальная проверка эффективности поиска с использованием модифицированных RD-деревьев............................................... 3.1.1 Используемые средства для проверки эффективности............................ 3.1.2 Оценка количества «ложных попаданий» при поиске на случайных данных................................................................................................. 3.1.3 Результаты экспериментальной проверки эффективности поиска......... 3.1.4 Оценка зависимости эффективности поиска от размера БД................. 3.2 Доработка алгоритма построения RD-дерева для эффективности разбиения последовательностей на фреймы........................................................ 3.2.1 Разработка алгоритма анализа данных для формирования актуальных разделителей фреймов для содержимого БД.............................. 3.2.2 Экспериментальная проверка корректности формирования актуальных разделителей фреймов................................................................... 3.2.3 Экспериментальная проверка эффективности поиска с использованием доработанного алгоритма построения RD-дерева.............. 3.3 Оценка степени применимости выполненной модификации RD деревьев к различным искомым данным.............................................................. 3.4 Оценка влияния выполненной модификации RD-деревьев на время построения индекса................................................................................................. 3.4.1 Оценка зависимости времени построения от размера БД..................... Выводы по главе 3................................................................................................... ГЛАВА 4. Применение полученных результатов для практических задач......................................................................................................................... 4.1 Применение модифицированных RD-деревьев для поиска по фрагменту в числовых массивах........................................................................... 4.2 Применение модифицированных RD-деревьев для текстового поиска по подстроке............................................................................................................ 4.2.1 Применение модифицированных RD-деревьев полнотекстового поиска с использованием хеширования слов................................................... 4.3 Реализация индекса на основе модифицированных RD-деревьев для СУБД PostgreSQL.................................................................................................... 4.3.1 Выбор встроенного в СУБД индекса для его модификации................. 4.3.2 Доработка операторов сравнения числовых массивов для учета порядка элементов............................................................................................... 4.3.3 Модификация структуры индекса и алгоритмов работы с ним............ 4.3.4 Использование сигнатур переменной длины в узлах RD-дерева......... 4.3.5 Анализ экспериментальных результатов................................................. Выводы по главе 4................................................................................................... ЗАКЛЮЧЕНИЕ..................................................................................................... СПИСОК ЛИТЕРАТУРЫ................................................................................... Приложение А (обязательное) Алгоритм поиска фрагмента в последовательностях по RD-дереву................................................................... Приложение Б (справочное) Алгоритм программы для определения степени применимости модификаций RD-дерева.......................................... Приложение B (справочное) Реализация определения вхождения числовых массивов друг в друга, учитывающая порядок элементов....... Список сокращений ИПС Информационно-поисковая система МД Метод доступа (к данным) СУБД Система управления базой данных БД База данных ПО Программное обеспечение Обобщенное поисковое дерево (General Information Search Tree) GIST ВВЕДЕНИЕ Актуальность работы. В современном мире огромную роль играют информационно-поисковые системы (ИПС). Информационные технологии проникают во все сферы человеческой деятельности. На сегодняшний день невозможно себе представить отсутствие электронного хранения информации с поддержкой соответствующих способов ее эффективного поиска. На темы, связанные с поиском информации, ее отбором из огромных объемов данных, пишется большое количество научных трудов [14,16,21,32], появляются новые способы поиска, постоянно совершенствуются существующие алгоритмы [50]. К настоящему времени в многочисленных ИПС накоплены колоссальные объемы информации, и ни на минуту не замедляются темпы их роста. Все это приводит к постоянному росту нагрузки и, как следствие, к росту требований к поисковым системам, что подчеркивает актуальность и значимость исследований в области информационного поиска.

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

Для стандартных типов данных (числа, даты и т.п.) к настоящему времени разработано много эффективных МД, реализованных в современных системах управления базами данных (СУБД). Кроме того, хорошо проработан и реализован в большом количестве ИПС текстовый поиск – словарный поиск, полнотекстовый поиск [18], поиск по различным шаблонам [16] и т.д. Однако для этих и других типов данных, которые также важны и востребованы на практике, в области информационного поиска еще остается немало проблем и актуальных вопросов.

Для многих типов данных, помимо поиска на точное равенство, развиваются возможности нечеткого поиска [53], приближенного поиска по сходству [32] и др.

Вопросам проектирования структур данных и алгоритмов информационного поиска посвящены работы Д. Хеллерстейна, А. Гуттмана, Р.

Финкеля, М. Никола и других. Из отечественных публикаций можно выделить работы О. С. Бартунова, Т. Г. Сигаева, И. А. Андрианова, П. Г. Айткулова, Л. М.

Бойцова и других. Особенно значимыми для данной диссертации явились работы Д. Хеллерстейна, О. С. Бартунова и Т. Г. Сигаева в области использования различных структур данных для информационного поиска.

Практически все современные МД к данным объединяет то, что для данных строятся специальные вспомогательные поисковые структуры – индексы, использование которых позволяет существенно сократить время поиска информации. Например: битовые карты, B-деревья и их модификации, R-деревья и их модификации, суффиксные структуры данных и др.

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

При поиске числовых массивов по их фрагменту, как правило, не учитывается порядок следования элементов (например, RD-деревья в СУБД PostgreSQL [19,65]), Для обеспечения поиска строк по подстроке, как правило, требуется большое количество памяти под индекс, многократно превышающее размер самих данных (например, суффиксные структуры [14,16], которые, к тому же, требуют серьезного перестроения даже при небольших изменениях данных), Не существует единого индексного МД, применяемого для последовательностей элементов любого типа.

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

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

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

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

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

2. Модификация выбранной поисковой структуры и алгоритмов работы с ней для ускорения поиска последовательностей по фрагменту.

3. Разработка программных реализаций модифицированной структуры индекса.

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

5. Внедрение результатов работы в деятельность конкретных организаций.

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

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

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

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

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

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

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

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

Практическую значимость имеют следующие полученные в диссертации результаты:

Разработанный индекс для СУБД PostgreSQL, основанный на 1.

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

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

Прикладное программное обеспечение (ПО), основанное на 3.

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

На защиту выносятся следующие основные результаты и положения:

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

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

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

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

седьмая всероссийская научно-техническая конференция «Вузовская наука региону» (Вологда, ВоГТУ, 2009 г.), всероссийская научная конференция «Молодые исследователи – регионам» (Вологда, ВоГТУ, 2009, 2010, 2011 гг.), III ежегодные смотры-сессии аспирантов и молодых ученых по отраслям наук (Вологда, ВоГТУ, 2009 г.), IV ежегодные смотры-сессии аспирантов и молодых ученых по отраслям наук (Вологда, ВоГТУ, 2010 г), седьмая международная научно-техническая конференция «Автоматизация и энергосбережение машиностроительного и металлургического производств, технология и надежность машин, приборов и оборудования» (Вологда, ВоГТУ, 2012), научный семинар вологодского регионального отделения Научного совета РАН по методологии искусственного интеллекта (Вологда, ВГПУ, 2013 г.), международная научно-практическая конференция «Вопросы образования и науки в XXI веке» (Тамбов, ИПК, 2013 г.), международная научно-практическая конференция «Современное общество, образование и наука» (Тамбов, ИПК, г.).

Кроме того, материалы работы использованы в Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на годы: «Разработка методов формализации и верификации 2009- распределенных информационно-поисковых систем на основе сервис ориентированной архитектуры».

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

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

интегрированной банковской системы (ИБС) RS-Bank была реализована возможность эффективного поиска по фрагменту в числовых массивах, отражающих хронологию выполнения операций. В числовых массивах хранились идентификаторы операций, выполненных по кредитному договору. Таким образом, примененный индексный метод позволил упростить формулировку и ускорить поисковые запросы конкретной последовательности выполненных операций.

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

Также результаты работы используются в учебном процессе кафедры автоматики и вычислительной техники Вологодского государственного университета (ВоГУ) для реализации поиска по программному коду в системе дистанционного лабораторного практикума по программированию, а также при преподавании курсов «Построение и анализ алгоритмов», «Алгоритмы и структуры данных» и на занятиях научного кружка «Программист».

Публикации результатов исследования. Основное содержание диссертационной работы опубликовано в 13 научных работах [1-13], среди которых 3 публикации в ведущих рецензируемых изданиях, рекомендованных ВАК, 1 монография и 9 докладов в материалах международных, национальных и региональных конференций.

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

Работа содержит 156 страниц машинописного текста, включая 49 рисунков и таблиц. Библиографический список включает 65 наименований.

ГЛАВА 1. Постановка задач исследования. Анализ способов индексации данных. Выбор структур и алгоритмов Объектом данного диссертационного исследования являются коллекции последовательностей элементов произвольного типа. Для однозначности определим, что будем считать в данной работе последовательностью элементов.

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

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

1.1.1 Задача поиска по фрагменту в числовых массивах Числовые массивы в роли последовательностей элементов удобно использовать для отражения хронологии каких-либо событий. Это могут быть последовательности состояний, в которых искомые объекты находились на протяжении своего существования, либо последовательности произведенных с объектами операций и т.д. При этом предполагается, что эти состояния/операции объектов имеют числовые идентификаторы, тем самым хронология их изменений технически представляет собой числовую последовательность.

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

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

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

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

Нормализация данных впервые была представлена в 1970 году и к настоящему времени очень хорошо и широко документирована [35,41,54]. Нормализация данных – это методика для формирования набора таблиц, которые представляют реальные бизнес-записи в базе данных, что полностью избавляет от дублирования данных в условиях высокой стоимости ресурсов хранения [39]. Разработка нормализации данных была выполнена под влиянием действовавших в то время мощных побудительных причин – дисковое пространство было дефицитным и дорогостоящим [39]. В результате общепринятым подходом стало преобразование бизнес-записей в нормализованное представление для компьютеров (и обратно) [39]. Фактически в сформированном наборе таблиц дублируются лишь значения ключей, связывающих таблицы, а основные элементы данных хранятся ровно один раз. В результате нормализации данных одна бизнес-запись может быть представлена посредством десятков или даже сотен таблиц [39]. Нормализованная схема базы данных – неестественное представление бизнес-записей, очень трудное для понимания бизнес-пользователями и неэффективное для формулировки и обработки аналитических бизнес-запросов. [39] Такая оптимизированная с точки зрения памяти структура хранения данных очень трудна для понимания и требует специальных механизмов для управления всеми задействованными таблицами, что существенно усложняет формулировку и обработку поисковых запросов.

Рассмотрим актуальный пример, требующий поиска хронологических числовых последовательностей элементов. Имеется БД кредитных договоров в коммерческом банке. По каждому договору в хронологическом порядке выполнено десятки и сотни операций (выдача кредита, погашение, вынос на просрочку и др.). Необходимо ускорить поиск кредитных договоров в запросах типа: «найти все договоры, по которым после выдачи кредита было не менее двух погашений подряд». На рисунке 1.1 приведена схема хранения данных, соответствующая третьей нормальной форме [35,41], которая в настоящее время является стандартом де-факто при проектировании БД.

Рисунок 1.1 – Нормализованная схема БД В данном случае таблица «операции_по_договорам» является синтетической (не естественной), полученной в результате нормализации данных.

В таблице 1.1 приведен пример содержимого данной таблицы БД.

Таблица 1.1 – Пример содержимого таблицы БД «операции_по_договорам»

идент_договора пор_номер_операции идент_операции … 1 (выдача) – 1 2 (погашение) – 1 3 (вынос на просрочку) – 1 1 (выдача) – 2 2 (погашение) – 2 2 (погашение) – 2 В данном случае требуемый поисковый запрос «найти все договоры, по которым после выдачи кредита было не менее двух погашений подряд» на языке SQL [61] формулируется сравнительно сложно (см. рисунок 1.2). Современные СУБД не позволяют эффективно выполнить такой поиск даже с использованием индексов. Приходится использовать такие неэффективные по быстродействию SQL-операторы, как IN, EXISTS, а также вложенные запросы. В результате такой поисковый запрос выполняется медленно.

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

Поэтому в последнее время для удобства/возможности выполнять различные поисковые запросы, используя индексные структуры, все чаще прибегают к изменению логической структуры БД – сознательной денормализации [39,40]. Денормализация заключается в хранении бизнес-записей без их декомпозиции на несколько таблиц, что позволяет:

во-первых, формулировать поисковые запросы более лаконично (например, на языке SQL [61]), что приводит к ускорению их выполнения, во-вторых, эффективно использовать индексы, что также приводит к ускорению поиска.

Возвращаясь к примеру с кредитными договорами в коммерческом банке, в результате денормализации можно удалить синтетическую таблицу «операции_по_договорам» из схемы БД (рисунок 1.3).

Рисунок 1.3 – Денормализованная схема БД Таким образом, хронологическая последовательность операций, выполненных по каждому договору, хранится в самой таблице «кредитные_договоры» в виде числового массива «выполненные_опер». В этих числовых последовательностях достаточно просто выполнить поиск по фрагменту. На рисунке 1.4 приведена формулировка требуемого поискового запроса «найти все договоры, по которым после выдачи кредита было не менее двух погашений подряд» на языке SQL (используется специальный оператор @, означающий поиск по фрагменту).

Рисунок 1.4 – Пример поискового запроса к денормализованным данным Для ускорения подобных поисковых запросов становится возможным использование индексных МД, используя индексацию числовых последовательностей, что является целью данной диссертационной работы.

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

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

1.1.2 Задача текстового поиска по подстроке Текстовые данные представляют собой последовательности символов, что также является объектом данного исследования. При этом поиск по фрагменту для текста формулируется как поиск подстроки. Для хранения текстовых данных в большинстве случаев используются обычные реляционные СУБД. Данная практическая задача направлена на точный поиск подстрок в текстовых полях БД, не накладывая ограничений на длину искомых подстрок и статичность индексируемых данных.

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

Текстовые данные занимают огромную часть накопленной на данный момент информации: персональные данные людей, содержимое web-сайтов, различная справочная информация, техническая документация и пр. Поэтому необходимость быстрого поиска текстовой информации сложно переоценить. В результате по этой теме написано много научных трудов [14,16,21,32] и разработано много способов поиска. Однако существенная часть имеющихся на данный момент подходов обладают определенными недостатками при индексации текста для поиска подстроки.

Современные СУБД поддерживают целый ряд способов поиска подстроки:

использование регулярных выражений [46,57], специальных функций и операторов и др. Примеры SQL-запросов согласно стандарту [61] выглядят следующим образом:

select * from texttable where textfld like '%substring%';

select * from texttable where substring(textfld from 5 for 9) like 'substring';

А, например, в диалекте языка SQL, который используется в свободно распространяемой СУБД PostgreSQL, имеется оператор «~» [65]. Пример SQL запроса на поиск подстроки с его использованием выглядит следующим образом:

select * from texttable where textfld ~ '.*substring.*';

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

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

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

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

Индексируемые документы рассматриваются, как последовательности целых чисел, полученных хешированием слов. При таком представлении документов их также можно отнести к объекту диссертационного исследования.

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

Примером таких индексов, ориентированных на слова естественного языка, а не символьные последовательности, может служить модуль tsearch2 для СУБД PostgreSQL [18]. Таким образом, разработанный индекс на основе R-деревьев, применительно к полнотекстовому поиску, может быть успешно применен в модуле tsearch2 к PostgreSQL, а также для решения широкого круга других прикладных задач.

1.2 Анализ способов индексации данных и выбор типа индекса для последовательностей элементов Целью данной диссертационной работы является ускорение поиска по фрагменту последовательностей элементов произвольного типа. В данном разделе рассмотрены основные способы индексации данных на предмет их применимости для достижения цели исследования. Результат данного анализа – выбор существующего индексного МД, наиболее подходящего для поиска последовательностей по фрагменту.

1.2.1 Индексы на основе битовых карт Индексы на основе битовых карт (bitmapped indexes) разработаны для ответов на запросы, которые затрагивают столбцы с ограниченным числом возможных значений, каждое из которых потенциально соответствует большому числу строк. Данный индекс, также как и другие типы индексов, хранит идентификаторы строк таблицы БД, которые рассматриваются строго как целые числа [26], поскольку определяются позициями битов в битовой карте. Операции получения идентификаторов строк по значениям атрибутов сводятся к использованию битовых операций с битовыми картами и выборке из получившейся битовой карты позиций ненулевых битов. Значения этих позиций считаются идентификаторами строк [26].

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

Таблица 1.2 – Пример индекса на основе битовых карт Битовая карта Идентификатор Значение строки «К» «С»

Красный 1 1 Синий 2 0 Синий 3 0 Зеленый 4 0 Красный 5 1 Операции получения идентификаторов строк по значениям атрибутов сводятся к использованию битовых операций с битовыми картами и выборке позиций ненулевых битов [26]. Достоинство очевидно – чтение из таблицы идет в физическом порядке расположения страниц, как и при полном сканировании, то есть каждая необходимая страница будет прочитана только один раз [23].

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

[22,26] Другим ограничением является то, что идентификатором строки данных должно быть строго натуральное число. В большинстве систем второе ограничение совершенно незаметно, поскольку идентификаторы и без того поддерживаются в автоинкрементном режиме. [26] Благодаря своей структуре индексы на основе битовых карт хорошо сжимаются, особенно если число возможных значений мало в сравнении с числом строк в таблице.

Недостаток индексов на основе битовых карт состоит в том, что их сложно обслуживать, когда данные в таблице изменяются. Это объясняется тем, что бито вые карты должны быть разжаты, сжаты вновь и, возможно, перестроены [26].

Кроме того, изменение ключевых столбцов приводит к конфликтам блокировок, поскольку любое изменение ключевых столбцов в таблице полностью ее блокирует [37,38].

Достоинства индексов на основе битовых карт 1. Индексы на основе битовых карт обычно создаются быстрее, чем многие другие виды индексов.

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

3. Индексы на основе битовых карт особенно эффективны, если комбинировать несколько таких индексов по разным столбцам.

4. Каждая страница данных читается только 1 раз независимо от сложности запроса и расположения данных в БД.

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

невозможно совмещать индексы, основанные на битовых картах, с кластерными индексами.

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

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

1.2.2 Hash-индексы Определение 1.2 Хеширование – преобразование данных произвольной длины в битовую строку фиксированной длины. Подобные преобразования выполняются хеш-функциями, а их результаты называют хеш-кодом.

Определение 1.3 Коллизия хеш-функции – существование двух различных входных значений данных с одинаковыми хеш-кодами.

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

При использовании хеширования в поисковых системах выбранная хеш функция должна удовлетворять следующим требованиям: должна быть быстрой и порождать хорошие хеш-коды для распределения элементов. Последнее требование минимизирует коллизии [25]. На случаи появления коллизий необходим определенный механизм их разрешения.

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

Хеш-индекс часто называется хеш-таблицей. Он представляет собой структуру, построенную с помощью выбранной хеш-функции для индексируемого набора значений. На рисунке 1.5 приведен пример хеш-таблицы для целых чисел, используя хеш-функцию, возвращающую остаток от деления на 8 (коллизии разрешаются с помощью связных списков) [25].

Рисунок 1.5 – Пример хеш-индекса для целых чисел Хеш-индекс также может быть составным. В этом случае хеш-функция применяется к совокупности значений атрибутов. [27] Применение хеш-индексов отличается от применения обычных индексов опять же в силу неуникальности хеширования. Они обязательно требуют применения пусть некоторого, но перебора записей в хеш-группе либо выборки с фильтрацией [27]. Этим данный тип индексов похож на индексы, основанные на R-деревьях и рассмотренные ниже.

Достоинства хеш-индексов 1. Быстрый поиск на точное равенство. По этому параметру хеш-индексы превосходят остальные типы индексов.

2. Небольшой размер индекса даже при индексации больших полей данных.

Недостатки и ограничения хеш-индексов 1. Эффективность поиска по индексу зависит от качества хеш-функции.

Необходимы методы разрешения коллизий. При часто возникающих коллизиях затраты на поиск достаточно высоки.

2. Хеш-индексы могут обрабатывать только простые сравнения равенства.

Нельзя выполнять сортировку по значению в виду нелинейности хеш-функции.

Следовательно, невозможно использовать в сравнениях операции больше/меньше.

1.2.3 Индексы на основе B-деревьев Механизм классических B-деревьев был предложен в 1970 г. Бэйером и МакКрейтом [28]. В современных СУБД, B-деревья являются, пожалуй, самым распространенным методом доступа к данным.

Определение 1.5 B-дерево порядка p представляет собой совокупность иерархически связанных страниц внешней памяти (каждый узел дерева страница), обладающая следующими свойствами [36]:

Каждая страница содержит не более 2p элементов (идентификаторов строк с ключом).

Каждая страница, кроме корневой, содержит не менее p элементов.

Если внутренняя (не листовая) вершина B-дерева содержит m ключей, то у нее имеется m+1 страниц-потомков.

Все листовые страницы находятся на одном уровне.

Последнее свойство означает, что B-деревья являются сбалансированными по высоте, т.е. высоты всех поддеревьев каждой из вершин дерева отличаются не более, чем на единицу [36]. Это обеспечивается тем, что сбалансированные деревья минимизируют свою высоту за счет равномерного распределения узлов в своей структуре. Основные операции в сбалансированных деревьях выполняются за время пропорциональное его высоте, т.е. за O(log(n)), где n – количество элементов, для которых построено дерево [28,34].

Как видно из определения, критерием управляемого роста B-дерева выступает ограничение на размер узла дерева от p до 2p.

Структура внутреннего узла B-дерева в типовом случае изображена рисунке 1.6.

N0 Key1 N1 Key2 N2 … Keym-1 N(m-1) Keym Nm Рисунок 1.6 – Структура внутреннего узла B-дерева При этом выдерживаются следующие свойства:

Key1 Key2... Keym;

В узле дерева Nm-1 находятся ключи K со значениями Keym-1 K Keym.

Следовательно, индексируемые с помощью данные B-деревьев упорядочены по значениям ключа [36]. Это дает преимущество по сравнению с индексами на основе битовых карт, которые всегда отсортированы по идентификаторам строк.

Пример B-дерева порядка 2 глубины 3 приведен на рисунке 1.7 [24].

Рисунок 1.7 – Классическое B-дерево порядка Поиск элемента в B-дереве Поиск в B-дереве производится очевидным образом. Предположим, что происходит поиск ключа K. В основную память считывается корневой узел B дерева. Предположим, что он содержит ключи Key1, Key2,..., Keym и ссылки на дочерние узлы N0, N1,..., Nm. В считанном узле последовательно (или с помощью какого-либо другого метода поиска в основной памяти) ищется ключ K. Если он обнаруживается, поиск завершен. Иначе возможны три ситуации: [36] 1. Если в считанном узле обнаруживается пара ключей Keyi и Keyi+1 такая, что Keyi K Keyi+1, то поиск продолжается в дочернем узле Ni.

2. Если обнаруживается, что K Keym, то поиск продолжается в дочернем узле Nm.

3. Если обнаруживается, что K Key1, то поиск продолжается в дочернем узле N0.

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

Если ключ не находится и в листовом узле, значит ключ K в B-дереве отсутствует [36].

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

Включение и исключение элемента из B-дерева Включение нового ключа K в B-дерево выполняется следующим образом.

По описанным выше правилам производится поиск ключа K. Поскольку этот ключ в дереве отсутствует, найти его не удастся, и поиск закончится в некоторой листовой странице A. Далее возможны два случая. Если A содержит менее 2p ключей, то ключ K просто помещается на свое место, определяемое порядком сортировки ключей в странице A. Если же страница A уже заполнена, то работает процедура расщепления. Заводится новая страница C. Ключи из страницы A (берутся 2p-1 ключей) + ключ K поровну распределяются между A и C, а средний ключ вместе со ссылкой на страницу C переносится в непосредственно родительскую страницу B. Конечно, страница B может оказаться переполненной, рекурсивно сработает процедура расщепления и т.д., вообще говоря, до корня дерева. Если расщепляется корень, то образуется новая корневая вершина, и высота дерева увеличивается на единицу. Одношаговое включение ключа с расщеплением переполненной страницы показано на рисунке 1.8. [36] Рисунок 1.8 – Добавление нового ключа в структуру B-дерева Процедура исключения ключа из классического B-дерева более сложна.

Приходится различать два случая: удаление ключа из листовой страницы и удаления ключа из внутренней страницы B-дерева. Описание процедуры приведено в [36].

При построении B-дерева для n элементов придется n раз выполнить алгоритм поиска со вставкой элемента, поэтому временная сложность построения B-дерева составляет O(n·log(n)).

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

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

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

Недостатки и ограничения индексов на основе B-деревьев 1. Применимы только для данных, которые можно отсортировать в определенном порядке.

2. Отсутствуют эффективные средства выборки данных (т.е. метода обхода дерева), упорядоченных по ключу, отличному от выбранного.

1.2.4 Индексы на основе B+-деревьев Схема организации классических B-деревьев проста и элегантна, но не очень хороша для практического использования [36]. Прежде всего, это связано с тем, что ключи с идентификаторами строк могут находиться как в листовых узлах, так и во внутренних узлах. Это приводит к непредсказуемости числа обменов с внешней памятью для поиска произвольного ключа. Кроме того, при пакетной выборке для обработки запросов интервала данных необходимо многократно спускаться по дереву от корня к листу, чтобы выбрать весь диапазон.

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

Из сказанного следует, что структура внутренних и листовых узлов у B+ дерева различна. Внутренние узлы устроены так же, как у B-дерева (см. рисунок 1.6), но в них хранятся только ключи (без идентификаторов строк) и ссылки на дочерние узлы [36]. В листовых же узлах хранятся все ключи, содержащиеся в дереве, вместе с идентификаторами строк (рисунок 1.9).

Key1 R1 Key2 R2 … Keym Rm Рисунок 1.9 – Структура листового узла B+-дерева Листовые узлы B+-дерева обладают следующими свойствами:

Key1 Key2... Keym;

Ri – идентификатор строки таблицы, содержащей значение Keyi.

На рисунке 1.10 изображено B+-дерево порядка 2 и глубины 3.

Рисунок 1.10 – B+-дерево порядка Поиск ключа выполняется аналогично поиску в классическом B-дереве, но всегда доходит до листового узла, в результате время поиска по индексу становится предсказуемым. При этом у ссылок на дочерние узлы смысл немного другой по сравнению с классическими Левый указатель B-деревьями.

(относительно ключа) ведет к ключам, которые строго меньше заданного значения, а правый – к ключам, которые больше или равны (GE) заданного [24].

Т.к. поиск всегда доходит до листа дерева, то его асимптотическая сложность составляет (log(n)), где n – количество элементов, для которых построено дерево.

Операции включения и исключения ключа выполняются аналогично классическим B-деревьям.

Таким образом, B+-деревья во многом превосходят B-деревья, уступают же B-деревьям в том, что требуют несколько больше памяти для представления (ключи-разделители и ключи в листьях) [48].

Важной полезной оптимизацией B+-деревьев является связывание листовых страниц в одно- или двунаправленный список. Это позволяет просматривать списки записей для заданного диапазона значений ключей с лишь одним прохождением дерева от корня к листу [36].

Однако дополнительную сложность вызывает возможность организации индексов по нескольким столбцам таблицы (так называемых «составных»

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

Имеется ряд технических приемов сжатия индексов с составными ключами, улучшающих использование внешней памяти, но, естественно, замедляющих выполнение операций включения и исключения. [36] Достоинства индексов на основе B+-деревьев 1. Все достоинства и преимущества классических B-деревьев.

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

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

4. Удаление всегда происходит из листового узла, что облегчает его реализацию.

Недостатки и ограничения индексов на основе B+-деревьев 1. Недостатки и ограничения, свойственные классическим B-деревьям.

2. Хранение избыточной информации в узлах дерева. Особенно при организации составных индексов.


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

В основе суффиксных поисковых структур лежит такая структура, как бор (рисунок 1.11).

Рисунок 1.11 – Бор, построенный для строки banana$ Определение 1.6 Бор (trie, луч, нагруженное дерево [31]) представляет собой дерево, хранящее все суффиксы строки. Каждый путь в дереве представляет собой некоторый суффикс, длина пути в точности равна длине суффикса, каждая вершина хранит символ [14].

Множество возможных значений каждого символа называется алфавитом и обозначается.

Как видно из рисунка 1.11, индексируемая строка «banana» дополнена терминальным символом вне алфавита ($). Такой прием используется, чтобы гарантировать взаимно однозначное соответствие между листьями бора и суффиксами строки [16].

Хотя время поиска подстроки является линейным, для построения бора требуется O(n2) операций, а для хранения – O(n2) памяти, что сильно ограничивает его практическое использование [14]. Для устранения недостатков бора обычно используется его сжатие. Для этого информация из узлов переносится на дуги, узлы степени 2 (за исключением корня) удаляются из дерева, а соответствующие дуги объединяются. Таким образом, каждая дуга в дереве соответствует некоторой подстроке индексируемого текста. Для такого сжатого бора используется термин суффиксное дерево (рисунок 1.12).

Рисунок 1.12 – Суффиксное дерево для строки banana$ Для суффиксных деревьев общие требования к памяти, по сравнению с бором, снижаются до O(n) [63], что расширяет возможности практического применения данной поисковой структуры.

При построении индекса для столбца таблицы БД используются обобщенные суффиксные деревья, построенные над множеством исходных строк и представляющие суффиксы каждой исходной строки [16].

Суффиксные деревья используются для решения большого круга поисковых задач, а для их построения используются разнообразные алгоритмы (МакКрейта, Укконена и др.). Для данной работы интересен только поиск по подстроке. Чтобы узнать, принадлежит ли строка v множеству S, нужно, начиная от корня суффиксного дерева, перемещаться по нему в соответствии с символами в строке v. Если в результате мы оказались в листе и использовали все символы из v, то v S, и не принадлежит в противном случае [16].

В диссертационной работе Андрианова И. А. [16] (одна из последних работ, касающихся алгоритмов поиска и построения суффиксных деревьев) удалось добиться следующих ассимптотических характеристик. Временная сложность построения обобщенных суффиксных деревьев составляет O(n·log(||)), поиска подстроки – O(m·log(||)), где n – длина текста, m – длина подстроки, || - размер исходного алфавита. Требования к памяти неизменны – O(n).

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

суффиксный массив равен {6,4,2,1,5,3} (лексикографически упорядоченные суффиксы: «a», «ana», «anana», «banana», «na», «nana»). Элемент массива с индексом i выражает индекс суффикса, который будет i-ым в лексикографическом порядке среди всех суффиксов строки [14].

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

Область же задач, решаемых при помощи суффиксных деревьев, больше чем у суффиксных массивов [14].

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

В работе Айткулова П. Г. удалось добиться следующих ассимптотических характеристик для суффиксных массивов. Временная сложность построения есть O(n·log2(n)), поиска подстроки – O(m + log(n)), где n – длина текста, m – длина подстроки. Требования к памяти неизменны – O(n).

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

2. Высокая эффективность поиска строк (последовательностей символов) с логарифмической асимптотикой.

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

2. Малое изменение (добавление, удаление или изменение одной записи) приводит к серьезной перестройке индекса [14], что ограничивает применение для динамических данных.

1.2.6 Индексы на основе R-деревьев Механизм классических R-деревьев был предложен Антонином Гуттманом в 1984 году в работе [58] как инструмент поиска часто изменяемых (динамических) пространственных данных. При этом R-деревья поддерживают как двумерные, так и трехмерные геометрические данные. Примеры типичных поисковых задач, решаемых с помощью R-деревьев:

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

По своей структуре R-деревья похожи на B+-деревья и также являются сбалансированными по высоте структурами с разной организацией внутренних и листовых страниц [43]. Подобно B-деревьям, в узлах R-дерева порядка p содержится не более 2p и не менее p элементов.

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

Как и у B-деревьев узлы R-дерева соответствуют страницам внешней памяти [43]. На рисунке 1.13 приведена структура внутренней страницы.

Прямоуг. 1 Прямоуг. 2 Прямоуг. m … Ссылка на Ссылка на Ссылка на поддерево 1 поддерево 2 поддерево m Рисунок 1.13 – Структура внутренней страницы R-дерева Пример индексации пространственных данных с помощью R-дерева приведен на рисунке 1.14.

Рисунок 1.14 – Пример R-дерева для индексации пространственных данных В листовых страницах вместо ссылок на поддеревья хранятся идентификаторы строк.

Индексация пространственных данных с помощью R-деревьев нашла широкое применение в пространственных базах данных и геоинформационных системах (ГИС). До сих пор R-деревья являются стандартом де-факто для индексации пространственных данных в промышленных СУБД.

Организация структуры R-дерева и поиск в нем По мере движения от корня к листу R-дерева выполнятся условие иерархичности узлов, т.е. охватывающий прямоугольник родительского узла включает в себя прямоугольники всех своих потомков [58]. Благодаря этому, при движении по дереву от корня к листу набор рассматриваемых объектов сужается с каждым шагом.

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

Основное отличие от B+-деревьев заключается в том, что возможен вариант, когда более одного поддерева после прохождения узла может участвовать в дальнейшем поиске. Следовательно, любой поисковый запрос выполняется за один «спуск» от корня к листу дерева, пока не будут найдены все искомые объекты.

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

Определение 1.7 Построенная для заданного набора объектов структура R-дерева называется оптимальной, если сумма площадей попарных перекрытий входов во всех нелистовых узлах дерева является минимальной среди всех возможных структур R-деревьев [43]:

S ( Ri Ri ), min R деревьяi j Для минимизации степени пересечения прямоугольников узлов требуется, чтобы наиболее близкие друг к другу объекты располагались «рядом», т.е. в одном поддереве. Алгоритмы разбиения множества объектов на минимально пересекающиеся группы приводятся в [43].

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


Включение и исключение элемента из R-дерева Алгоритмы вставки и удаления элементов из R-дерева похожи на аналогичные алгоритмы B-деревьев и описаны в [58]. Временная сложность построения R-дерева для n объектов составляет O(n·log(n)).

Потенциал для индексирования других типов данных В отличие от других типов индексов, R-деревья накладывают минимальные требования к типу индексируемых данных. Структура R-дерева такова, что ее можно использовать не только для пространственных данных, для которых она разработана, не изменяя при этом алгоритмов и принципов работы с индексом. По сути, чтобы использовать R-дерево для индексации какого-либо другого типа данных нужно:

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

2. Обеспечить иерархичность этой информации в узлах дерева при его построении для эффективного поиска.

3. Разработать алгоритм принятия решения о необходимости поиска в дочерних поддеревьях, используя сохраненную в узлах дерева информацию.

Данный потенциал R-деревьев успешно используется для построения обобщенных методов доступа к произвольным данным. Например, обобщенное поисковое дерево GIST в свободно распространяемой СУБД PostgreSQL [20,65] и т.п.

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

2. Минимальные требования к типу индексируемых данных, что позволяет использовать R-деревья для реализации обобщенных методов доступа.

Недостатки и ограничения индексов на основе R-деревьев 1. Эффективность поиска зависит от степени пересечения сигнатур, т.е.

фактически от реализации алгоритмов построения.

2. Не гарантируют хорошей асимптотики скорости поиска в наихудшем случае.

1.2.7 Индексы на основе RD-деревьев Как было сказано выше, индексы на основе R-деревьев накладывают минимальные требования к типу индексируемых данных. В результате появилось множество разновидностей R-деревьев и обобщенных индексов, построенных на их основе [20,50,56,60,62].

Для данной работы интересен только поиск последовательностей по фрагменту. Для поиска наборов элементов существует специальная разновидность R-деревьев – RD-деревья. Данная разновидность R-деревьев предложена Джозефом Хеллерстейном в 1994 году в работе [60]. Аббревиатура «RD» расшифровывается как «Russian Doll» (матршка), подчеркивая тем самым иерархичность дочерних и родительских узлов дерева.

Перед тем как рассматривать структуру RD-дерева обратимся к понятию блюмовского фильтра.

Понятие блюмовского фильтра Блюмовские фильтры (bloom filters) были разработаны Бартоном Ховардом Блюмом в 1970 году в работе [51] и являются эффективной по размеру вероятностной структурой данных, используемой для определения, принадлежит ли элемент набору или нет. Основные свойства блюмовских фильтров [49]:

Количество памяти, необходимое для хранения фильтра, мало по сравнению с размером данных, принадлежащих проверяемому набору;

Время проверки того, принадлежит ли элемент заданному набору, не зависит от количества элементов в наборе;

Ложноотрицательные результаты проверки невозможны;

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

Таким образом, проверка элемента на принадлежность набору возвращает либо «элемент принадлежит набору, но возможны ошибки», либо «элемент точно не принадлежит набору». Чем больше элементов в наборе, тем больше вероятность ложноположительного ответа.

Блюмовские фильтры представляют собой битовый массив (b1, b2, …, bm), который изначально содержит все нули. Для понимания того, каким образом работают блюмовские фильтры, рассмотрим основные правила установки и проверки битов [49]. Для этой цели используются k независимых хеш-функций (h1, h2, …, hk), каждая из которых возвращает значение от 1 до m (длины битового массива). Для того чтобы сохранить заданный элемент в битовом массиве, для него применяется каждая хеш-функция, и на основе возвращаемых значений (r1, r2, …, rk) устанавливаются в 1 биты со смещением r. Таким образом, будет установлено k бит в битовом массиве или меньше, если несколько хеш-функций вернут одинаковые значения. На рисунке 1.15 приведен пример сохранения элемента в битовом массиве (элемент «e», m = 16, k = 4) [49].

Рисунок 1.15 – Пример сохранения элемента в блюмовском фильтре Для проверки, находится ли элемент в сохраненном битовом массиве, используется похожий алгоритм. Отличие лишь в том, что вместо установки k бит в массиве выполняется проверка этих k бит на предмет наличия 0 хотя бы в одном из них [49]. Если это так, то проверяемый элемент точно не сохранен в битовом массиве, а, следовательно, отсутствует в отображаемом наборе элементов.

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

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

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

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

Проверка включения сигнатуры A в сигнатуру Б заключается в проверке того, что в Б установлены все биты, установленные в А. Данная проверка используется при обходе узлов дерева во время поиска. Решение о включении дочернего поддерева в поиск, принимается на основании включения сигнатуры искомого объекта в сигнатуру рассматриваемого поддерева.

Числовые Хеш последовательности Бит Число 1 1) 225,225,227,164, 2 2) 172,160,172,160 4 5 3) 162,32,171,165, 7 4) 225,162,165,226 8 10 0110110010000000 11 13 Ссылка на поддерево 1 Ссылка на поддерево 14 Сигнатура 0010110010000000 0110000000000000 0000000010110110 Ссылка на 225,225,227,164,160 Ссылка на 162,32,171,165,225 Ссылка на 225,162,165, Ссылка на 172,160,172, Рисунок 1.16 – Пример RD-дерева для индексации числовых последовательностей Хеш-функция, используемая при построении блюмовских фильтров, содержащихся в сигнатурах RD-дерева, не является идеальной (как и большинство хеш-функций). Коллизии хеширования приводят к тому, что для различных наборов элементов могут быть одинаковые сигнатуры. Именно этот факт приводит к ложноположительному результату проверки включения сигнатур друг в друга, используя блюмовские фильтры узлов при поиске. Следовательно, поиск с использованием RD-дерева может дать определенное количество неверных результатов, так называемых «ложных попаданий», т.е. лишних спусков до листового узла. В этом состоит основная проблема RD-деревьев (как и хеш индексов).

Достоинства индексов на основе RD-деревьев 1. Все достоинства и преимущества классических R-деревьев.

2. Компактность. Сигнатуры, основанные на блюмовских фильтрах, хранимые в узлах дерева, существенно компактнее индексируемых данных.

Недостатки и ограничения индексов на основе RD-деревьев 1. Недостатки и ограничения, свойственные классическим R-деревьям.

2. Неточность индекса. Возможны «ложные попадания» при поиске.

1.2.8 Выбор структуры индекса для индексации последовательностей Для выбора индексного МД для диссертационного исследования, сформулируем необходимые критерии, основываясь на цели диссертации, объекте исследования и сформулированных в начале главы практических задачах, решаемых в рамках исследования:

1. Применимость для индексации последовательностей элементов с поддержкой поиска по фрагменту.

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

2. Минимальные требования к типу элементов последовательностей.

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

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

4. Эффективные алгоритмы построения и обновления индекса.

На статичность данных не должно быть ограничений.

5. Компактность.

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

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

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

Индексы на основе B*-деревьев имеют множество достоинств. Однако для поиска последовательностей элементов по фрагменту они плохо применимы.

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

Суффиксные структуры данных предназначены главным образом для поиска текста по подстроке, что является частным случаем поиска последовательностей по фрагменту. Однако их основной проблемой является их размер. Хотя асимптотическая оценка – O(n), фактический размер индекса многократно превышает размер индексируемых данных. Так в диссертационной работе Андрианова И.А. объм создаваемого индекса на основе суффиксных деревьев в зависимости от входных данных составил от 10 до 15 байт на один входной символ [16]. В работе же Айткулова П.Г. при использовании суффиксных массивов это значение составило и вовсе не менее 40 [14]. Поэтому данный тип индексов целесообразно использовать только для коллекций небольшого размера (до нескольких гигабайт). Другим недостатком суффиксных поисковых структур является то, что даже незначительные изменения данных приводят к серьзной перестройке индекса [14]. Поэтому такие индексы не подходят для динамических данных. Кроме того, суффиксные массивы используют сортировку суффиксов индексируемых строк в лексикографическом порядке. Для последовательностей элементов это требование накладывает ограничение на тип элементов (аналогично B-деревьям). По этим причинам суффиксные структуры неприменимы для достижения цели данного исследования.

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

Модификация же R-деревьев – RD-деревья – разработана специально для индексации наборов элементов. При этом поддерживаются различные типы поиска, в том числе поиск по фрагменту. К типу элементов набора предъявляется минимум требований: фактически достаточно только отношения равенства, что допустимо. Алгоритмы работы со структурой RD-дерева не зависят от типа элементов в индексируемых наборах, поэтому одинаково эффективны для наборов элементов любого типа. RD-деревья обладают высокой скоростью поиска на реальных данных, а алгоритмы построения и обновления делают возможным их применение для динамических данных. Индексы данного типа очень компактные, благодаря использованию блюмовских фильтров в узлах дерева.

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

Однако RD-деревья имеют ряд недостатков, которые ограничивают их использование для последовательностей элементов:

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

Технически неточность поиска приводит к тому, что найденные по индексу объекты необходимо сравнивать с оригиналом, прочитанным из БД. Для этого требуются дополнительные чтения страниц БД, что на существенных объемах данных значительно замедляет работу [17].

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

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

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

1.3 Постановка задач дальнейшего исследования Существует достаточно большое количество работ, посвященных алгоритмам построения и использования R-деревьев и их разновидностей для пространственных данных. С использованием R-деревьев успешно решены различные задачи пространственного поиска. Однако достаточно небольшое количество работ посвящено такой разновидности R-деревьев, как RD-деревья, предназначенных для индексации наборов элементов.

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

Если для R-деревьев данная проблема хорошо изучена и разработаны эффективные алгоритмы построения индекса [43], то для RD-деревьев взаимное пересечение сигнатур изучено недостаточно и требует необходимости в исследовании.

Также слабоизученным остается вопрос, касающийся неточности поиска с помощью RD-деревьев в результате коллизий хеширования, используемого при построении узлов дерева. Для минимизации размера индекса сигнатуры его узлов представляют собой битовые массивы фиксированного размера (блюмовские фильтры [49,51]). Очевидно, что данные битовые массивы неоднозначно описывают индексируемые данные и для разных объектов могут получиться одинаковые сигнатуры. Остается открытым вопрос: «Каким образом можно снизить вероятность коллизий при хешировании?».

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

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

элементов в числа, и хранить в сигнатурах последовательности чисел.

2. При вставке последовательности в поддерево сигнатура последнего расширяется по следующим правилам (сигнатуры делятся на части спецсимволом, например, «$»):

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

2.2. Если вставляемая последовательность начинается с элементов, расположенных слева от какого либо спецсимвола «$» сигнатуры поддерева, а заканчивается элементами, расположенными справа от этого же спецсимвола «$», то спецсимвол удаляется, а последовательность вставляется на его место, объединяя левую и правую части сигнатуры. Иначе применяется следующее правило.

2.3. Если вставляемая последовательность начинается с элементов, которыми заканчивается какая-либо часть сигнатуры, то последовательность добавляется в конец данной части без удаления спецсимвола «$». Иначе применяется следующее правило.

2.4. Если вставляемая последовательность заканчивается элементами, с которых начинается какая-либо часть сигнатуры, то последовательность добавляется в начало данной части без удаления спецсимвола «$». Иначе применяется следующее правило.

2.5. Вставляемая последовательность дописывается в сигнатуру поддерева, например, с левого края через спецсимвол «$».

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

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

Индексируемые мамалинастеж$лес строки Ссылка на поддерево 1) мама 2) настеж 3) малина 4) лес мама$настеж малина$лес Ссылка на поддерево 1 Ссылка на поддерево Сигнатура мама настеж малина лес Ссылка на «мама» Ссылка на «малина» Ссылка на «лес»

Ссылка на «настеж»

Рисунок 1.17 – Пример RD-дерева, построенного по предложенному алгоритму Достоинства и недостатки предложенного алгоритма построения узлов RD дерева сведены в таблицу 1.3.

Таблица 1.3 – Достоинства и недостатки предложенного алгоритма Достоинства Недостатки 1. Много меньше «ложных попаданий» 1. Расходы памяти увеличиваются с при поиске, но на асимптотику это не O(n) до поскольку в O(n·log(n)), влияет, по-прежнему в наихудшем случае, когда все O(n) наихудшем случае. последовательности разные и 2. Простота реализации. непересекающиеся, каждая из них будет присутствовать на всех уровнях дерева.

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

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

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

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

Выводы по главе 1. Произведен анализ существующих способов индексации данных.

Изучены достоинства и недостатки каждого типа индексов на предмет максимального соответствия цели диссертационного исследования и применимости к объекту исследования.

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

Основные причины выбора данного типа индексов:

a. Применимость для индексации последовательностей элементов произвольного типа с поддержкой поиска по фрагменту, b. Потенциальная возможность ускорения поиска, c. Отсутствие ограничений на статичность индексируемых данных, d. Компактность.

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

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



Pages:   || 2 | 3 |
 





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

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