Mass updates on multidimensional data.pdf Для эффективной работы с информацией разработаны разнообразные структурыданных. Одна из самых распространённых из них - дерево. Широко известны квад-родеревья [1], кд-деревья [2], обобщения дерева отрезков [3] и дерева Фенвика [4].Существующие структуры данных для работы с многомерными массивами данныхпозволяют эффективно получать статистическую информацию и изменять отдельныеэлементы.Цель настоящей работы заключается в том, чтобы исследовать возможность вы-полнения массовых обновлений - единообразного изменения областей данных. Ни од-на из вышеперечисленных структур данных в чистом виде не предоставляет подобнуюфункциональность. Подробнее с возникающими проблемами можно ознакомиться в [5].Рассмотрим d-мерное пространство Zd. Пусть x, y Е Zd; будем говорить, что x ^ у,если Xfc ^ yfc для всех k Е {1, 2 , . . . , d } . Для любого c Е Z будем обозначать c == (c, c , . . . , c) Е Zd; для любых x, у Е Zd, x ^ у, положим P x y = [xi..yi] х [x2..y2] х . . . хРассмотрим абелеву группу (G, +) и отображение A : P1 n ^ G, n Е Z. Можнотрактовать A как многомерный массив с множеством индексов Pi,n и множествомдопустимых значений ячеек G.Массовый запрос определим следующим образом: get (A, P) = Е A(x) .xePМассовое обновление: update(A, P, v) = A' : P1 n ^ G, гдеA ' ( x ) = / A ( x ) + v, x Е P ,A ( x ) = \ A(x), x ЕP.Определим оператор Dj следующим образом:(DjA)(x) = A ( x i , . . . , x j , . . . ,xd) - A ( x i , . . . ,xj - 1 , . . . ,xd),полагая A(x) = 0 при x Е P1,n. Заменим элементы исходного массива A(x) на линейныеdмногочлены от d переменных C(x)(z) = (D1D2 DdA)(x) П (zj - xj ).j = iУтверждение 1. Для области вида P1,z массовый запрос сводится к массовомузапросу на массиве C и подстановке переменных:get(A,Pi , z ) = get(C,Pi , z ) ( z ).Утверждение 2. Для области вида P x n массовое обновление равносильно еди-ничному обновлению в новом массиве:dupdate(A, Px,n, v) ^ update(C, Px,x, v П (z - xi )).i = iОслабленным назовем массовый запрос или обновление, для которого применимоутверждение 1 или 2 соответственно.Утверждение 3. Произвольные массовые обновления и запросы выражаются неболее чем через 2d ослабленных.Утверждения 1-3 позволяют свести задачу с массовыми обновлениями к хорошоизученной задаче с единичными обновлениями. Последнюю можно решать с использо-ванием любых существующих структур данных. Это свойство позволяет делать выбороптимальной структуры данных для каждой задачи отдельно.При использовании популярных структур данных асимптотическая оценка на вы-полнение массовых операций составляет O(log n). При малой размерности простран-ства эта оценка позволяет говорить об эффективности предлагаемого метода сведениязадачи с массовыми обновлениями к задаче с единичными обновлениями. Свободавыбора структуры данных свидетельствует о гибкости метода.Отметим, что не все задачи выполнения массовых операций на многомерных мас-сивах данных можно сформулировать в терминах, использованных в данной работе.Вопрос об обобщении подхода на более широкие классы задач остаётся открытым.

Скачать электронную версию публикации