Для снятия этого ограничения предлагается схема хранения дан-
ных, основанная на основе аппроксимации бассейна аттрактора по-
средством многомерныхгеометрическихпримитивов и хранения этих
элементов в многомерной индексной структуре. Остановимся подроб-
ней на данном способе построения аттрактора и процедуре поиска
последовательности.
Реализация хаотического процессора.
Пусть имеется последова-
тельность
{
X
i
}
и ее идентификатор
I
, которые необходимо запомнить.
Рассмотрим
{
X
i
}
как аттрактор некоторого отображения
F
и постро-
им бассейн этого аттрактора. Для этого выполним процедуру разби-
ения последовательности
{
X
i
}
на подпоследовательности и ограни-
чим каждую из нихсоответствующим
n
-мерным параллелепипедом
— МОП. Тогда полученная последовательность параллелепипедов и
будет являться бассейном нашего аттрактора.
Каждому МОП поставим в соответствие следующие числа:
•
идентификатор всей последовательности
{
X
i
}
;
•
идентификатор элемента
X
i
в исходной последовательности, ко-
торый является первым элементом в
{
Q
i
}
;
•
точку следующей подпоследовательности, наиболее удаленную
от границ соответствующего МОП;
•
признак конца последовательности.
Получившийся набор параллелепипедов и связанныхс ними дан-
ныхсохраняется в структуре многомерного индекса — в
R
-дереве с
приоритетами [12]. Такой способ организации позволяет сохранять
n
-
мерные параллелепипеды (регионы) и эффективно определять принад-
лежность произвольной точки одному или нескольким сохраненным
регионам.
Таким образом, элементы последовательности
{
X
i
}
разбиты на
ограничивающие параллелепипеды и сохранена их упорядоченная со-
вокупность в многомерном дереве, которое в силу своего построения
позволяет эффективно отвечать на поисковые запросы о принадлеж-
ности произвольной точки пространства одному или нескольким па-
раллелепипедам. По оценкам, приведенным в работе [12], время на
обработку поискового запроса составляет
O
((
N/B
)
1
−
1
/n
+
T/B
)
, где
N
— число параллелепипедов размерности
n
, сохраненных в дереве,
B
— размер дискового блока,
T
— число полученныхответов на за-
прос. В работе [12] приведены теоретические и эмпирические оценки
сложности выполнения операций добавления и удаления элементов
дерева, которые превосходят на сегодняшний день показатели анало-
гичныхмногомерныхиндексныхструктур.
Хаотический процессор реализуется как надстройка над индексной
структурой. Способ построения описанной индексной структуры ли-
нейно масштабируется для сохранения набора последовательностей.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2007. № 2 113
