Методы пространственного индексирования в СУБД тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Мартынов, Максим Геннадьевич

• Мартынов, Максим Геннадьевич
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Мартынов, Максим Геннадьевич

1 Введение

2 Пространственные методы доступа

2.1 Области применения.

2.2 Типы хранимых данных

2.3 Пространственные запросы.

2.4 Методы индексирования

2.4.1 Методы индексирования точечных объектов.

2.4.2 Методы индексирования протяженных объектов

2.4.3 Пространственные деревья.

2.5 Я-деревья.

3 Улучшения алгоритмов обработки Я-дерева

3.1 Локальные координаты.

3.2 Модификация алгоритма динамического удаления и вставки

3.3 Временный локальный клеточный индекс.

4 Пространственное соединение с использованием II-деревьев 37 4.1 Комбинированный алгоритм пространственного соединения

4.1.1 Алгоритм пространственного соединения, использующий свойство асимметрии чтения страниц.

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

4.1.3 Комбинированный алгоритм.

4.2 Клеточная эвристика.

4.3 Использование ориентированных многоугольников.

5 Использование алгоритмов пространственных методов для индексирования текстов

5.1 Индекс для инвертированных списков.

5.2 Алгоритм обработки инвертированных списков.

5.3 Оценка выигрыша в производительности.

Введение диссертации (часть автореферата) на тему «Методы пространственного индексирования в СУБД»

Пространственные методы доступа [5, 48, 1] являются основой геоинформационных систем, а также широко применяются в других областях, таких как временные базы данных [8], компьютерное зрение [27], базы знаний, САПР [7] и др., требующих многоатрибутного индексирования [48]. Важным требованием к таким системам является необходимость эффективной обработки очень больших объемов данных, имеющих пространственную природу, что делает необходимым использование специальных методов доступа к данным в таких системах.

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

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

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

Хранение линейных индексов по каждому атрибуту в отдельности также не является решением проблемы [5], так как при выполнении многоатрибутного запроса [48] в такой системе необходимо сначала выполнить вспомогательные запросы по каждому атрибуту для получения множеств объектов, удовлетворяющих ограничениям основного запроса по соответствующим атрибутам, а затем выполнить пересечение полученных множеств. Результирующие множества промежуточных запросов обычно содержат намного больше элементов, чем результирующее множество основного запроса, что и является причиной неэффективности данного метода.

Все это привело к созданию специальных методов индексирования для пространственных данных [5, 48, 1], сущность которых состоит в том, что объекты, близкие в исходном пространстве, хранятся вместе во вторичной памяти. Это и позволяет быстро производить поиск.

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

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

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

Наиболее известными структурами такого типа являются различные модификации 11-деревьев [13, 59, 36], а также С-деревья [35]. Эти методы основаны на аппроксимации реальных пространственных объектов ограничивающими объектами: прямоугольниками со сторонами параллельными осям координат или произвольными выпуклыми многоугольниками соответственно.

В данной работе рассматривается более узкий класс таких методов, в которых не используется техника дублирования данных, применяемая в 11+-деревьях [59], так как требуются большие вычислительные затраты на модификацию дерева при сильном разбросе максимальных размеров пространственных объектов [48].

Как и в одномерном случае над пространственными деревьями выполняются операции вставки и удаления объектов, а также различные виды запросов: диапазонные, точечные и соединения (см. раздел 2.3). Однако, в отличие от В-деревьев, алгоритм построения пространственного дерева недетерминирован, что дает возможность для оптимизации [13]. Но получение оптимального варианта алгоритма не представляется возможным, поэтому реально применяются различные эвристические методы, эффективность использования которых проверяется проведением большого числа экспериментов с различными исходными данными.

