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

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

Коротков Александр Евгеньевич

Методы, алгоритмы и программные средства повышения скорости поиска в базах данных

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Автор: _____

6 ДЕК 2012

Москва - 2012

005056335

005056335

Работа выполнена в Национальном исследовательском ядерном университете «МИФИ».

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

Кудрявцев Константин Яковлевич

Официальные оппоненты: доктор технических наук, профессор,

профессор кафедры «САПР» Московского государственного горного университета Петров Андрей Евгеньевич

кандидат технических наук, доцент, доцент кафедры математического обеспечения вычислительных систем Московского государственного технического университа радиотехни электроники и автоматики Андрианова Елена Гельевна

Ведущая организация: Федеральное государственное унитар

предприятие «Московский ордена Трудового Красного Знамени научно-исследовательский радиотехнический институт»

Защита состоится « _ 2012 г. в Ж часов на заседании

диссертационного совета Д 212.130.03 при Национальном исследовательском ядерном университете «МИФИ», расположенном по адресу: 115409, г. Москва, Каширское шоссе, 31.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан «ЛЗ-»

2012 г.

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

Ученый секретарь диссертационного совета

ОУ/^^^уЩ^ Леонова Н. М.

Общая характеристика работы

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

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

Одной из наиболее широко применяемых структур данных является В-дерево. В-дерево обеспечивает высокую скорость выполнения запросов, связанных с типами данных и поисковыми предикатами, заданными SQL стандартом. Однако, для многих современных приложений необходима работа с типами данных и поисковыми предикатами, не заданными стандартом SQL. Примером таких типов данных могут служить геометрические типы данных (точки, многоугольники, кривые и т.д.), которые широко применяются в геоинформационных системах (ГИС). В ГИС также применяются не заданные SQL стандартом поисковые предикаты, такие как предикат пересечения геометрических объектов, предикат вхождения одного геометрического объекта в другой. Хотя для ГИС существуют различные стандарты, такие как Open GIS, структуры данных используемые СУБД для эффективной обработки поисковых запросов отличаются.

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

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

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

• Высокая вычислительная сложность расстояния Левенштейна при большом объеме исходных строк.

• Ограничения методов индексации для поиска по расстоянию Левенштейна в строковых массивах.

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

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

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

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

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

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

3. Разработать индексную структуру на основе ИС-дерева и к-грамм для поиска в наборах строк но расстоянию Левенштейна.

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

Объектами исследований диссертационной работы являются базы данных, содержащие наборы пространственных данных и наборы строк.

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

Методами исследования исследования диссертационной работы являются методы теории множеств, теории алгоритмов, линейной алгебры, математического анализа.

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

1. Разработан новый алгоритм разделения узла И-дерева для одномерного случая, основанный на использовании нового понятия «угловой разделяющей пары».

2. Разработано применение нового алгоритма разделения узла для Ы-дерева к многомерному случаю.

3. Разработан новый алгоритм вычисления расстояния Левенштейна с пороговым значением и математически доказана его корректность.

4. Разработана структура данных на основе 1Ш-дерева и к-грамм для поиска в наборах строк по расстоянию Левенштейна.

5. Разработан алгоритм фильтрации сигнатур для структуры данных на основе РШ-дерева и к-грамм, математически доказана его корректность.

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

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

2. Новый алгоритм вычисления расстояния Левенштейна с пороговым значением и предложенное применение 1Ш-дерева к набору к-грамм индексируемой строки позволяют с большей скоростью решать задачи нечеткого поиска в наборах строк, что представляет практическую ценность при очистке данных, смягчении поисковых запросов и проверке правописания.

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

1. новый алгоритм разделения узла 11-дерева для одномерного случая, основанный на использовании нового понятия «угловой разделяющей пары»;

2. применение нового алгоритма разделения узла для R-дерева к многомерному случаю;

3. новый алгоритм вычисления расстояния Левенштейна с пороговым значением;

4. структура данных на основе RD-дерева и k-грамм для поиска в наборах строк по расстоянию Левенштейна;

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

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

• Spring/Summer Young Researchers' Colloquium on Software Engineering (SYRCoSE) [1-3];

• IADIS International Conference Applied Computing [4];

• Международный научно-технический семинар в городе Алушта [5];

• Научная сессия МИФИ [6].

Реализация результатов диссертации заключается в следующем.

1. Программная реализация предложенного алгоритма разделения узла R-дерева была включена в исходных код наиболее развитой СУБД с открытым исходным кодом PostgreSQL.

2. Программная реализация предложенного алгоритма вычисления расстояния Левенштейна с пороговым значением была включена в исходных код наиболее развитой СУБД с открытым исходным кодом PostgreSQL.

3. Разработанный алгоритм разделения узла для R-дерева был применен в Государственном астрономическом институте им. П. К. Штернберга для поиска астрономических объектов.

4. Разработанный алгоритм разделения узла для R-дерева, а также методы нечеткого поиска текста были применены в ЗАО «Геноаналитика» для построения генетической карты и поиске формулировок заболеваний.

Публикации

Всего по теме диссертации опубликовано 12 печатных работ [1-12] в том числе 5 статьи в журналах, рекомендованных ВАК РФ для публикации основных результатов работы [7—11]. Личный вклад автора

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

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

наименований и одного приложения. Основная работа диссертации содержит 132 страницы текста, включая 47 рисунков и 7 таблиц.

Основное содержание работы

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

В первой главе проведен анализ основных алгоритмов и структур данных, служащих для поиска пространственных данных, а также для нечеткого поиска в наборах строк. Рассмотрены такие структуры для хранения пространственных данных, как Спс1-файл, <Зиас1-дерево, к-с!-дсрево, 11-дерево, а также их разновидности. 11-дерево и его разновидности наиболее распространенны для индексирования пространственных и других видов многомерных данных в силу следующих причин.

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

2. 11-дерево поддерживает различные виды запросов, такие как топологические запросы, запросы на поиск по направлению, запросы на поиск ближайших соседей.

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

4. 11-дерево не накладывает дополнительных ограничений на индексируемые данные, таких как нахождение всех пространственных объектов внутри заранее заданных границ.

5. II-дерево может индексировать объекты в пространстве с произвольным числом измерений.

6. И,-дерево обладает простой структурой, похожей на В-дерево, что позволило разработчиками легко встроить эту структуру данных в СУБД.

Было показано, что основным недостатком 11-дерева является возможность пересечения минимальных охватывающих прямоугольников (МОП) его узлов. Степень пересечения МОП узлов зависит от исходных данных при построении дерева, а также от самой процедуры построения 11-дерева, к которой на настоящий момент существует множество модификаций. Высокая степень пересечения МОП узлов, в конечном

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

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

• вставка произвольного символа в произвольную позицию строки;

• замена произвольного символа строки другим произвольным символом;

• удаление произвольного символа строки.

Расстояние Левенштейна между строками а и Ь будем обозначать как 1еьепзМет(а, Ь). Для расчета расстояния Левенштейна между строками может быть использован алгоритм выравнивания двух последовательностей. Этот алгоритм основан на заполнении матрицы Б размерами п + 1 на тп + 1 (где п и ш - длины строк а и Ь соответственно).

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

[ 1еуепзЫет(а,Ь),1еуепзМет(а,Ь) < к _ 1еуепзЫет_ЬкгезкоЫ{а, Ь,к) = ■( 1тепзМе;п(а Ь) > к

I гъ ч Л-) ЬС с/с-/0011ьсиьуи/) и} ^ П/

= ппп{1еьепзЫет(а, 6), к + 1}

(!)

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

