% !TeX encoding = UTF-8
% !TeX spellcheck = ru_RU-Russian

\section{Параллельный алгоритм поиска активностей}
\label{sec:Approach}

\subsection{Формальные определения и обозначения}
\label{sec:Definitions}

\textit{Временной ряд (time series)} $T$ представляет собой последовательность хронологически упорядоченных вещественных значений:

\begin{equation}
	\label{eq:Series}
	T=(t_1,\ldots,t_n), \, t_i \in \mathds{R}
\end{equation}
Число $n$ обозначается как $ \lvert T \rvert $ и называется длиной ряда.

\textit{Подпоследовательность (subsequence)} $T_{i,m}$ временного ряда $T$ представляет собой непрерывное подмножество $T$ из $m$ элементов, начиная с позиции $i$:

\begin{equation}
	\label{eq:Subsequence}
	T_{i,m}=(t_i,\ldots,t_{i+m-1}), \, 1 \leqslant m \ll n, 1 \leqslant i \leqslant n-m+1.
\end{equation}

Временной ряд $T$ может быть логически разбит на сегменты~-- непересекающиеся подпоследовательности заданной длины $m$. Здесь и далее без существенного ограничения общности мы можем считать, что $n$ кратно $m$, поскольку $m \ll n$ Множество сегментов ряда, имеющих длину $m \ll n$, обозначим как $S_T^m$, элементы этого множества как $S_1,\ldots,S_{n/m}$:

\begin{equation}
	\label{eq:Segment}
	S_T^m=(S_1,\ldots,S_{n/m}), \, S_i=T_{m\cdot(i-1)+1,\,m}.
\end{equation}

Концепция \textit{сниппетов (snippet)} предложена Кеогом и др. в работе~\bblcite{DBLP:conf/icbk/ImaniMDCK18} и уточняет понятие типичных подпоследовательностей временного ряда следующим образом. Каждый сниппет представляет собой один из сегментов временного ряда. Со сниппетом ассоциируются его ближайшие соседи~-- подпоследовательности ряда, имеющие ту же длину, что и сниппет, которые более похожи на данный сниппет, чем на другие сегменты. Для вычисления схожести подпоследовательностей используется специализированная мера схожести MPdist, основанная на евклидовом расстоянии. Сниппеты упорядочиваются по убыванию мощности множества своих ближайших соседей. Множество сниппетов ряда $T$, имеющих длину $m$ обозначается, как $C_T^m$, а элементы этого множества~-- как $C_1,\ldots,C_K$:

\begin{equation}
	\label{eq:Snippets}
	C_T^m=(C_1,\ldots,C_K), \, C_i \in S_T^m.
\end{equation}
Число $K$ $(1 \leqslant K \leqslant n/m)$ представляет собой параметр, задаваемый прикладным программистом, и отражает соответствующее количество наиболее типичных сниппетов. С каждым сниппетом ассоциированы следующие атрибуты: индекс сниппета, ближайшие соседи и значимость данного сниппета. Сниппеты упорядочиваются по убыванию их значимости.


Мера MPdist~\bblcite{DBLP:journals/datamine/GharghabiIBDK20}, используемая для вычисления схожести подпоследовательностей при нахождении сниппетов, неформально определяется следующим образом. Два временных ряда равной длины $m$ тем более похожи друг на друга в смысле меры MPdist, чем больше в каждом из них имеется подпоследовательностей заданной длины $\ell \; (3 \leqslant \ell \leqslant m)$, близких друг к другу в смысле нормализованного евклидова расстояния.

\subsection{Реализация}
\label{subsec:Approach-Implementation}

В данном разделе приводится краткое описание параллельного алгоритма PSF поиска сниппетов на графическом процессоре, предложенного в нашей  предыдущей работе~\bblcite{ZymblerGoglachev}.

\begin{figure}[ht!]
	\centering
	\includegraphics[width=0.95\linewidth]{pic-data}
	\caption{Структуры данных алгоритма PSF}
	\label{fig:DataStructures}
\end{figure}