Наиболее важным видом запросов, выполняемых над пространственными деревьями, является пространственное соединение [22]. Примером такого запроса может служить нахождение всех городов, находящихся на реках, при наличии пространственных индексов городов и рек некоторого района. Выполнение таких запросов является наиболее трудоемкой операцией с вычислительной точки зрения. Это привело к созданию достаточно сложных методов выполнения пространственных соединений [34, 22, 21, 47, 2], использующих для оптимизации различные особенности обрабатываемых данных и соединяемых индексов.

Диссертация состоит из б глав.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Мартынов, Максим Геннадьевич

6 Заключение

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

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

2. Предложена модификация алгоритма динамического удаления и вставки И*-дерева, улучшающая пространственную структуру индекса.

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

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

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

6. Для внутренних и внешних аппроксимаций пространственных объектов и Т11*-дерева, применяемых в алгоритмах пространственного соединения, предложено использовать ориентированные многоугольники, дающие достаточно точное пространственное описание объекта при небольших затратах памяти. Кроме того, предложен быстрый способ тестирования ориентированных многоугольников на пересечение.

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

Для предложенных новых алгоритмов и модификаций существующих методов получены аналитические оценки и проведены численные эксперименты, выявляющие условия, при которых данные методы дают улучшение производительности. Реализация системы сравнения прототипов методов индексирования выполнена на языке программирования С в контексте системы хранения [28].

Список литературы диссертационного исследования кандидат физико-математических наук Мартынов, Максим Геннадьевич, 1998 год

1. M.Г. Мартынов. Пространственные методы доступа. Программирование. 1998, 3. С.59-69.

2. М. Martynov. Variations of R-tree structure for indexing of spatial objects. In Proc. of the Intnl. Workshop on Advances in Databases and Information Systems ADBIS'94, pages 217-221, Moscow, May 23-26 1994.

3. M. Martynov. Spatial joins and R-trees. In Proc. of the Second Intnl. Workshop on Advances in Databases and Information Systems ADBIS'95, pages 295-304, London etc., 1996. Springer-Verlag.

4. M. Martynov and B. Novikov. An indexing algorithm for text retrieval. In Proc. of the Third Intnl. Workshop on Advances in Databases and Information Systems ADBIS'96, pages 171-175, Moscow, Sept. 10-13 1996. MEPhl.

5. Б.А. Новиков. Системы хранения баз данных и знаний. Программирование. 1993, 2. С.3-30.

6. А.Н. Ширяев. Вероятность. М.: Наука., 1989, 640 С.

7. A. Guttman. New features for relational database systems to support CAD applications. PhD thesis, pages 287-296, 1984.

8. К. K. Al-Taha and R. Barrera. Temporal data and GIS: An overview. In Proceedings of GIS/LIS ;90, Nov. 1990.

9. K. K. Al-Taha and A. Frank. Temporal GIS Keeps Data Current. GIS-World, pages 382-388, Oct. 1991.

10. K. M. S. Allen, S. W. Green, and E. B. W. Zubrow. Interpreting Space: GIS and Archaeology. Taylor and Francis, London, 1990.

11. M. Armstrong. Temporality in spatial databases. In Proceedings of GIS/LIS ;88, pages 880-889, 1988.

12. D. A. Beckley, M. W. Evans, and V. K. Raman. Multikey retrieval from K-d trees and quad-trees, pages 291-301, Austin, TX, May 1985. ACM.

13. N. Beekmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 322331, Atlantic City, NJ, 1990.

14. A. Belussi and C. Faloutsos. Estimating the selectivity of spatial queries using the 'correlation' fractal dimension. VLDB, pages 299-310, 1995.

15. S. Berchtold, C. Böhm, B. Braunmüller, D. Keim, and H.-P. Kriegel. Fast parallel similarity search in multimedia databases. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 1-12, 1997.

16. S. Berchtold, C. Böhm, and H.-P. Kriegel. Improving the query performance of high-dimensional index structures by bulk-load operations. Proc. 6th Int. Conf. on Advances in Database Technology, pages 216-230, 1998.

