Содержание к диссертации
Введение
Глава 1. Анализ современных методов доступа к данным 10
1.1. Современные методы доступа к данным 10
1.2. Задача поиска пространственных данных
1.2.1. Введение 14
1.2.2. R-дерево 17
1.2.3. Разделение узла в R-дереве 26
1.3. Задача нечеткого поиска в строковых массивах 34
1.3.1. Расстояние Левенштейна 36
1.3.2. Разложение строки на k-граммы 41
1.3.3. RD-дерево 42
1.4. Выводы по первой главе 48
Глава 2. Методы ускорения поиска пространственных данных 50
2.1. Основные понятия и определения 50
2.2. Анализ вариантов применения угловых разделяющих пар 52
2.3. Алгоритм разделения узла R-дерева 57
2.4. Применение алгоритма разделения узла R-дерева к многомерному случаю 63
2.5. Выводы по второй главе 67
Глава 3. Методы ускорения нечеткого поиска в наборах строк 68
3.1. Вычисление расстояния Левенштейна с пороговым значением 68
3.1.1. Обозначения и соотношения 69
3.1.2. Алгоритм вычисления расстояния Левенштейна с пороговым значением 77
3.2. Применение RD-дерева к набору k-грамм для поиска по расстоянию Левенштейна 81
3.2.1. Структура данных 81
3.2.2. Алгоритм фильтрации сигнатур 83
3.3. Выводы по третьей главе 86
Глава 4. Экспериментальная проверка разработанных методов 88
4.1. Экспериментальная проверка разработанного алгоритма разделения узла R-дерева 90
4.1.1. Наборы данных 90
4.1.2. Эксперименты для одномерного случая на синтетических наборах данных з
4.1.3. Эксперименты для многомерного случая на синтетических наборах данных 94
4.1.4. Эксперименты на реальных данных 102
4.2. Экспериментальная проверка алгоритма вычисления расстояния Левеиштейна с пороговым значением 103
4.2.1. Наборы данных 103
4.2.2. Методика проведения экспериментов 104
4.2.3. Результаты 104
4.3. Экспериментальная проверка RD-дерева на основе k-грамм 108
4.3.1. Наборы данных 108
4.3.2. Результаты 108
4.4. Выводы по четвертой главе 114
Заключение 116
Литература
- Задача поиска пространственных данных
- Анализ вариантов применения угловых разделяющих пар
- Алгоритм вычисления расстояния Левенштейна с пороговым значением
- Эксперименты для одномерного случая на синтетических наборах данных
Введение к работе
Актуальность темы Информационные технологии интенсивно развиваются в современном мире и охватывают всё новые виды деятельности человека. В связи с этим накапливаются огромные массивы данных, и вопросы их обработки и хранения стоят особенно остро. При этом нагрузки на базы данных (БД) постоянно возрастают. Постоянно повышающиеся требования удовлетворяются как за счет совершенствования аппаратных средств, так и с помощью применения новых алгоритмов и структур данных. Таким образом, для современных БД, помимо современной аппаратной платформы, крайне важным является наличие высокопроизводительных методов доступа к данным.
Задачи повышения производительности носят разносторонний характер и требуют разработки различных алгоритмов, методов и структур данных при работе с геометрическими, текстовыми, мультимедийными и другими типами данных. Для повышения производительности обработки и извлечения данных в реляционных базах данных используются индексы и другие структуры данных.
Одной из наиболее широко применяемых структур данных является В-дерево. В-дерево обеспечивает высокую скорость выполнения запросов, связанных с типами данных и поисковыми предикатами, заданными SQL стандартом. Однако, для многих современных приложений необходима работа с типами данных и поисковыми предикатами, не заданными стандартом SQL. Примером таких типов данных могут служить геометрические типы данных (точки, многоугольники, кривые и т.д.), которые широко применяются в геоинформационных системах (ГИС). В ГИС также применяются не заданные SQL стандартом поисковые предикаты, такие как предикат пересечения геометрических объектов, предикат вхождения одного геометрического объекта в другой. Хотя для ГИС существуют различные стандарты, такие как Open GIS, структуры данных используемые СУБД для эффективной обработки поисковых запросов отличаются.
Существуют различные структуры данных, призванные обеспечить высокую скорость обработки поисковых запросов, касающихся пространственных данных, такие как разновидности grid-файлов, Quadtree и подобные ему деревья, R-дерево и подобные ему деревья. У каждой структуры данных есть свои преимущества и недостатки. R-дерево и его разновидности наиболее популярны по сравнению с другими перечисленными структурами данных, поскольку они могут эффективно работать во внешней памяти, а также могут хранить объекты, обладающие протяженностью, а не только точки. Основным недостатком R-дерева является то, что
охватывающие прямоугольники его узлов могут пересекаться. Сильная степень этого пересечения приводит к тому, что при поиске нужно сканировать много путей в дереве, что снижает скорость поиска. Способом уменьшения этого недостатка может быть новый алгоритм разделения узла для R-дерева, позволяющий уменьшить степень пересечения охватывающих прямоугольников узлов, тем самым увеличивая скорость поиска.
Наиболее распространенным типом данных является текстовый тип и задача повышения производительности поиска в текстовых массивах является одной из самых актуальных. В целом ряде практических задач таких как: очистка данных, смягчение запросов и проверка правописания не менее актуальным является нечеткий поиск в строковых массивах. При этом нечеткий поиск в СУБД не стандартизован, а самих мер похожести строк существует несколько. Среди различных мер похожести расстояние Левенштейна используется наиболее широко, поскольку оно применимо ко многим случаям. В настоящее время можно выделить две основные трудности при применении расстояния Левенштейна.
Высокая вычислительная сложность расстояния Левенштейна при большом объеме исходных строк.
Ограничения методов индексации для поиска по расстоянию Левенштейна в строковых массивах.
При этом для решения большинства практических задач, вычисление точного значения расстояния Левенштейна не обязательно, а достаточно его вычисления с пороговым значением.
Таким образом, вопросы повышения скорости поиска информации в базах данных являются актуальными и особенно для пространственных и текстовых данных.
Цель диссертационной работы состоит в повышении скорости поиска пространственных данных и разработке новых алгоритмов нечеткого поиска в массивах строк.
Для достижения поставленных целей необходимо решить следующие задачи.
-
Провести анализ алгоритмов построения R-дерева и его модификаций и разработать новый алгоритм разделения узла R-дерева, позволяющий улучшить качество результирующего R-дерева для пространственных данных.
-
Провести анализ существующих способов вычисления расстояния Левенштейна и разработать новый алгоритм вычисления расстояния Левенштейна с пороговым значением для поиска в текстовых данных.
-
Разработать индексную структуру на основе RD-дерева и k-грамм для поиска в наборах строк по расстоянию Левенштейна.
4. Реализовать разработанные алгоритмы, провести их экспериментальное исследование и внедрение.
Объектами исследований диссертационной работы являются базы данных, содержащие наборы пространственных данных и наборы строк.
Предметами исследований диссертационной работы являются алгоритмы и структуры данных, обеспечивающие высокую производительность при поиске многомерных данных и при нечетком поиске в наборах строк.
Методами исследования исследования диссертационной работы являются методы теории множеств, теории алгоритмов, линейной алгебры, математического анализа.
Научная новизна результатов работы заключается в следующем.
-
Разработан новый алгоритм разделения узла R-дерева для одномерного случая, основанный на использовании нового понятия «угловой разделяющей пары».
-
Разработано применение нового алгоритма разделения узла для R-дерева к многомерному случаю.
-
Разработан новый алгоритм вычисления расстояния Левенштейна с пороговым значением и математически доказана его корректность.
-
Разработана структура данных на основе RD-дерева и k-грамм для поиска в наборах строк по расстоянию Левенштейна.
-
Разработан алгоритм фильтрации сигнатур для структуры данных на основе RD-дерева и k-грамм, математически доказана его корректность.
Практическая значимость результатов диссертации заключается в следующем.
-
Новый алгоритм разделения узла R-дерева позволяет повысить скорость поиска пространственных данных.
-
Новый алгоритм вычисления расстояния Левенштейна с пороговым значением и предложенное применение RD-дерева к набору k-грамм индексируемой строки позволяют с большей скоростью решать задачи нечеткого поиска в наборах строк, что представляет практическую ценность при очистке данных, смягчении поисковых запросов и проверке правописания.
На защиту выносятся следующие основные результаты и положения:
1. новый алгоритм разделения узла R-дерева для одномерного случая, основанный на использовании нового понятия «угловой разделяющей пары»;
-
применение нового алгоритма разделения узла для R-дерева к многомерному случаю;
-
новый алгоритм вычисления расстояния Левенштейна с пороговым значением;
-
структура данных на основе RD-дерева и k-грамм для поиска в наборах строк по расстоянию Левенштейна;
-
алгоритм фильтрации сигнатур для структуры данных на основе RD-дерева и к-грамм.
Апробация работы Основные результаты диссертации докладывались на следующих конференциях:
Spring/Summer Young Researchers' Colloquium on Software Engineering (SYRCoSE) [1-3];
IADIS International Conference Applied Computing [4];
Международный научно-технический семинар в городе Алушта [5];
Научная сессия МИФИ [6].
Реализация результатов диссертации заключается в следующем.
-
Программная реализация предложенного алгоритма разделения узла R-дерева была включена в исходных код наиболее развитой СУБД с открытым исходным кодом PostgreSQL.
-
Программная реализация предложенного алгоритма вычисления расстояния Левенштейна с пороговым значением была включена в исходных код наиболее развитой СУБД с открытым исходным кодом PostgreSQL.
-
Разработанный алгоритм разделения узла для R-дерева был применен в Государственном астрономическом институте им. П. К. Штернберга для поиска астрономических объектов.
-
Разработанный алгоритм разделения узла для R-дерева, а также методы нечеткого поиска текста были применены в ЗАО «Геноаналитика» для построения генетической карты и поиске формулировок заболеваний.
Публикации
Всего по теме диссертации опубликовано 12 печатных работ [1-12] в том числе 5 статьи в журналах, рекомендованных ВАК РФ для публикации основных результатов работы [7-11].
Личный вклад автора
Все научные и практические результаты диссертации получены автором лично.
Структура и объем диссертации Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы из 115
Задача поиска пространственных данных
Под нечетким поиском в строковых массивах, подразумевается поиск в массиве строк тех, которые "похожи" на поисковую строку. "Схожесть" строк может определяться различным образом, в зависимости от природы данных и решаемой задачи. Были предложены различные функции, определяющие "похожесть" [47, 101], такие как расстояние Левенштейна [48], метрика Яро [49], косинусовая метрика на основе токенов [50, 51]. Предложенных мер, расстояние Левенштейна используется наиболее широко, поскольку оно применимо ко многим случаям. Нечеткий поиск в строковых массивах востребован в целом ряде практических задач, таких как: очистка данных [102], смягчение запросов и проверка правописания.
Задача очистки данных возникает в том случае, когда в одну базу данных (БД) загружаются данные из различных источников. При этом строки, полученные из разных источников и содержащие одну и ту же информацию, могут быть записаны разным способом и даже содержать ошибки. Поэтому при загрузке новых данных, может быть актуальным искать среди имеющегося набора строк те, которые похожи на добавляемую строку, чтобы избежать возможного дублирования.
Смягчение поискового запроса актуально в том случае, когда запрос пользователя к БД может содержать неточности. Это может быть связано с тем, что пользователь на момент составления запроса, ещё не знает точно, что именно он ищет. Когда такой запрос включает в себя условие на текстовое поле, то имеет смысл заменить строгое соответствие приблизительным. Использование такого подхода позволяет пользователю найти то, что он ищет, за меньшее число запросов.
При автоматической проверке правописания, если программа находит в тексте ошибку, то бывает целесообразно искать в базе данных похожее слово, которое пользователь мог иметь ввиду, и предлагать соответствующее исправление.
Основные результаты в направлении повышения эффективности нечеткого поиска в строковых массивах представлены в работах [50, 67, 103-107]. В большинстве работ используется идея k-грамм. к-грамма -это подстрока длины к исходной строки, которая используется в качестве сигнатуры. Предложенные методы основаны на индексных структурах, которые в свою очередь применяются к наборам к-грамм. ax a2 ... aL bt Щ ... b L
Расстояние Левенштейна между строками а и Ъ будем обозначать как levenshtein(a,b). Для расчета расстояния Левенштейна между строками может быть использован алгоритм выравнивания двух последовательностей [39, 61].
Пусть строки а = а\а2...ап и b = bi&2---&m имеют длины пит соответственно. Выравнивание происходит путем вставки в строки а и b пустых символов «-». После добавления символов «-» строка а — а\а2...ап становится а — a\a 2...a L, a b = b\b2...bm становится b = b\b\...b L. Выравнивание принято показывать в виде строк а и Ь , записанных одна под другой (см. рисунок 1.5).
Введем матрицу D размером п+1 на га+1. Определим элемент матрицы D следующим образом Dij = Ievenshtein(aia2...ai,bib2...bj), то есть элемент матрицы Dij определяется как расстояние Левенштейна между префиксами строк а и b длин і и j соответственно.
По определению, элемент Dn m равен расстоянию Левенштейна между строками а, Ь. Таким образом, расстояние Левенштейна может быть вычислено с помощью заполнения матрицы D. Пример заполнения матрицы D приведен на рисунке 1.6. Прямолинейная реализация заполнения матрицы D потребует 0(п т) времени и 0(п т) памяти. Алгоритм заполнения матрицы может быть легко оптимизирован в отношении объема требуемой памяти до 0(min{n, га}) за счет построчного или постолбцевого порядка заполнения матрицы, при котором нужно одновременно хранить в памяти значения матрицы D только в двух строках или столбцах соответственно. Однако, в этом случае сохраняется временная сложность 0(п га), которая может представлять существенную трудность в случаях, когда пит достаточно велики.
Заметим, что для решения задач, перечисленных выше, как правило, знать точное значение расстояния Левенштейна не обязательно. При очистке данных, коррекции опечаток и смягчении поисковых запросов задача состоит в том, чтобы найти в массиве строк те, которые похожи на заданную. Таким образом, если в качестве меры "похожести" применяется расстояние Левенштейна, то задача состоит в том, чтобы из массива строк выбрать те, для которых это расстояние не велико, и именно для этих строк необходимо знать его точное значение. Для тех строк, для которых значение расстояния Левенштейна велико, знать его точное значение не обязательно.
Таким образом, можно сформулировать задачу нахождения расстояния Левенштейна с пороговым значением к. Если расстояние Левенштейна между строками а и b не превышает А;, то необходимо узнать его точное значение. Если же расстояние Левенштейна превышает к, то достаточно только установления этого факта, точное значение расстояния знать не обязательно. Эта задача может быть представлена как нахождение значения функции levenshtein_threshold(a,b,k) (формула 1.10) которая равна расстоянию Левенштейна между строками а и Ь, если оно не превосходит к, и равна к +1 в противном случае.
Задача нахождения значения функции levenshtein_threshold(a, b, к) может быть решена с меньшей временной сложностью, чем нахождение значения функции levenshtein(a,b). Можно заполнять в матрице D только те элементы, которые отстоят от диагонали матрицы D не более чем на к. В самом деле, элементы, отстоящие от диагонали более чем на к имею значение гарантированно больше к и их использование в дальнейших расчетах не может дать в результате значение не превосходящее к [63]. Таким образом задача нахождения значения функции levenshtein_threshold(a, Ъ, к) может быть решена с временной сложностью 0(min(n,m) к). Пример матрицы D с пороговым значением 2 приведен на рисунке 1.7.
Анализ вариантов применения угловых разделяющих пар
Работа данного алгоритма проиллюстрирована на рисунке 2.13 для набора интервалов [0,5], [1, 7], [3,6], [3,8]. Вначале находится первая угловая разделяющая пара 5,0 (состояние 1 на рисунке 2.13), за это отвечают строки 3-11. Далее осуществляется поиск следующего значения s2./ и соответствующего sl.u (строки 13-27). Этот шаг отображен как состояние 2 на рисунке 2.13, откуда видно что граница s2J увеличилась, но при этом не потребовалось увеличение si.и. Соответственно, в строках 29-37 не находятся новые угловые разделяющие пары. Далее в строках 39-47 осуществляется переход к следующему значению s2.Z, таким образом находится угловая разделяющая пара 5,1 (состояние 3 на рисунке 2.13). После этого осуществляется поиск следующего значения 52 Л и соответствующего si.и (строки 13-27). В строках 29-37 находится промежуточная угловая разделяющая пара 6,1 (состояние 4 на рисунке 2.13). Далее в строках 39-47 осуществляется переход к следующему значению 52./, таким образом находится угловая разделяющая пара 7,3 (состояние 5 на рисунке 2.13). Далее снова в осуществляется поиск следующего значения 52.1 (строки 13-27), при это оказывается что текущее значение уже наибольшее (состояние 6 на рисунке 2.13). И в завершение в строках 39-47 осуществляется переход к последней найденной угловой разделяющей паре 8,3 (состояние 7 на рисунке 2.13).
Когда угловая разделяющая пара найдена, вызывается ConsiderSplit (алгоритм 11). ConsiderSplit принимает ограничивающие интервалы групп и максимальное число элементов, которое может быть размещено в группы, в соответствии с заданными ограничивающими интервалами, в качестве входных параметров. Максимальное число элементов, которые могут быть размещены в группах, определяется по индексам в отсортированных массивах, откуда извлекаются границы разделяющих пар. ConsiderSplit ищет разделения с наименьшей степенью пересечения групп, где минимальное число элементов в группе больше или равно га. Когда разделение с нулевым пересечением возможно, то ConsiderSplit выбирает разделение, где расстояние между ограничивающими интервалами групп наибольшее. Это свойство достигается за счёт того, что переменной overlap разрешается принимать отрицательные значения. Заметим, что если некоторые элементы могут быть размещены в обе группы, то ConsiderSplit рассматривает разделение, где распределение элементов по группам наиболее близко к равномерному. Алгоритм 11 ConsiderSplit Вход: Ограничивающие интервалы групп si и s2, числа nl и п2, которые представляют собой максимальные числа элементов, которые могут быть размещены в каждой из групп. Выход: Обновленная информация о том, какое оптимальное разбиение найдено на данный момент. і: overlap = (si.и — s2.l)/(s2.u — si./) 2: if nl m and n2 m and overlap best_overlap then 3: best_overlapl = overlap 4: best__Sl = Si 5: best_s2 = S2 6: best_nl 4= ПІ 7: best_n2 = n2 8: end if Алгоритм DoubleSortSplit (алгоритм 12) представляет собой алгоритм разделения в целом. На первом шаге он вызывает EnumerateCornerSplitPairs для того, чтобы найти угловую разделяющую пару с наименьшим пересечением. На втором шаге он распределяет элементы, которые могут быть однозначно распределены. После этого, остаток элементов сортируется по серединам их интервалов и распределяется таким образом, чтобы распределение интервалов между группами было наиболее равномерным. Поскольку сортировка - наиболее дорогая часть этого алгоритма, то его временная сложность - 0(п 1од(п)) (п - число интервалов). Алгоритм 12 DoubleSortSplit Вход: Переполненный узел
Выход: Два новых узла, в каждом из которых не менее т элементов і: Вызвать EnumerateSplitPairs для того, чтобы найти угловую разделяющую пару с наименьшим пересечением. 2: Распределить между группами те интервалы, которые могут быть размещены только в одну группу. 3: Отсортировать остальные элементы по серединам их интервалов. 4: Распределить первые к из этих элементов в первую группу, а остальные распределить во вторую группу, таким образом, чтобы распределение элементов между группами было наиболее равномерным среди всех возможных к. 2.4. Применение алгоритма разделения узла R-дерева к многомерному случаю
Предложенный алгоритм может быть применен и к многомерному случаю. Алгоритм MultidimensionalDoubleSortSplit (алгоритм 13) представляет собой такое применение. На первом шаге он перечисляет все угловые разделяющие пары вдоль всех осей и выбирает угловую разделяющую пару и соответствующую ось, которые имеют наименьшую степень пересечения. Если два или более разделения имеют одинаковую степень пересечения, то выбирается та ось, длина охватывающего интервала вдоль которой больше. Это стратегия делает МОП групп наиболее близкими к квадратам, что помогает при поиске. Учитывая это, если оказывается возможным разделение без пересечений охватывающих интервалов, рассмотрение между охватывающими интервалами не так важно. Поэтому переменной overlap в MulitdimensionalConsiderSplit (см. алгоритм 14) запрещено принимать отрицательные значения.
На втором шаге элементы, которые могут быть распределены однозначно, распределяются. После этого оставшиеся элементы сортируются в порядке разницы в приросте площади групп. В завершение среди возможных разделений выбирается то, у которого наименьшая степень пересечения между МОП групп.
Алгоритм 13 MultidimensionalDoubleSortSplit Вход: Массив е, состоящий из п записей Выход: Группы записей д\ и 2 1: Вызвать EnumerateSplitPairs для каждой оси для того, чтобы найти допустимую угловую разделяющую пару с наименьшей среди всех степенью пересечения. Использовать алгоритм MultidimensionalConsiderSplit вместо ConsiderSplit. 2: Распределить элементы, которые могут быть однозначно распределены только в одну группу в соответствии с найденной ранее угловой разделяющей парой. 3: Отсортировать элементы по разнице прироста площади МОП групп при присоединении элемента. 4: Распределить первые к отсортированных элементов в д\, а остальные распределить в #2, таким образом, чтобы степень пересечения МОП групп была наименьшей среди всех возможных к.
Алгоритм вычисления расстояния Левенштейна с пороговым значением
Пример прямолинейного применения RD-дерева к наборам к-грамм представлен на рисунке 3.6. Здесь как внутренние, так и листовые узлы содержат наборы k-грамм. Записи во внутренних узлах содержат все к-граммы, содержащиеся в соответствующих поддеревьях.
Для задачи поиска по расстоянию Левенштейна наборы k-грамм в листовых страницах не так полезны, как исходные строки. Исходные строки занимают меньше места, проверка на выполнение поискового предиката с использованием исходной строки может быть точной, в то время как для набора k-грамм возможна только оценка. Пример RD-дерева с исходными строками в листовых страницах представлен на рисунке 3.7.
При к 3 общее множество k-грамм велико по сравнению с разумным размером записи в узле дерева. В таких случаях записи во внутренних узлах целесообразно заменить на сигнатуры. Сигнатура представляет собой битовый вектор, число бит в котором меньше, чем мощность множества возможных k-грамм. Это означает, что одному биту может соответствовать больше, чем одна к-грамма. Бит при этом устанавливается в 1, если присутствует хотя бы одна к-грамма из соответствующих данному биту. Таким образом, если некоторый бит сигнатуры равен 0 то это означает, что во всем поддереве нет ни одной из соответствующих этому биту k-грамм. Таким образом, сигнатура представляет собой фильтр Блума [НО], т.е. компактное представление множества, допускающее ложноположителыюе срабатывание, но не допускающее ложноотрицателыюе. Для отображения k-грамм на биты сигнатуры использовалась хэш-функция сгс32 [111]. В таком представлении, RD-дерево, за исключением листьев, становится очень похожим на S-дерево [72]. С учетом того, что сигнатуры соответствуют множествам к-грамм, предлагаемая индексная структура похожа на реализацию GiST индекса в модуле pg_trgm СУБД PostgreSQL, за исключением того что в модуле pg_trgm в листах хранятся множества триграм [112]. Пример такого дерева приведен на рисунке 3.8.
Ускорение поиска по такому дереву осуществляется за счет пропуска сканирования тех поддеревьев, сигнатура которых исключает возможность нахождения в поддереве строки, удовлетворяющей поисковому предикату.
Задача алгоритма фильтрации сигнатур состоит в том, чтобы по сигнатуре определить, может ли в соответствующем поддереве находится строка, удовлетворяющая поисковому запросу. При поиске те поддеревья, для которых результат работы этого алгоритма будет отрицательным, будут пропущены, таким образом достигается ускорение поиска. Для каждой k-граммы поисковой строки можно проверить наличие соответствующего бита в сигнатуре. Если бит равен 0, то это гарантирует, что данная к-грамма не присутствует ни в одной строке соответствующего поддерева. Если бит равен 1 то k-грамма может присутствовать в строке, находящейся в соответствующем поддереве. Таким образом, посчитав количество к-грамм, для которых бит в сигнатуре равен 1, можно получить ограничение сверху возможного числа общих k-грамм между поисковой строкой и произвольной строкой поддерева. C(sh s2,l,k) = \si\ + \s2\ + k-l-l-k (3.30)
В то же время у нас есть условие (3.30) на минимальное число общих k-грамм между поисковой строкой и строкой, удовлетворяющей поисковому запросу. Если эти два ограничения несовместимы (верхняя граница оказывается меньше нижней), то это значит, что в поддереве нет строк, удовлетворяющих поисковому запросу, и его сканирование можно пропустить.
Приведенной выше способ фильтрации сигнатур использует только количество k-грамм, для которых биты в сигнатуре равны 1. В то же время использование информации о вхождении конкретных k-грамм в сигнатуру может дать более точный результат, таким образом, обеспечивая более быстрый поиск. Пусть si и s2 - некоторые строки. Если строку si разбить на п непересекающихся фрагментов и т из этих фрагментов не будет присутствовать в s2, то это означает что расстояние Левенштейна между строками si и s2 составляет не менее т [113, 114]. Если применить эту утверждение к k-граммам, то его можно сформулировать следующим образом. Если в строке si есть т непересекающихся k-грамм, не входящих в s2, то расстояние Левенштейна между строками si и s2 составляет не менее т. Применим это утверждение к фильтрации сигнатур. Если в поисковой строке s есть т непересекающихся k-грамм, для которых бит блок в сигнатуре равен 0, то минимальное расстояние Левенштейна между s и строкой поддерева - т. Таким образом, нужно найти наибольшее число непересекающихся k-грамм поисковой строки, для которых бит в сигнатуре равен 0. Это делает алгоритм 16, его работа представлена на рисунке 3.9. Этот алгоритм последовательно рассматривает k-граммы строки s. Если бит в сигнатуре для рассматриваемой k-граммы равен 0, то счетчик к-грамм, которые нужно найти, уменьшается на единицу, а следующие к—1 k-граммы пропускаются.
Эксперименты для одномерного случая на синтетических наборах данных
Эксперименты проводились как на реальных, так и на синтетических наборах данных. Для одномерного случая, синтетический набор данных содержит 106 случайно сгенерированных интервалов. Размер интервала генерировался как случайная величина, подчиняющаяся закону iV(0,1)1. Под степенью пересечения подразумевается среднее число интервалов, которым будет принадлежать случайно взятая точка из диапазона значений. Степень пересечения интервалов варьировалась экспоненциально от 1 до 104. Закон распределения середин интервалов зависит от типа набора данных следующим образом.
Равномерный набор данных. Середины интервалов распределены по закону R(0; I)2. Нормальный набор данных. Середины интервалов распределены по закону N(0,1). Равномерный набор данных с кластерами. Вначале генерируется 500 центров кластеров, которые распределены по закону i?(0,1). После этого для каждого кластера генерируется 2000 середин интервалов, сдвиг которых относительно центра кластера распределен по закону Д(0;6 10-4).
Нормальный набор данных с кластерами. Вначале генерируется 500 центров кластеров, которые распределены по закону Л/"(0,1)- После этого для каждого кластера генерируется 2000 середин интервалов, 1 Нормальный закон распределений с математически ожиданием 0 и среднеквадратичным отклонением 1 2 Равномерный закон распределения на интервале от 0 до 1 сдвиг которых относительно центра кластера распределен по закону iV(0;6 l(T4). Синтетические наборы данных для многомерных случаев были аналогичными, только вместо скалярных случайных величин, которые генерировались в наборах данных приведенных выше, генерировались векторы, компоненты которых имели тоже распределение, что и соответствующие величины в одномерном случае. Таким образом, эти наборы данных содержали n-мерные прямоугольники.
При проведении экспериментов также использовались следующие реальные наборы данных. База данных Geonames, 7603617 точек (GN)3 Дороги Калифорнии, 2,249,727 МОП улиц Калифорнии (CAR)4 Сеть каналов Tiger Streams, содержащая МОП 194,971 каналов штатов США Айова, Канзас, Миссури и Небраска (TS) 5
Эксперименты показывают, что все алгоритмы, основанные на сортировке, работают почти одинаково. Поэтому в результатах представлен только один алгоритм, основанный на сортировке по середине интервала. Таким образом в экспериментах использовались следующие алгоритмы:
Для того чтобы сравнить скорость поиска, с использованием индексных структур, полученных с помощью различных алгоритмов разделения узла, измерялось число доступа к узлам при выполнении запроса. Для проведения экспериментов было сгенерировано 1000 маленьких интервалов размером 10 5, и измерялось число доступов к узлам дерева для извлечения всех интервалов из набора данных, которые пересекаются с данным интервалом. На рисунке 4.1 представлено сравнение среднего числа доступов к узлам. Для более наглядного сравнения представлено не абсолютное значение, а отношения значения для конкретного алгоритма к среднему значению по всем алгоритмам. Измерения были проделаны для 4-х наборов данных, описанных ранее, с различными уровнями пересечения. На рисунке 4.2 приведено сравнение времени создания дерева. Данные представлены тем же способом, что и число доступов к узлам: отношение времени создания для конкретного алгоритма к среднему времени создания. На графиках показаны доверительные интервалы для представленных на них значений. Они были получены путем многократного повторения экспериментов и оценки методом За.
Можно видеть, что в тех случаях, когда доверительные интервалы для числа доступов к узлам при поиске в деревьях, построенных с применением различных алгоритмов разделения узла, не пересекаются, превосходство показывает разработанный алгоритм (число доступов к узлам меньше). При высокой степени пересечения данных наблюдается существенное превосходство разработанного алгоритма, до 1,5 раз в сравнении с алгоритмом, основанном на сортировке по середине интервала, и до 2 раз по сравнению с Гуттмановским квадратичным алгоритмом. Можно видеть, что время создания дерева при использовании разработанного
