Содержание
- 2. Точечные и пространственные данные Два вида данных: Точечные (координатные) данные: Объекты (в бд) – кортежи из
- 3. Точечные и пространственные данные Методы доступа к многомерным данным: Доступ к точечным данным (PAM – Point
- 4. Точечные данные Свойства точечного пространства: Фиксированное число (k) измерений, у каждого измерения свой собственный домен значений
- 5. Точечные данные Виды запросов: Запросы по точному совпадению (exact-match queries): все координаты (атрибуты) зафиксированы в запросе;
- 6. Отображение в одномерное пространство Зачем отображать в одномерное пространство? Одномерное пр-во проще и для него есть
- 7. Отображение в одномерное пространство Более симметричное решение: перетасовать двоичные представления координат. Пусть: k – размерность пространства
- 8. Отображение в одномерное пространство Пример: Z-порядок на плоскости (k=2, d=3) Большинство переходов (от точки к точке)
- 9. Отображение в одномерное пространство Операции с данными в Z-порядке: Поиск по точному совпадению, вставка, удаление и
- 10. Отображение в одномерное пространство Замечания: Проверка расположения SR и QR относительно друг друга не требует доступа
- 11. Отображение в одномерное пространство Алгоритм: RangeSearch(QR, SR, level) --- В начале SR – всё k-мерное пространство,
- 12. Отображение в одномерное пространство Пример: k = 2, d = 3, QR = Точки: {(0,3), (1,
- 13. Отображение в одномерное пространство Процесс нахождения S-регионов, удовлетворяющих пространственному запросу (пример работы алгоритма RangeSearch): (вне) (внутри)
- 14. Отображение в одномерное пространство Несколько замечаний о пространственных запросах: Точки внутри каждого SR расположены в Z-порядке
- 15. Сеточная1 организация В отличии от предыдущей структуры: явно задаваемое разбиение пространства Свойства: Динамичность: гибкие вставка и
- 16. Сеточная организация Сеточное разбиение: Каждое измерение разбивается на интервалы, независимые друг от друга Разбиение всегда происходит
- 17. Сеточная организация Объединение нескольких блоков на одной странице: Блоки, образующие выпуклые (в математическом смысле) области в
- 18. Сеточная организация Запрос по точному совпадению: С помощью шкал найти точное расположение нужной записи в (k-мерном)
- 19. Сеточная организация Пространственный запрос: Интервалы для каждого измерения задают гипер-прямоугольную область Какие-то точки, расположенные рядом с
- 20. Сеточная организация Операция вставки: Найти нужную страницу (как в запросе по точному совпадению) Далее возможны три
- 21. Сеточная организация Операция вставки (продолжение): Страница переполняется, при этом страница описывает только один блок: Пространство должно
- 22. Сеточная организация Пример: Последовательность вставок, емкость страницы – 3 записи (точки)
- 23. Сеточная организация Операция удаления: Если страница стала пустой или коэффициент заполнения страницы стал меньше заданного граничного
- 24. K-d-деревья K-мерные (dimensional) деревья: Бинарные деревья Разбиение пространства зависит от точечных данных Рекурсивное разбиение вдоль одного
- 25. K-d-деревья Создание сбалансированного k-d-дерева на основе заданного набора точек (пример на следующем слайде): Отсортировать точки и
- 26. K-d-деревья Виды k-d-деревьев (аналогично разнице между B-деревом и B+-деревом): Однородные: во внутренних узлах хранятся дискриминаторные точки
- 27. K-d-деревья Поиск по (неоднородному) k-d-дереву: а) Запрос по точному совпадению: Двигаться вниз от корневого узла: на
- 28. K-d-деревья в) Пространственный запрос: На i-ом уровне: если нижняя и верхняя границы области значений для i
- 29. K-d-деревья K-d-деревья для представления данных во внешней памяти: Сгруппировать соседние листы в страницы с данными Сгруппировать
- 30. Тетрарные1 деревья Структура для двухмерного пространства (графические изображения, карты и т.д.) Примечание: аналогичная древовидная структура но
- 31. Тетрарные деревья Пример: Однородное точечное тетрарное дерево Обозначения: ЮЗ – юго-запад, ЮВ – юго-восток, НЗ –
- 32. Тетрарные деревья б) Матричное тетрарное дерево (MX-quadtree; matrix -> MX): Разбиение пространства происходит не по множеству
- 33. Тетрарные деревья Пример: Матричное тетрарное дерево
- 34. K-D-B-деревья K-d- и тетрарные деревья предназначены (преимущественно) для представления данных в оперативной памяти K-D-B-дерево [4] –
- 35. K-D-B-деревья Схематический вид K-D-B-дерева:
- 36. K-D-B-деревья Поиск по K-D-B-дереву: Запросы по точному совпадению: движение по дереву до листа, содержащим точки в
- 37. K-D-B-деревья Удаление точки: Найти и удалить из соответствующего листа Незаполненность: коэффициент заполнения страницы меньше определенного значения
- 38. Другие типы многомерных деревьев TV-дерево1 [5]: Специально предназначено для представления точечных данных в пространствах очень большой
- 39. Другие типы многомерных деревьев M-дерево [6]: Предназначено для объектов в метрическом пространстве: Функция расстояния (метрика) должна
- 40. Упражнения Рассмотрим дискретное целочисленное трехмерное пр-во - (0..7, 0..7, 0..7). Отсортируйте следующие точки в Z-порядке: (4,
- 42. Скачать презентацию