17. S. Berchtold, C. Böhm, and H.-P. Kriegel. The pyramid-technique: Towards breaking the curse of dimensionality. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 142-153, 1998.

18. S. Berchtold, B. Ertl, D. Keim, H.-P. Kriegel, and T. Seidl. Fast nearest neighbor search in high-dimensional space. Proc. 14 Int. Conf. on Data Engineering, pages 209-218, 1998.

19. S. Berchtold, D. A. Keim, and H.-P. Kriegel. The X-tree: an index structure for high-dimensional data. VLDB, pages 28-39, 1996.

20. T. Brinkhoff, H.-P. Kriegel, R. Schneider, and B. Seeger. Multistep processing of spatial joins. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 197-208, 1994.

21. T. Brinkhoff, H.-P. Kriegel, and B. Seeger. Efficient processing of spatial joins using R-trees. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 237-246, 1993.

22. T. Brinkhoff, H.-P. Kriegel, and B. Seeger. Parallel processing of spatial joins using R-trees. In Proc. 12th Int. Conf. on Data Engineering, 1996.

23. E. Brown, J. Callan, W. Croft, and J. Moss. Supporting full-text information retrieval with a persistent object store. In Proc. Intnl. Conf. on EDBT., 1994.

24. D. Comer. The ubiquitous B-tree. Computing Surveys, 11 (2): 121-138, 1979.

25. W. Croft and L. Smith. A loosely-coupled integration of a text retrieval system and an object-oriented database system. In 15th Annu. Int. ACM SIGIR Conf. Res. and Dev. Inf. Retriev., SIGIR Forum, pages 223-232, Oct. 1991.

26. D. Ballard and C. Brown. Computer vision. Prentice Hall, 1982.

27. H. Dombrowska, I. Kaprizkina, and B. Novikov. Representation of the SYNTHESIS data structures in the object store. In Proc. of the workshop on advances in databases and information systems ADBIS'93, pages 60-68, Moscow, May 22-24 1993.

28. M. Stonebraker et al. Application of abstract data types and abstract indices to CAD data bases. In ACM-IEEE Data Base Week Proceedings, San Jose, CA, May 1983. ACM.

29. C. Faloutsos, H.J. Jagadish and Y. Manolopoulos. Analysis of the n-dimensional quadtree decomposition for arbitrary hyperectangles. TKDE, 9(3):373-383, 1997.

30. C. Faloutsos and S. Christodoulakis. Signature files: an access method for documents and its analytical performance evaluation. ACM Trans, on Database Systems, 4(2):267-288, 1984.

31. C. Faloutsos, T. Sellis, and N. Roussopoulos. Analysis of object oriented spatial access methods. In U. Dayal and I. Traiger, editors, Proceedings of the ACM SIGMOD Annual Conference, pages 426-439, San Francisco, CA, May 1987. ACM, ACM Press.

32. D. Greene. An implementation and performance analysis of spatial data access method. Proc. of 5th Int. Conf. on Data Eng., pages 606-615, 1989.

33. O. Guenther. Efficient computation of spatial joins. In The Ninth IEEE International Conference on Data Engineering, Vienna, Austria, Apr. 1993.

34. O. Günter and H. Noltemeier. Spatial database indices for large extended objects. In Proc. 7th Int. Conf. on Data Eng., pages 520-526, Cobe, Japan, 1991.

35. A. Guttman. R-trees: a dynamic index structure for spatial searching. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 47-57, 1984.

36. A. Guttman. R-trees: A dynamic index structure for spatial searching. In B. Yormack, editor, Proceedings of the ACM SIGMOD '94-, pages 47-57, Boston, MA, June 1984. ACM.

37. N. W. J. Hazelton. Time in GIS. In The Monash University GIS Seminar Series, Oct. 1992.

38. G. Hjaltason and H. Samet. Incremental distance join algorithms for spatial databases. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 237-248, 1998.