не обязательно. Эта задача может быть представлена как нахождение значения функции levenshtein_threshold(a, b, к) (формула 1) которая равна расстоянию Левенштейна между строками а и Ь, если оно не превосходит к, и равна к + 1 в противном случае. Задача нахождения значения функции levenshtein _threshold(a, b, к) может быть решена с временной сложностью 0(min(n, т) ■ к), за счет заполнения только части матрицы D вокруг её диагонали. Однако для многих задач, существующие алгоритмы расчета расстояния Левенштейна с пороговым значением всё ещё не достаточно быстры. Поэтому актуальной задачей является разработка более быстрого алгоритма расчета расстояния Левенштейна с пороговым значением.

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

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

Во второй главе описан новый алгоритм разделения узла R-дерева, разработанный в ходе данной диссертационной работы:

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

В одномерном алгоритме разделения входные элементы содержат множество I интервалов хг: I = {ж,}. Интервал Ж; определяется своими верхней и нижней границами: Х{ = (1г,Щ). Общая нижняя граница это I = min{li}, а общая верхняя граница - и = тах{щ}. Назовем пару <а, Ь> разделяющей парой, если любой интервал из I содержится либо в интервале (1,а), либо в интервале (Ь, и): Vx(x g I => (х С (I, а)) V (х С (Ь,и)). Будем называть разделяющую пару <а, Ь> угловой разделяющей парой, если (а е (М) А (6 е {¿¿}) A ((Vf(i < а =Ф- Зх(х € I => (х % (l,t)) А (х 2 (6,«)))) V (Vt(t >b=> Зх(х €l=>(xg(l, a)) A (x<Z (t, u))))).

Ha первом шаге алгоритма разделения узла одномерного R-дерева, осуществляется перечисление всех угловых разделяющих пар. Это делается на основе использования двух массивов: первый содержит входные элементы,

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

Работа данного алгоритма проиллюстрирована на рисунке 1 для набора интервалов [0, 5], [1, 7], [3,6], [3,8]. Вначале находится первая угловая разделяющая пара <5, 0> (состояние 1 на рисунке 1). Далее осуществляется поиск следующего значения в2.1 и соответствующего з1.и. Этот шаг отображен как состояние 2 на рисунке 1, откуда видно что граница й2.1 увеличилась, но при этом не потребовалось увеличение s1.il. Далее осуществляется переход к следующему значению э2 Л. таким образом находится угловая разделяющая пара <5, 1> (состояние 3 на рисунке 1). После этого осуществляется поиск следующего значения в2.1 и соответствующего Далее находится промежуточная угловая

разделяющая пара <6, 1> (состояние 4 на рисунке 1). После этого осуществляется переход к следующему значению з2.1, таким образом находится угловая разделяющая пара <7, 3> (состояние 5 на рисунке 1). Далее снова в осуществляется поиск следующего значения й2.1, при это оказывается что текущее значение уже наибольшее (состояние 6 на рисунке 1). И в завершение осуществляется переход к последней найденной угловой разделяющей паре <8, 3> (состояние 7 на рисунке 1).

1 2) | 1 I 3)ЕЩЕЩ 4)|

g

2

3

2) : 1

1 : :. 2

!

211 Ь—ШВ

3

i 2

Ьгч

S2.I

s1 .и <5, 0>

s2.ll next s2.l

s1 .и

s2.l sl.u <5, 1>

s2.l i sl.u: next s2.l nextsl.u <6, 1>

5) Г

1

2

4

6) -

s2.i sl.u <7, 3>

1

! 2

s2 isa^

4, .1 sl.u Si

7) L

! 1

2

s2.l sl.u <8, 3>

next sl.u

Рис. 1. Иллюстрация работы алгоритма перечисления угловых разделяющих пар

Среди всех перечисленных угловых разделяющих пар выбирается наилучшая по следующим критериям (перечислены в порядке убывания приоритета).

• Минимальное число элементов в группе больше или равно т.

• Степерь пересечения интервалов групп - наименьшая.

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

• Распределение элементов по группам наиболее близко к равномерному.

Было разработано применение разработанного алгоритма к многомерному случаю. На первом шаге перечисляются все угловые разделяющие пары вдоль всех осей и выбирается угловая разделяющая пара и соответствующая ось, для которых степень пересечений охватывающих интервалов - наименьшая. Если два или более разделения имеют одинаковую степень пересечения, то выбирается та ось, длина охватывающего интервала вдоль которой больше. Это стратегия делает МОП групп наиболее близкими к квадратам, что помогает при поиске.

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

• новый алгоритм вычисления расстояния Левенштейна с пороговым значением;

• индексную структуру на основе РЮ-дерева и к-грамм для поиска в наборах строк по расстоянию Левенштейна.

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

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

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

Пример исходной матрицы (£>) приведен на рисунке 2. Суммы исходной и дополнительной матриц (£)") приведен на рисунке 3.

Введем матрицу Б* размерностью п на т, такую что Д? = тт-Ш-',, к+ 1}, где к - пороговое значение. Таким образом, будет отражать

расстояние Левенштейна с пороговым значением.

к а Р н а в а л

1 0 1 2 3 4 5 6 7

к 2 1 0 1 2 3 4 5 6

а 3 2 1 0 1 2 3 4 5

Р 4 3 2 1 0 1 2 3 4

а 5 4 3 2 1 0 1 2 3

в 6 5 4 3 2 1 0 1 2

а 7 6 5 4 3 2 1 0 1

н 8 7 6 5 4 3 2 1 0

Рис. 2. Матрица В строк «караван» и «карнавал».

к а Р н а в а л

1 1 3 5 7 9 11 13 15

к 3 1 1 3 5 7 9 11 13

а 5 3 1 1 3 5 7 9 11

Р 7 5 3 1 1 3 5 7 9

а 9 7 5 3 2 1 3 5 7

в 11 9 7 5 4 3 1 3 5

а 13 11 9 7 6 4 3 1 3

н 15 13 11 9 7 6 5 3 2

Рис. 3. Матрица В" для строк «караван» и «карнавал»

£>£„ = тт{С(<5гл) ■ с<1, + С?(-<5у) -<Н,к + 1}

Що = тт{Д*_1>0 + Н{-6ц - 1 )■(<* + су), к + 1}, г > 1

= тт!^-.! + Н{5ц + 1) • (й + а), к+1}Л>1

= тт <

' + °Г ■ <1((Ц, Ьг)

+ - 1) ■ (<* + гу)

+ - 1) ■ (а + са)

А; + 1

,г>и>1

В диссертационной работе показано, что для матрицы £>* будут выполняться свойства 2, 3, 4 и 5.

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

значения не превосходят к. Заполнение г + 1 строки начинается с ячейки ¡¿_ 1 и заканчивается, когда одновременно текущий номер ячейки в строке больше щ + 1 и значение ячейки больше к (или будет достигнут конец строки). Пример матрицы Е на момент завершения работы алгоритма показан на рисунке 4.

к а Р н а в а л

1 1 3

к 3 1 1 3

а 3 1 1 3

Р 3 1 1 3

а 3 2 1 3

в 3 3 1 3

а 3 1 3

н 3 2

Рис. 4. Матрица Е для строк «караван» и «карнавал»

