Если оказывается, что при сохранении двухразныхпоследователь-
ностей набор ограничивающихрегионов совпадает, то в этом случае
необходимо либо признать, что эти последовательности для задачи
хранения являются идентичными, и исключить вторую последователь-
ность из рассмотрения, либо повторно разбить конфликтующую по-
следовательность с меньшим диаметром разбиения. Реализация функ-
ции
F
(
x
)
, в случае использования
R
-дерева как основы хаотического
процессора, будет состоять в получении из
R
-дерева списка регионов,
которым принадлежит точка
x
, и выборе из него того, центр которого
находится к
х
ближе всего.
Сложность операции вычисления меры близости при использова-
нии данного подхода составит
O
(
m
(
N/B
)
1
−
1
/n
)
, где
m
— длина за-
проса
Q
,
N
— число параллелепипедов размерности
n
, сохраненных в
дереве,
B
— размер дискового блока.
Рассмотрим процедуру поиска сохраненной последовательности
по поисковому запросу
{
Q
i
}
. Для этого запроса ассоциативная память
должна дать один из возможныхответов:
•
идентификатор последовательности, которая содержит подпо-
следовательность, похожую на
{
Q
i
}
, в смысле критерия, опи-
санного ранее;
•
“
необходимы дополнительные данные
”, в случае, если нельзя
однозначно сопоставить
{
Q
i
}
с сохраненными последователь-
ностями, т.е.
{
S
i
}
— подпоследовательность более чем одной
последовательности, и для того чтобы однозначно ответить на
поисковый запрос, необходимо дополнить поисковый запрос, т.е.
расширить его дополнительными точками;
•
null
в случае, если невозможно дать ни один из перечисленных
ответов, то
{
Q
i
}
не соответствует ни одной из сохраненных по-
следовательностей.
Процедура поиска наиболее похожей последовательности по за-
просу
Q
состоит из двухлогическихчастей: оценка похожести сохра-
ненныхпоследовательностей на запрос
Q
и выбор одного из перечи-
сленныхответов по результатам оценки.
Оценки для первого шага получаются итеративным образом, ана-
логичным вычислению меры похожести запроса
Q
последовательно-
сти
S
i
: последовательно рассматриваются точки запроса, но учитыва-
ются все регионы, в которые попала точка запроса. Таким образом,
значения мер близости
Q
и
S
i
для всехсохраненныхпоследовательно-
стей вычисляются за один проход по точкам запроса. Все пары
{
S
i
, v
i
}
ранжируются по убыванию
v
i
, и в зависимости от того, сколько эле-
ментов содержат максимальное значение
v
max
=
supp
(
v
i
)
, делается
второй шаг.
114 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2007. № 2