Структуры данных алгоритма PSF представлены на рис.~\ref{fig:DataStructures}. 
Ключевой для распараллеливания структурой данных является матрица $ED_{matr}$, в которой хранятся нормализованные евклидовы расстояния между каждой подпоследовательностью длины $\ell$ сегмента $S$ и каждой подпоследовательностью длины $\ell$ исходного ряда: 
\begin{equation}
	\label{eq:EDmatr}
	%\forall seg \in S^m_T \,\, \exists ED_{matr} \in \mathds{R}^{(m-\ell+1)\times(n-m+1)}: \, ED_{matr}(i,j)=\operatorname{ED_{norm}}(S_{i,\,\ell},T_{j,\,\ell}).  
	ED_{matr} \in \mathds{R}^{(m-\ell+1)\times(n-\ell+1)}:\, ED_{matr}(i,j)=\operatorname{ED_{norm}}(S_{i,\,\ell},T_{j,\,\ell}).
\end{equation}

Параллелизм вычислений матрицы расстояний $ED_{matr}$ реализован на основе следующей техники, предложенной в работе~\bblcite{DBLP:conf/icdm/YehZUBDDSMK16}. Сначала вычисляется матрица центрированных сумм произведений значений ряда, которая используется для вычисления корреляции по Пирсону между подпоследовательностями ряда. Далее значения корреляции по Пирсону между двумя подпоследовательностями ряда преобразуются в z-нормализованное евклидово расстояние.

На втором шаге в каждом столбце матрицы $ED_{matr}$, полученной на первом шаге, находится минимум. Обозначим вектор таких минимумов за $allP_{BA}$:

\begin{equation}
	\label{eq:allPBA}
	allP_{BA} \in \mathds{R}^{n-\ell+1}: \, allP_{BA}(j)=\min_{1 \leqslant i \leqslant m-\ell+1}ED_{matr}(i,j).  
\end{equation}

На третьем шаге в каждой строке $ED_{matr}$ выполняется поиск минимумов в скользящем окне длины~$\ell$. Обозначим матрицу таких минимумов за $allP_{AB}$:

\begin{equation}
	\label{eq:allPAB}
	allP_{AB} \in \mathds{R}^{(m-\ell+1)\times(n-\ell+1)}: \, allP_{AB}(i,j)=\min _{j \leqslant c \leqslant j+m-\ell+1}ED_{matr}(i,c).  
\end{equation}

На четвертом шаге для каждой подпоследовательности ряда, имеющей длину $\ell$, и сегмента $S$ выполняется построение матричного профиля. Для построения одного матричного профиля выполняется сцепление соответствующих данной подпоследовательности столбца матрицы $allP_{AB}$ и подпоследовательности длины $m-\ell+1$, входящей в вектор $allP_{BA}$. Результат сцепления обозначим как вектор $P_{ABBA}$ (здесь символ $\odot$ означает операцию конкатенации):

\begin{equation}
	\label{eq:PABBA}
	%\forall seg \in S^m_T \, P_{ABBA}(seg,j)=allP_{AB}(seg,j) \cdot allP_{BA}(j) \cdot \ldots \cdot allP_{BA}(j+\ell), \, 1 \leqslant j \leqslant n-m+1.  
	%P_{ABBA} \in \mathds{R}^{2(m-\ell+1)}: \, P_{ABBA}(T_{j,\ell})=\{allP_{AB}(i,j)\}_{i=1}^{m-\ell+1} \, \odot \, \{allP_{BA}(i)\}_{i=j}^{m-\ell+1},
	\begin{gathered}
		P_{ABBA} \in \mathds{R}^{2(m-\ell+1)}: \, P_{ABBA}(T_{j,\,\ell})=allP_{AB}(1,j) \odot \ldots \odot allP_{AB}(m-\ell+1,j)  \, \odot \\
		\odot \, allP_{BA}(j) \odot \ldots \odot allP_{BA}(m-\ell+1),
	\end{gathered}
	%	P_{ABBA} \in \mathds{R}^{2(m-\ell+1)}: \, P_{ABBA}(T_{j,\ell})=\{allP_{AB}(i,j)\}_{i=1}^{m-\ell+1} \, \odot \, \{allP_{BA}(i)\}_{i=j}^{m-\ell+1},
\end{equation}
где $1 \leqslant j \leqslant n-\ell+1$. Для финального вычисления меры схожести MPdist между сегментом и подпоследовательностью необходимо выполнить сортировку вектора $P_{ABBA}$ по возрастанию и взять его $k$-е значение.