Методы, алгоритмы и программные средства повышения скорости поиска в базах данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Коротков, Александр Евгеньевич

• Коротков, Александр Евгеньевич
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Коротков, Александр Евгеньевич

Введение

Глава 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. Исходный код приведен в приложении Б.

Список литературы диссертационного исследования кандидат технических наук Коротков, Александр Евгеньевич, 2012 год

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.