Также в третьей главе описана разработанная индексная структура на основе ШЭ-дерева и к-грамм для поиска в наборах строк по расстоянию Левенштейна. Пример такого ШЭ-дерева приведен на рисунке 5. В его листовых узлах вместо наборов к-грамм хранятся исходные строки. Во внутренних узлах хранятся сигнатуры. Сигнатура представляет собой битовый вектор, число бит в котором меньше, чем мощность множества возможных к-грамм. Это означает, что одному биту может соответствовать больше, чем одна к-грамма. Бит при этом устанавливается, если присутствует хотя бы одна к-грамма из соответствующих данному биту. Таким образом, если некоторый бит сигнатуры не установлен то это означает, что во всем поддереве нет ни одной из соответствующих этому биту к-грамм. Таким образом, сигнатура представляет собой фильтр Блума, т.е. компактное представление множества, допускающее ложноположительное срабатывание, но не допускающее ложноотрицательное. Для отображения к-грамм на биты сигнатуры использовалась хэш-функция сгс32. В таком представлении, ШЭ-дерево, за исключением листьев, становится очень похожим на Б-дерево. Пример такого дерева приведен на рисунке 5.

Для поиска по предложенному RD-дереву по расстоянию Левенштейна был разработан следующий алгоритм фильтрации сигнатур. Пусть si и s2 - некоторые строки. Если строку si разбить на п непересекающихся фрагментов и то из этих фрагментов не будет присутствовать в s2, то это означает что расстояние Левенштейна между строками si и s2 составляет не менее т. Если применить эту утверждение к k-граммам, то его можно сформулировать следующим образом. Если в строке si есть то непересекающихся k-грамм, не входящих в s2, то расстояние Левенштейна между строками si и s2 составляет не менее т. Применим это утверждение к фильтрации сигнатур. Если в поисковой строке s есть то непересекающихся k-грамм, для которых не установлен бит в сигнатуре, то минимальное расстояние Левенштейна между s и строкой поддерева - то. Таким образом, нужно найти наибольшее число непересекающихся k-грамм поисковой строки, для которых не установлен бит в сигнатуре. Работа этого алгоритма представлена на рисунке 6. Этот алгоритм последовательно рассматривает k-граммы строки s. Если бит в сигнатуре для рассматриваемой к-граммы не установлен, то счетчик k-грамм, которые нужно найти уменьшается на единицу, а следующие к — 1 k-граммы пропускаются.

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

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

• база данных Geonames, 7603617 точек (GN)1;

• дороги Калифорнии, 2,249,727 МОП улиц Калифорнии (CAR)2;

1 http: //download. geonames . org/export/duinp/allCount.ries. zip

2 http://www.rtreeportal.org/datasets/spatial/US/CAR.tar.gz

блок

6 бл

бло

+1 не

совпадение

7 I 15

тгтг

запрашиваемая строка k-грамы запрашиваемой строки

смещения k-грам в сигнатуре

— 2 минимально возможное ' расстояние Левенштейна

совпадение

0 0 0 0 1 0 1 1 10 10 110 0

сигнатура

Рис. 6. Иллюстрация процесса фильтрации сигнатуры

• сеть каналов Tiger Streams, содержащая МОП 194,971 каналов штатов США Айова, Канзас, Миссури и Небраска (TS) 3.

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

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

• словарь английского языка объемом 98 тысяч слов, средняя длина слова 8, 4 знаков;

• словарь русского языка объемом 145 тысяч слов, средняя длина слова 11,3 знаков;

• названия статей из списка DBLP. Всего 2, 5 миллиона названий, средняя длина названия - 47 знаков.

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

3 http: //www.rtreeportal.org/datasets/spatial/US/TS.tar .gz