39. G. Hjaltason, H. Samet, and Y. Sussmann. Speeding up bulk-loading of quadtrees. Proceedings of the 5th International ACM Workshop on Advances in GIS, pages 50-53, 1997.

40. E. G. Hoel and H. Samet. A qualitative comparison study of data structures for large line segment databases, volume 21, pages 205-214, San Diego, California, June 1992. ACM, Acm Press.

41. I. Kamel and C. Faloutsos. Hilbert R-tree: an improved R-tree using fractals. VLDB, 1994.

42. I. Kamel and C. Fauloutsos. Parallel R-trees. In Proc. ACM SIGMOD Int. Conf. on Management of Data, volume 21:2 of SIGMOD Record, pages 195-204, San Diego, Calif., 1992.

43. A. Kent, R. Sacks-Davies, and K. Ramamohanarao. A superimposed coding scheme based on multiple block descriptor files for indexing very large databases. In Proc. 14 conf. VLDB, pages 351-359, 1988.

44. G. Lapalme, J. M. Rousseau, S. Chapleau, M. Cormier, P. Cossette, and S. Roy. GEOROUTE A geographic information system for transportation applications, cacm, 35(1) :80—88, Jan. 1992.

45. M.-L. Lo and C. Ravishankar. Spatial join using seeded trees. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 209-220, 1994.

46. D. Lomet. A review of recent work on multi-attribute access methods. ACM SIGMOD Record, 21(3):56-63, 1992.

47. D. Lomet and B. Salzberg. The hB-tree: a multiattribute indexing method with good guaranteed performance. ACM TODS, 15(4):625-658, 1990.

48. B. Mandelbrot. Fractal Geometry of Nature. W.H. Freeman, New York, 1977.

49. J. Nievergelt, H. Hinterberger, and K. C. Sevcik. The grid file: An adaptable, symmetric multikey file structure. ACM Trans, on Database Systems, 9(1):38-71, Mar. 1984.

50. B. Novikov. Towards a realistic model of indices in object bases. In Proc. of the Second Intnl. Workshop on Advances in Databases and1.formation Systems ADBIS'95, pages 153-159, Moscow, June 27-30 1995. Phasis.

51. J. A. Orenstein and F. A. Manola. PROBE spatial data modeling and query processing in an image database application. 14(5):611—629, May 1988.

52. J. M. Patel and D. J. DeWitt. Partition based spatial-merge join. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 259-270, 1996.

53. J. Robinson. The k-d-B-tree: a search structure for large multidimensional dynamic indexes. Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 10-18, 1981.

54. B. Salzberg. On indexing spatial and temporal data. Information Systems, 19(6) :447-465, 1994.

55. B. Salzberg and D. Lomet. Spatial database access methods. 20(3):5—15, Sept. 1991.

56. J. Sander, M. Ester, H.-P. Kriegel, and X. Xu. Density-based clustering in spatial databases: The algorithm GDBSCAN and its applications. Data Mining and Knowledge Discovery, 2(2), 1998.

57. T. Sellis, N. Roussopoulos, and C. Faloustos. The R+ -tree: A dynamic index for multi-dimensional objects. In Very Large Data Bases, pages 507-518, Brighton, England, 1987.

58. F. Wang. Relational-linear quadtree approach for two-dimensional spatial representation and manipulation. 3(1)¡118—122, Mar. 1991.

59. T. Ylonen. An algorith for full text indexing. Master's thesis, Helsinki University of Technology, 1992.

60. J. Zobel, A. Moffat, and R. Sacks-Davis. Efficient indexing technique for full-text database systems. In Proc. 18th Intnl. Conf. on VLDB. Vancouver, British Columbia, Canada, 1992., pages 352-362, 1992.

61. J. Zobel, A. Moffat, and R. Sacks-Davis. Searching large lexicons for partially specified terms using compressed inverted files. In Proc. 19th Intnl. Conf. on VLDB. Dublin, Ireland, 1993., pages 290-301, 1992.