Таблица 1. Сравнение числа доступов к узлам на реальных данных (С(3 - квадратичный алгоритм Гуттмана. МЬ - «новый линейный» алгоритм. И* - алгоритм разделения узла И*-дерева, ББ - разработанный алгоритм)

Набор данных Ср. число Среднее число доступов к узлам

GQ NL R* DS

GN 4,87 14,4 ± 0,5 219 ± 13 11,0 ± 0,2 7,3 ± 0,4

11,07 16,9 ± 0,6 210 ± 14 12,1 ± 0,3 7,9 ± 0,5

101,36 26,6 ± 1,3 263 ± 17 14,8 ± 0,3 10,2 ± 0,4

998,70 52 ± 2 290 ± 20 29,8 ± 0,5 22,6 ± 0,7

CAR 1,32 7,5 ± 0,3 29,9 ± 1,4 7,0 ± 0,2 6,3 ± 0,2

11,32 8,2 ± 0,2 31,9 ± 1,6 7,3 ± 0,2 7,1 ± 0,3

102,93 11,4 ± 0,4 34,3 ± 1,6 10,3 ± 0,3 9,7 ± 0,3

999,67 28,7 ± 0,5 62 ± 2 27,8 ± 0,5 26,1 ± 0,6

TS 1,00 4,87 ± 0,13 14,8 ± 0,5 4,30 ± 0,10 4,39 ± 0,10

9,95 5,88 ± 0,16 16,6 ± 0,6 5,63 ± 0,13 5,21 ± 0,15

99,92 9,0 ± 0,2 22,5 ± 0,7 8,65 ± 0,17 8,48 ± 0,19

999,75 26,4 ± 0,3 46,2 ± 0,8 27,0 ± 0,3 25,3 ± 0,4

не велико (не превышает половины длины искомой строки). В этом случае скорость работы оказывается выше от 1,7 до 8 раз.

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

• английский словарь из пакета Aspell в дистрибутиве Ubuntu linux;

• имена людей с Web сайта комиссии по переписи населения в штате Техас США.

Эксперименты проводились с различным значением к от 2 до 5 и различной длиной сигнатуры: 480 бит, 992 бит, 1984 бит и 1872 бит. В качестве поисковых строк выбирались случайные строки из набора данных. Значение порога выбиралось в интервале от 1 до 3.

Разработанная индексная структура сравнивалась с инвертированным деревом на k-граммах по размеру индекса и скорости поиска по индексу. Сравнение размеров индекса для словаря английского языка представлено на рисунке 8. Число доступов к узлам для поиска по словарю английского языка с пороговым значением к = 2 представлено на рисунке 7.

Таблица 2. Среднее время вычисления расстояния Левенштейна для базы данных ВВЬР (К - полное заполнение матрицы £>, Т - заполнение только части ячеек на основе их расположения, Т - предлагаемый алгоритм)

Длина строки Порог Время вычисления, мс

N Т Р

1-10 1 - 10 5,79 ± 0,02 2,00 ± 0,02 1,11 ± 0,02

21-30 1 - 10 17,97 ± 0,10 5,20 ± 0,07 1,00 ± 0,02

21 -30 18,4 ± 0,2 13,0 ± 0,2 3,45 ± 0,11

41 - 50 1 - 10 27.70 ± 0,07 7,16 ± 0,07 1,18 ± 0,10

21 - 30 28,02 ± 0,12 20,52 ± 0,12 4,63 ± 0,07

41 - 50 28,87 ± 0,14 26,44 ± 0,15 12,30 ± 0,17

61-70 1 - 10 37,35 ± 0,08 9,26 ± 0,08 1,34 ± 0,10

21 - 30 37,55 ± 0,10 26,16 ± 0,11 5,07 ± 0,06

41 - 50 37,58 ± 0,10 34,36 ± 0,09 13,1 ± 0,10

G1 - 70 38,71 ± 0,14 38,82 ± 0,15 23,94 ± 0,18

81-90 1 - 10 47,71 ± 0,08 10,51 ± 0,12 1,37 ± 0,10

21 -30 47,50 ± 0,13 29,86 ± 0,18 4,17 ± 0,07

41 - 50 47,39 ± 0,13 40,65 ± 0,13 11,56 ± 0,14

61 - 70 47,73 ± 0,13 47,13 ± 0,12 23,21 ± 0,19

81 - 00 48,5 ± 0,2 50,2 ± 0,2 36,7 ± 0,3

101 - 110 1 - 10 57,57 ± 0,13 10,88 ± 0,18 1,40 ± 0,02

21 -30 57,4 ± 0,3 32,9 ± 0,3 3,04 ± 0,08

41 - 50 57,2 ± 0,2 45,0 ± 0,3 8,5 ± 0,2

61 - 70 57,5 ± 0,3 53,5 ± 0,2 19,0 ± 0,4

81 - 90 58,1 ± 0,3 58,9 ± 0,2 33,5 ± 0,4

101 - 110 59,5 ± 0,4 62,0 ± 0,3 48,7 ± 0,8

121 - 130 1 - 10 68,1 ± 0,2 12,8 ± 0,3 1,50 ± 0,02

21 - 30 68,2 ± 0,3 33,4 ± 0,5 2,05 ± 0,04

41 - 50 68,1 ± 0,3 47,4 ± 0,4 4,67 ± 0,17

61 - 70 67,9 ± 0,3 57,8 ± 0,3 12,25 ±0,4

81 - 90 68,0 ± 0,3 65,2 ± 0,3 26,19 ± 0,7

101 - 110 67,9 ± 0,3 69,7 ± 0,3 44,7 ± 0,6

121 - 130 68,3 ± 0,6 71,4 ± 0,6 59,47 ± 1,13

141 - 150 1-10 78,0 ± 0,4 11,7 ± 0,6 1,61 ± 0,02

21 -30 75,0 ± 0,3 35 ± 2 1,90 ± 0,09

41-50 76,6 ± 0,7 48,1 ± 1,4 2,9 ± 0,2

61 - 70 77,0 ± 0,8 59,8 ± 0,8 7,1 ± 0,6

81 - 90 78,2 ± 0,8 69,7 ± 0,6 16,98 ± 1,16

101 - 110 78,3 ± 0,7 76,4 ± 0,6 34,6 ± 1,8

121 - 130 79,4 ± 0,7 81,5 ± 0,6 53,2 ± 1,6

141 - 150 82,0 ± 1,4 85,5 ± 1,4 69,2 ± 3

161 - 170 1 - 10 91,1 ± 0,4 16,2 ± 0,7 1,75 ± 0,02

21-30 91,8 ± 0,3 35,7 ± 0,7 1,79 ± 0,02

41 - 50 91,4 ± 0,4 49,3 ± 0,6 2,03 ± 0,02

61 - 70 91,0 ± 0,4 62,1 ± 0,5 3,33 ± 0,12

81 - 90 90,9 ± 0,4 72,7 ± 0,5 7,7 ± 0,4

101 - 110 90,5 ± 0,5 81,6 ± 0,5 19,7 ± 0,9

121 - 130 91,4 ± 0,5 88,8 ± 0,3 39,0 ± 1,6

141 - 150 90,5 ± 0,5 93,1 ± 0,4 64,9 ± 1,3

161 - 170 90,6 ± 0,5 94,9 ± 0,5 82,6 ± 1,4

500.00

50,00

СС

Рис. 7. Среднее число доступов к узлам при поиске по расстоянию Левенштейна с порогом 2 на наборе данных №1

18000000

£ ю

О

16000000 14000000 12000000 10000000 8000000 6000000 4000000 2000000

Рис. 8. Размеры индексных структур на наборе данных №1

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

В заключении отражены основные результаты, полученные в данной диссертационной работе.

В приложение вынесены акты о внедрениях, а также исходные коды, разработанные в ходе данной диссертационной работы и включенные в код наиболее развитой СУБД с открытым исходным кодом PostgreSQL.

Основные результаты работы

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

2. Для разделения узла одномерного 11-дерева введены понятия разделяющей пары и угловой разделяющей пары. Разработан алгоритм разделения узла одномерного II-дерева на основе двойной сортировки, осуществляющий перечисление всех угловых разделяющих нар, и его применение к многомерному случаю. Проведен анализ работы алгоритма в одномерном случае для различных входных данных.

3. Разработан новый алгоритм вычисления расстояния Левенштейна с пороговым значением. Этот алгоритм позволяет более полно отсекать вычисления, которые не могут повлиять на конечный результат.

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

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

6. Проведена экспериментальная проверка разработанного алгоритма вычисления расстояния Левенштейна с пороговым значением, которое показало, что разработанный алгоритм позволяет существенно сократить время поиска (ускорение от 1,7 до 8 раз), когда пороговое значение не велико (не превышает половины длины искомой строки).

7. Проведена экспериментальная проверка разработанного применения 1Ш-дерева к набору к-грамм, которое показало, что разработанная индексная структура имеет размер от 2,3 до 7 раз меньше по сравнению с инвертированным деревом, сохраняя при этом сравнимое время поиска по расстоянию Левенштейна.

8. Разработанный алгоритм разделения узла для 11-дерева был применен в Государственном астрономическом институте им. П. К. Штернберга для поиска астрономических объектов.

9. Разработанный алгоритм разделения узла для Ы-дерева, а также методы нечеткого поиска текста были применены в ЗАО «Геноаналитика» для построения генетической карты и поиске формулировок заболеваний.

10. Программная реализация разработанного алгоритма разделения узла 11-дерева была включена в наиболее развитую СУБД с открытым исходным кодом PostgreSQL 4.

11. Программная реализация разработанного вычисления расстояния Левенштейна с пороговым значением была включена в исходных код наиболее развитой СУБД с открытым исходным кодом PostgreSQL 5.

Основные публикации по теме диссертации

1. Korotkov A. Database index for approximate string matching // Proceedings of the 4th Spring/Summer Young Researchers' Colloquium on Software Engineering. SYRCoSE '10. 2010. Pp. 136-140.

2. Korotkov A. Information system user interfaces automatic creation. SYRCoSE '09. 2009. Pp. 132-134.

3. Korotkov A. A new double sorting-based node splitting algorithm for R-tree // Proceedings of the 5th Spring/Summer Young Researchers' Colloquium on Software Engineering. SYRCoSE '11. 2011. Pp. 36-41.

4. Korotkov A. Automatic Creation of User Interfaces for Information System // Proceedings of the IADIS International Conference Applied Computing. IADIS '09. 2009. Pp. 327-329.

5. Коротков A. E. Индекс базы данных для нечеткого поиска строки // Труды XIX международного научно-технического семинара. МНТС '10. 2010. С. 208-209.

6. Коротков А. Е., Панферов В. В. Применение обобщенного дерева поиска для нечеткого поиска текста // Труды научной сессии МИФИ-2010. 2010. С.. 174-176.

7. Korotkov A. A new double sorting-based node splitting algorithm for R-tree // Programming and Computer Software. 2012. Vol. 38. Pp. 109-118.

4 http://goo.gl/u6RLI

5 http://goo.gl/WS91f

8. Shelenkov A., Korotkov A., Korotkov E. MMsat—a database of potential micro- and minisatellites // Gene. 2008. Vol. 409, no. 1-2. Pp. 53 - 60.

9. Короткой А. E., Панферов В. В. Применение обобщенного дерева поиска для нечеткого поиска строки // Наука и образование. 2011. Т. 3.

10. Короткое А. Е. Алгоритм разделения одномерных интервалов на группы при индексировании // Естественные и технические науки. 2012. Т. 1. С. 312-316.

11. Коротков А. Е., Трифонова Е. Е. Алгоритм расчета расстояния Левенштейна с пороговым значением // Естественные и технические науки. 2012. Т. 1. С. 317-322.

12. Кудрявцев К. Я., Коротков А. Е. Методы повышения скорости поиска информации в базах данных. LAP Lambert Aeademic Publishing, 2012. 84 с.

Подписано в печать 20.11.2012. Формат 60x84 1/16. Объем 1,25 п.л. Тираж 100 экз. Заказ №261 Типография НИЯУ МИФИ. 115409, Москва, Каширское шоссе, д. 31

Введение

Глава 1. Анализ современных методов доступа к данным

1.1. Современные методы доступа к данным.

1.2. Задача поиска пространственных данных.

1.2.1. Введение.

1.2.2. 11-дерево.

1.2.3. Разделение узла в И-дереве.

1.3. Задача нечеткого поиска в строковых массивах.

1.3.1. Расстояние Левенштейна.

1.3.2. Разложение строки на к-граммы.

1.3.3. ЦБ-дерево.

1.4. Выводы по первой главе

Глава 2. Методы ускорения поиска пространственных данных

2.1. Основные понятия и определения.

2.2. Анализ вариантов применения угловых разделяющих пар

2.3. Алгоритм разделения узла Я-дерева

2.4. Применение алгоритма разделения узла 11-дерева к многомерному случаю.

2.5. Выводы по второй главе

Глава 3. Методы ускорения нечеткого поиска в наборах строк

3.1. Вычисление расстояния Левенштейна с пороговым значением

3.1.1. Обозначения и соотношения.

3.1.2. Алгоритм вычисления расстояния Левенштейна с пороговым значением.

3.2. Применение ГШ-дерева к набору к-грамм для поиска по расстоянию Левенштейна.

3.2.1. Структура данных.

3.2.2. Алгоритм фильтрации сигнатур.

3.3. Выводы по третьей главе.

Глава 4. Экспериментальная проверка разработанных методов 88 4.1. Экспериментальная проверка разработанного алгоритма

разделения узла II-дерева.

4.1.1. Наборы данных.

4.1.2. Эксперименты для одномерного случая на синтетических наборах данных.

4.1.3. Эксперименты для многомерного случая на синтетических наборах данных.

4.1.4. Эксперименты на реальных данных

4.2. Экспериментальная проверка алгоритма вычисления расстояния Левепштейна с пороговым значением.

4.2.1. Наборы данных.

4.2.2. Методика проведения экспериментов.

4.2.3. Результаты.

4.3. Экспериментальная проверка RD-дерева на основе k-грамм

4.3.1. Наборы данных.

4.3.2. Результаты.

4.4. Выводы по четвертой главе.

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

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

Одной из наиболее широко применяемых структур данных является В-дерево. В-дерево обеспечивает высокую скорость выполнения запросов, связанных с типами данных и поисковыми предикатами, заданными SQL стандартом. Однако, для многих современных приложений необходима работа с типами данных и поисковыми предикатами, не заданными стандартом SQL. Примером таких типов данных могут служить геометрические типы данных (точки, многоугольники, кривые и т.д.), которые широко применяются в геоинформационных системах (ГИС). В ГИС также применяются не заданные SQL стандартом поисковые предикаты, такие как предикат пересечения геометрических объектов, предикат вхождения одного геометрического объекта в другой. Хотя для ГИС существуют различные стандарты, такие как Open GIS, структуры данных используемые СУБД для эффективной обработки поисковых запросов отличаются.

Существуют различные структуры данных, призванные обеспечить высокую скорость обработки поисковых запросов, касающихся пространственных данных, такие как разновидности grid-файлов [1-4], Quadtree и подобные ему деревья [5-7], R-дерево и подобные ему деревья [8-10]. У каждой структуры данных есть свои преимущества и недостатки. R-дерево и его разновидности наиболее популярны по сравнению с другими перечисленными структурами данных, поскольку они могут эффективно работать во внешней памяти, а также могут хранить объекты, обладающие протяженностью, а не только точки. Основным недостатком R-дерева является то, что охватывающие прямоугольники его узлов могут пересекаться. Сильная степень этого пересечения приводит к тому, что при поиске нужно сканировать много путей в дереве, что снижает скорость поиска. Способом уменьшения этого недостатка может быть новый алгоритм разделения узла для R-дерева, позволяющий уменьшить степень пересечения охватывающих прямоугольников узлов, тем самым увеличивая скорость поиска.

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

• Высокая вычислительная сложность расстояния Левенштейна при большом объеме исходных строк.

• Ограничения методов индексации для поиска по расстоянию Левенштейна в строковых массивах.

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

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

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

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

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

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

3. Разработать индексную структуру на основе РШ-дерева и к-грамм для поиска в наборах строк по расстоянию Левенштейна.

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

Объектами исследований диссертационной работы являются базы данных, содержащие наборы пространственных данных и наборы строк.

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

Методами исследования исследования диссертационной работы являются методы теории множеств, теории алгоритмов, линейной алгебры, математического анализа.

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

1. Разработан новый алгоритм разделения узла II-дерева для одномерного случая, основанный на использовании нового понятия «угловой разделяющей пары».

2. Разработано применение нового алгоритма разделения узла для II-дерева к многомерному случаю.

3. Разработан новый алгоритм вычисления расстояния Левенштейна с пороговым значением и математически доказана его корректность.

4. Разработана структура данных на основе 1Ш-дерева и к-грамм для поиска в наборах строк по расстоянию Левенштейна.

5. Разработан алгоритм фильтрации сигнатур для структуры данных на основе 1Ш-дерева и к-грамм, математически доказана его корректность.

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

1. Новый алгоритм разделения узла 11-дерева позволяет повысить скорость поиска пространственных данных.

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

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

1. новый алгоритм разделения узла R-дерева для одномерного случая, основанный на использовании нового понятия «угловой разделяющей пары»;

2. применение нового алгоритма разделения узла для R-дерева к многомерному случаю;

3. новый алгоритм вычисления расстояния Левенштейна с пороговым значением;

4. структура данных на основе RD-дерева и k-грамм для поиска в наборах строк по расстоянию Левенштейна;

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

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

• Spring/Summer Young Researchers' Colloquium on Software Engineering (SYRCoSE) [11-13];

• IADIS International Conference Applied Computing [14];

• Международный научно-технический семинар в городе Алушта [15];

• Научная сессия МИФИ [16].

Реализация результатов диссертации заключается в следующем.

1. Программная реализация предложенного алгоритма разделения узла 11-дерева была включена в исходных код наиболее развитой СУБД с открытым исходным кодом PostgreSQL.

2. Программная реализация предложенного алгоритма вычисления расстояния Левенштейна с пороговым значением была включена в исходных код наиболее развитой СУБД с открытым исходным кодом PostgreSQL.

3. Разработанный алгоритм разделения узла для Я-дерева был применен в Государственном астрономическом институте им. П. К. Штернберга для поиска астрономических объектов.

4. Разработанный алгоритм разделения узла для 11-дерева, а также методы нечеткого поиска текста были применены в ЗАО «Геноаналитика» для построения генетической карты и поиске формулировок заболеваний.

Публикации

Всего по теме диссертации опубликовано 12 печатных работ [11-22] в том числе 5 статьи в журналах, рекомендованных ВАК РФ для публикации основных результатов работы [17-21].

Личный вклад автора

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

Структура и объем диссертации Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы из 115 наименований и одного приложения. Основная работа диссертации содержит 132 страницы текста, включая 47 рисунков и 7 таблиц.

4.4. Выводы по четвертой главе

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

1. синтетический равномерный набор данных для 1-4 измерений;

2. синтетический равномерный набор данных с кластерами для 1-4 измерений;

3. синтетический нормальный набор данных для 1-4 измерений;

4. синтетический нормальный набор данных с кластерами для 1-4 измерений;

5. база данных Geonames;

6. дороги Калифорнии;

7. сеть каналов Tiger Streams.

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

1. словарь английского языка;

2. словарь русского языка;

3. названий статей из списка DBLP.

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

1. словарь английского языка;

2. имена людей.

На основании результатов экспериментальных проверок можно сделать следующие выводы.

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

2. Показано, что разработанный алгоритм вычисления расстояния Левенштейна с пороговым значением позволяет существенно сократить время поиска (от 1,7 до 8 раз), когда пороговое значение не велико (не превышает половины длины искомой строки).

3. Показано, что предложенное применение ГШ-дерева к набору к-грамм позволяет уменьшить размер индекса от 2,3 до 7 раз по сравнению с инвертированным деревом, сохраняя при этом сравнимое время поиска по расстоянию Левенштейна.

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

Программная реализация разработанного алгоритма вычисления расстояния Левенштейна с пороговым значением была включена в исходный код наиболее развитой СУБД с открытым исходным кодом PostgreSQL 7. Исходный код приведен в приложении Б.

Заключение

В данной диссертационной работе представлены следующие результаты.

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

2. Для разделения узла одномерного Я-дерева введены понятия разделяющей пары и угловой разделяющей пары. Разработан алгоритм разделения узла одномерного Я-дерева на основе двойной сортировки, осуществляющий перечисление всех угловых разделяющих пар, и его применение к многомерному случаю. Проведен анализ работы алгоритма в одномерном случае для различных входных данных.

3. Разработан новый алгоритм вычисления расстояния Левенштейна с пороговым значением. Этот алгоритм позволяет более полно отсекать вычисления, которые не могут повлиять на конечный результат.

4. Предложено применение ШЗ-дерева к набору к-грамм для поиска в строковых массивах по расстоянию Левенштейна. Разработан алгоритм фильтрации сигнатур, позволяющий пропускать при сканировании больше поддеревьев, чем при фильтрации на базе числа общих к-грамм.

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

6. Проведена экспериментальная проверка разработанного алгоритма вычисления расстояния Левенштейна с пороговым значением, которое показало, что разработанный алгоритм позволяет существенно сократить время поиска (ускорение от 1,7 до 8 раз), когда пороговое значение не велико (не превышает половины длины искомой строки).

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

Были выполнены следующие внедрения результатов диссертационной работы.

1. Разработанный алгоритм разделения узла для R-дерева был применен в Государственном астрономическом институте им. П. К. Штернберга для поиска астрономических объектов. Акт о внедрении представлен в приложении А.

2. Разработанный алгоритм разделения узла для R-дерева, а также методы нечеткого поиска текста были применены в ЗАО «Геноаналитика» для построения генетической карты и поиске формулировок заболеваний. Акт о внедрении представлен в приложении А.

3. Программная реализация разработанного алгоритма разделения узла R-дерева была включена в СУБД с открытым исходным кодом PostgreSQL 8. Исходный код приведен в приложении Б.

4. Программная реализация разработанного алгоритма вычисления расстояния Левенштейна с пороговым значением была включена в СУБД с открытым исходным кодом PostgreSQL 9. Исходный код приведен в приложении Б.

1. Hinriehs K. The grid file system: implementation and case studies of applications: Ph. D. thesis. Zurich, ETH, Switzerland: 1.stitute fur Informatik, 1985.

2. Ouksel M. A. The interpolation-based grid file // Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems. PODS '85. New York, NY, USA: ACM, 1985. Pp. 20-27.

3. Whang K.-Y., Krishnamurthy R. The Multilevel Grid File A Dynamic Hierarchical Multidimensional File Structure // Proceedings of the Second International Symposium on Database Systems for Advanced Applications. World Scientific Press, 1992. Pp. 449-459.

4. Blanken H. M., IJbema A., Meek P., Akker B. v. d. The Generalized Grid File: Description and Performance Aspects // Proceedings of the Sixth International Conference on Data Engineering. Washington, DC, USA: IEEE Computer Society, 1990. Pp. 380-388.

5. Finkel R. A., Bentley J. L. Quad trees a data structure for retrieval on composite keys // Acta Informatica. 1974. Vol. 4. Pp. 1-9. 10.1007/BF00288933.

6. Bentley L. J. Multidimensional binary search trees used for associative searching // Commun. ACM. 1975.— September. Vol. 18. Pp. 509-517.

7. Robinson T. J. The K-D-B-tree: a search structure for large multidimensional dynamic indexes // Proceedings of the 1981 ACM SIGMOD international conference on Management of data. SIGMOD '81. New York, NY, USA: ACM, 1981. Pp. 10-18.

8. Beckmann N., Kriegel H.-R, Schneider R., Seeger B. The R*-tree: an efficient and robust access method for points and rectangles // SIGMOD Rec. 1990. — May. Vol. 19. Pp. 322-331.

9. Guttman A. R-trees: a dynamic index structure for spatial searching // SIGMOD Rec. 1984.-June. Vol. 14. Pp. 47-57.

10. Korotkov A. Database index for approximate string matching // Proceedings of the 4th Spring/Summer Young Researchers' Colloquium on Software Engineering. SYRCoSE '10. 2010. Pp. 136-140.

11. Korotkov A. Information system user interfaces automatic creation. SYRCoSE '09. 2009. Pp. 132-134.

12. Korotkov A. A new double sorting-based node splitting algorithm for R-tree // Proceedings of the 5th Spring/Summer Young Researchers' Colloquium on Software Engineering. SYRCoSE '11. 2011. Pp. 36-41.

13. Korotkov A. Automatic Creation of User Interfaces for Information System // Proceedings of the IADIS International Conference Applied Computing. IADIS '09. 2009. Pp. 327-329.

14. Коротков A. E. Индекс базы данных для нечеткого поиска строки // Труды XIX международного научно-технического семинара. МНТС '10. 2010. С. 208-209.

15. Коротков А. Е., Панферов В. В. Применение обобщенного дерева поиска для нечеткого поиска текста // Труды научной сессии МИФИ-2010. 2010. С. 174-176.

16. Korotkov A. A new double sorting-based node splitting algorithm for R-tree // Programming and Computer Software. 2012. Vol. 38. Pp. 109-118.

17. Shelenkov A., Korotkov A., Korotkov E. MMsat—a database of potential micro- and minisatellites // Gene. 2008. Vol. 409, no. 1-2. Pp. 53 60.

18. Коротков A. E., Панферов В. В. Применение обобщенного дерева поиска для нечеткого поиска строки // Наука и образование. 2011. Т. 3.

19. Коротков А. Е. Алгоритм разделения одномерных интервалов на группы при индексировании // Естественные и технические науки. 2012. Т. 1. С. 312-316.

20. Коротков А. Е., Трифонова Е. Е. Алгоритм расчета расстояния Левенштейна с пороговым значением // Естественные и технические науки. 2012. Т. 1. С. 317-322.

21. Кудрявцев К. Я., Коротков А. Е. Методы повышения скорости поиска информации в базах данных. LAP Lambert Academic Publishing, 2012. 84 с.

22. Bayer R., McCreight E. Organization and maintenance of large ordered indices // Proceedings of the 1970 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control. SIGFIDET '70. New York, NY, USA: ACM, 1970. Pp. 107-141.

23. Comer D. Ubiquitous B-Tree // ACM Comput. Surv. 1979. — June. Vol. 11. Pp. 121-137.

24. Samet H. The Quadtree and Related Hierarchical Data Structures // ACM Comput. Surv. 1984.-June. Vol. 16. Pp. 187-260.

25. Samet H. An overview of quadtrees, octrees, and related hierarchical data structures // Theoretical Foundations of Computer Graphics and CAD. 1988. Vol. 40, no. 1. Pp. 51-68.

26. Samet H. Applications of spatial data structures: Computer graphics, image processing, and GIS. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1990.

27. Samet H. The design and analysis of spatial data structures. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1990.

28. Hunter G. M. Efficient computation and data structures for graphics.: Ph. D. thesis. Princeton, NJ, USA: Princeton University, 1978. AAI7823520.

29. Donald, Meagher. Geometric modeling using octree encoding // Computer Graphics and Image Processing. 1982. Vol. 19, no. 2. Pp. 129 147.

30. Six H.-W., Widmayer P. Spatial Searching in Geometric Databases // Proceedings of the Fourth International Conference on Data Engineering. Washington, DC, USA: IEEE Computer Society, 1988. Pp. 496-503.

31. Merrett T. H. Multidimensional paging for efficient database querying // Proceedings of the International Conference in Management of Data. Milan: 1978. June. Pp. 277-289.

32. Moffat A., Zobel J. Self-indexing inverted files for fast text retrieval // ACM Trans. Inf. Syst. 1996.-October. Vol. 14. Pp. 349-379.

33. Shieh W.-Y., Chung C.-P. A statistics-based approach to incrementally update inverted files // Inf. Process. Manage. 2005. —March. Vol. 41. Pp. 275-288.

34. Williams H. E., Zobel J., Bahle D. Fast phrase querying with combined indexes // ACM Trans. Inf. Syst. 2004. October. Vol. 22. Pp. 573-594.

35. Zobel J., Moffat A. Inverted files for text search engines // ACM Comput. Surv. 2006.-July. Vol. 38.

36. Wagner R. A., Fischer M. J. The String-to-String Correction Problem //J. ACM. 1974.-January. Vol. 21. Pp. 168-173.

37. Wagner R. A., Lowrance R. An Extension of the String-to-String Correction Problem // J. ACM. 1975.-April. Vol. 22. Pp. 177-183.

38. Nesbit J. C. The accuracy of approximate string matching algorithms //J. Comput. Based Instruct. 1986.— August. Vol. 13. Pp. 80-83.

39. Owolabi O., McGregor D. R. Fast approximate string matching // Softw. Pract. Exper. 1988.-April. Vol. 18. Pp. 387-393.

40. Kukich К. Techniques for automatically correcting words in text // ACM Comput. Surv. 1992.-December. Vol. 24. Pp. 377-439.

41. French J. C., Powell A. L., Schulman E. Applications of approximate word matching in information retrieval // Proceedings of the sixth international conference on Information and knowledge management. CIKM '97. New York, NY, USA: ACM, 1997. Pp. 9-15.

42. Baeza-Yates R. A., Ribeiro-Neto B. Modern Information Retrieval. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1999.

43. Левенштейн В. Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады Академий Наук СССР. 1965. Т. 163, № 4. С. 845-848.

44. Jaro M. A. Probabilistic linkage of large public health data files // Statistics in Medicine. 1995. Vol. 14, no. 5-7. Pp. 491-498.

45. Bayardo R. J., Ma Y., Srikant R. Scaling up all pairs similarity search // Proceedings of the 16th international conference on World Wide Web. WWW '07. New York, NY, USA: ACM, 2007. Pp. 131-140.

46. Cohen W. W. Integration of heterogeneous databases without common domains using queries based on textual similarity // SIGMOD Rec. 1998. — June. Vol. 27. Pp. 201-212.

47. Vintsyuk T. K. Speech discrimination by dynamic programming // Cybernetics and Systems Analysis. 1968. Vol. 4. Pp. 52-57. 10.1007/BF01074755.

48. Keshet J., Bengio S. Automatic speech and speaker recognition: large margin and kernel methods. J. Wiley & Sons, 2009.

49. Sellers P. H. On the Theory and Computation of Evolutionary Distances // SIAM Journal on Applied Mathematics. 1974. Vol. 26, no. 4. Pp. 787-793.

50. H P., Sellers. The theory and computation of evolutionary distances: Pattern recognition // Journal of Algorithms. 1980. Vol. 1, no. 4. Pp. 359 373.

51. Needleman S. B., Wunsch C. D. A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of two Proteins // Journal of Molecular Biology. 1970.-March. Vol. 48, no. 3. Pp. 443-453.

52. Sankoff D., Mainville S. Common Subsequences and Monotone Subsequences // Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison / Ed. by D. Sankoff, J. B. Kruskal. Addison-Wesley, 1983. Pp. 363-365.

53. Altschul S. F., Gish W., Miller W. et al. Basic local alignment search tool. // Journal of molecular biology. 1990.— October. Vol. 215, no. 3. Pp. 403-410.

54. Myers E. W. An overview of sequence comparison algorithms in molecular biology. University of Arizona, Dept. of Computer Science, 1991.

55. Suhai S. Computational methods in genome research. Language of science. Plenum Press, 1994.

56. Waterman M. S. Introduction to computational biology maps, sequences, and genomes: interdisciplinary statistics. CRC Press, 1995. Pp. I-XV, 1-431.

57. Yap T., Frieder 0., Martino R. High performance computational methods for biological sequence analysis. Kluwer Academic Publishers, 1996.

58. Gusfield D. Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press, 1997.

59. Li C., Wang B., Yang X. VGRAM: improving performance of approximate queries on string collections using variable-length grams // Proceedings of the 33rd international conference on Very large data bases. VLDB '07. VLDB Endowment, 2007. Pp. 303-314.

60. Sarawagi S., Kirpal A. Efficient set joins on similarity predicates // Proceedings of the 2004 ACM SIGMOD international conference on Management of data. SIGMOD '04. New York, NY, USA: ACM, 2004. Pp. 743-754.

61. Li C., Lu J., Lu Y. Efficient Merging and Filtering Algorithms for Approximate String Searches // Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. Washington, DC, USA: IEEE Computer Society, 2008. Pp. 257-266.

62. Chaudhuri S., Kaushik R. Extending autocompletion to tolerate errors // Proceedings of the 35th SIGMOD international conference on Management of data. SIGMOD '09. New York, NY, USA: ACM, 2009. Pp. 707-718.

63. Hellerstein J. M., Pfeffer A. The RD-Tree: An Index Structure for Sets: Tech. Rep. 1252: University of Wisconsin at Madison, 1994.— October.

64. Deppisch U. S-tree: a dynamic balanced signature index for office retrieval // Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval. SIGIR '86. New York, NY, USA: ACM, 1986. Pp. 77-87.

65. Aoki P. M. Generalizing "Searchnin Generalized Search Trees (Extended Abstract) // Proceedings of the Fourteenth International Conference on Data Engineering. ICDE '98. Washington, DC, USA: IEEE Computer Society, 1998. Pp. 380-389.

66. Kornacker M. Access methods for next-generation database systems: Ph. D. thesis. University of California, Berkeley, 2000. AAI9994590.

67. Kornacker M., Mohan C., Hellerstein J. M. Concurrency and recovery in generalized search trees // SIGMOD Ree. 1997.-June. Vol. 26. Pp. 62-72.

68. Aref W. G., Ilyas I. F. SP-GiST: An Extensible Database Index for Supporting Space Partitioning Trees // J. Intell. Inf. Syst. 2001.— December. Vol. 17. Pp. 215-240.

69. Sigaev T., Bartunov O. GiST support in PostgreSQL. http://www.sai. msu.su/~megera/postgres/gist/. v

70. Sigaev T., Bartunov O. SP-GiST for hackers, http://www.sai.msu.su/ "megera/wiki/spgistdev.

71. Aref W. G., Samet H. Efficient processing of window queries in the pyramid data structure // Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. PODS '90. New York, NY, USA: ACM, 1990. Pp. 265-272.

72. Jagadish H. V. On Indexing Line Segments // Proceedings of the 16th International Conference on Very Large Data Bases. VLDB '90. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1990. Pp. 614-625.

73. Orenstein J. A., Merrett T. H. A class of data structures for associative searching // Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems. PODS '84. New York, NY, USA: ACM, 1984. Pp. 181-190.

74. Hinrichs K. H., Nievergelt J. The grid file: a data structure designed to support proximity queries on spatial objects: Tech. Rep. 54: Institut fur Informatik, ETH Zurich, 1983.

75. Orenstein J. A. Redundancy in spatial databases // SIGMOD Ree. 1989.— June. Vol. 18. Pp. 295-305.

76. Papadias D., Sellis T., Theodoridis Y., Egenhofer M. J. Topological relations in the world of minimum bounding rectangles: a study with R-trees // SIGMOD Ree. 1995.-May. Vol. 24. Pp. 92-103.

77. Lin P. L., Tan W. H. An efficient method for the retrieval of objects by topological relations in spatial database systems // Inf. Process. Manage. 2003. July. Vol. 39. Pp. 543-559.

78. Papadias D., Theodoridis Y., Sellis T. K. The Retrieval of Direction Relations using R-trees // Proceedings of the 5th International Conference on Database and Expert Systems Applications. DEXA '94. London, UK: Springer-Verlag, 1994. Pp. 173-182.

79. Berchtold S., Keim D. A., Kriegel H.-P., Seidl T. Indexing the Solution Space: A New Technique for Nearest Neighbor Search in High-Dimensional Space // IEEE Trans, on Knowl. and Data Eng. 2000. — January. Vol. 12. Pp. 45-57.

80. Manolopoulos Y., Nanopoulos A., Papadopoulos A. N., Theodoridis Y. R-Trees: Theory and Applications (Advanced Information and Knowledge Processing). Secaucus, NJ, USA: Springer-Verlag New York, Inc., 2005.

81. Brakatsoulas S., Pfoser D., Theodoridis Y. Revisiting R-Tree Construction Principles // Proceedings of the 6th East European Conference on Advances in Databases and Information Systems. ADBIS '02. London, UK: Springer-Verlag, 2002. Pp. 149-162.

82. Al-Badarneh A. F., Yaseen Q., Hmeidi I. A new enhancement to the R-tree node splitting //J. Information Science. 2010. Vol. 36, no. 1. Pp. 3-18.

83. Greene D. An Implementation and Performance Analysis of Spatial Data Access Methods // Proceedings of the Fifth International Conference on

84. Data Engineering. Washington, DC, USA: IEEE Computer Society, 1989. Pp. 606-615.

85. Tao Y., Papadias D. Performance analysis of R*-trees with arbitrary node extents // Tran. Knowl. Data Eng. (TKDE. 2004. Vol. 16. Pp. 6-653.

86. Kanth K., Agrawal D., Singh A., Abbadi A. E. Indexing non-uniform spatial data // Database Engineering and Applications Symposium, International. 1997. Vol. 0. P. 289.

87. Ang C.-H., Tan Т. C. New Linear Node Splitting Algorithm for R-trees // Proceedings of the 5th International Symposium on Advances in Spatial Databases. SSD '97. London, UK: Springer-Verlag, 1997. Pp. 339-349.

88. Скворцов А. В. Глобальные алгоритмы построения R-деревьев // Геоинформатика. Теория и практика. 1998. № 1. С. 67-83.

89. Скворцов А. В. Алгоритмы улучшения качества R-деревьев // Известия вузов. Физика. 2001. Т. 44, № 6. С. 21-27.

90. Gong J., Ке S. A new node-split algorithm in R-tree based on spatial clustering // FSKD / Ed. by M. Li, Q. Liang, L. Wang, Y. Song. IEEE, 2010. Pp. 2081-2085.

91. Aggarwal С. C., Wolf J. L., Yu P. S., Epelman M. The S-Tree: An Efficient Index for Multidimensional Objects // Proceedings of the 5th International Symposium on Advances in Spatial Databases. SSD '97. London, UK: Springer-Verlag, 1997. Pp. 350-373.

92. Ross K. A., Sitzmann I., Stuckey P. J. Cost-Based Unbalanced R-Trees // Proceedings of the 13th International Conference on Scientific and Statistical

93. Database Management. SSDBM '01. Washington, DC, USA: IEEE Computer Society, 2001. Pp. 203100. Salzberg В., Tsotras V. J. Comparison of access methods for time-evolving data // ACM Comput. Surv. 1999.-June. Vol. 31. Pp. 158-221.

94. Arasu A., Ganti V., Kaushik R. Efficient exact set-similarity joins // Proceedings of the 32nd international conference on Very large data bases. VLDB '06. VLDB Endowment, 2006. Pp. 918-929.

95. Chaudhuri S., Ganjam K., Ganti V., Motwani R. Robust and efficient fuzzy match for online data cleaning // Proceedings of the 2003 ACM SIGMOD international conference on Management of data. SIGMOD '03. New York, NY, USA: ACM, 2003. Pp. 313-324.

96. Sutinen E., Tarhio J. On Using q-Gram Locations in Approximate String Matching // Proceedings of the Third Annual European Symposium on Algorithms. ESA '95. London, UK: Springer-Verlag, 1995. Pp. 327-340.

97. Sutinen E., Tarhio J. Filtration with q-Samples in Approximate String Matching // Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching. CPM '96. London, UK: Springer-Verlag, 1996. Pp. 50-63.

98. Ukkonen E. Approximate string-matching with q-grams and maximal matches // Theor. Comput. Sci. 1992. — January. Vol. 92. Pp. 191-211.

99. Damerau F. J. A technique for computer detection and correction of spelling errors // Commun. ACM. 1964. —March. Vol. 7. Pp. 171-176.

100. Yang R., Kalnis P., Tung A. K. H. Similarity evaluation on tree-structured data // Proceedings of the 2005 ACM SIGMOD international conference on Management of data. SIGMOD '05. New York, NY, USA: ACM, 2005. Pp. 754-765.

101. Bloom B. H. Space/time trade-offs in hash coding with allowable errors // Commun. ACM. 1970.-July. Vol. 13. Pp. 422-426.

102. Peterson W. W., Brown D. T. Cyclic Codes for Error Detection // Proceedings of the IRE. 1961. Vol. 49. Pp. 228-235.

103. Sigaev T., Bartunov O. pgtrgm. http://www.p0stgresql.0rg/d0cs/9. 1 / s t at i c/pgt r gm. ht ml.

104. Navarro G., Baeza-yates R., Sutinen E., Tarhio J. Indexing Methods for Approximate String Matching // IEEE Data Engineering Bulletin. 2000. Vol. 24. P. 2001.

105. Navarro G. A guided tour to approximate string matching // ACM Comput. Surv. 2001.-March. Vol. 33. Pp. 31-88.

106. Theodoridis Y., Sellis T. A model for the prediction of R-tree performance // Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposiumon Principles of database systems. PODS '96. New York, NY, USA: ACM, 1996. Pp. 161-171.