sec_2_4.tex.bak

\begin{frame}
\frametitle{About This Work...}

\emph{Spatio-temporal Joins on Symbolic Indoor Tracking Data}.~\cite{DBLP:conf/icde/LuYCJ11} \\
H.~Lu, B.~Yang, and C.~S. Jensen.\\~\\

\begin{itemize}
  \item Published at \emph{ICDE' 2011}.
  \item Studies the probabilistic, spatio-temporal joins on hisorical indoor tracking data.
  \item Two-phase hash-based algorithms are proposed for the point and interval joins.
  \item A filter-and-refine framework, along with spatial indexes and pruning rules.
\end{itemize}

\end{frame}
%------------------------------------------------

\begin{frame}
\frametitle{Motivation}

\begin{itemize}
  \item Huge amount of tracking data serves as a foundation for a wide variety of indoor applications and services.\cite{jensen2010indoor}
    \begin{fitemize}
      \item shopping mall, airports, office buildings, akin to those enabled by outdoor GPS
      \item hot area detection, space planning, security control, movement pattern discovery
    \end{fitemize}

  \item Spatio-temporal joins fall short in indoor setting.
    \begin{fitemize}
      \item indoor space consists of semantic entities enable or constrain movement
      \item semantics of indoor space call for novel spatio-temporal join predicates
      \item indoor positioning technologies differ fundamentally from outdoor setting, low accuracy and sampling frequency
    \end{fitemize}

  \item Joins on indoor tracking data call for new definition and new implementation techniques that take into account:
  \begin{fitemize}
    \item specifics of indoor space
    \item limitations of indoor positioning
  \end{fitemize}
\end{itemize}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Preliminaries: Symbolic Indoor Tracking}

\begin{figure}[tb]
  \includegraphics[width=\columnwidth]{figures/2-4/2-4-1.pdf}
\end{figure}

\begin{enumerate}
  \ssize{
  \item ${C2P: C \rightarrow 2^P}$ maps a cell to a set of indoor partitions
  \item ${D2C: D \rightarrow 2^C}$ maps a device to a set of corresponding cells
  \item According to Deployment Graph, for partitioning device, ${D2C(device_{13})} = \{ C_{10},C_{13} \} \cup \{ C_{12},C_{13} \} = \{ C_{10},C_{12},C_{13} \}$
  \item For presence device, ${D2C(device_{25})} = \{ C_{21},C_{22} \}$ as the cells intersect its detection range.
  \item ${D2C: D \rightarrow 2^C}$ is useful as it captures the possible movements of objects.
  }
\end{enumerate}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Preliminaries: Symbolic Indoor Tracking}

\begin{columns}[c]
  \column{.52\textwidth}
  \begin{figure}[tb]
    \includegraphics[width=\columnwidth]{figures/2-4/2-4-2.pdf}
  \end{figure}

  \column{.48\textwidth}
  \begin{fitemize}
    \item \conceptbf{Object Tracking Table} ${OTT}$ records the converted trajectories with schema ${(ID, objectID, deviceID, t_s, t_e)}$
    ~\\
    \item a record states that the object ${objectID}$ is observed by the device ${deviceID}$ in the closed interval from time ${t_s}$ to ${t_e}$.
  \end{fitemize}

\end{columns}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Problem Definitions}

Given an ${OTT}$, it is of interesting to identify object pairs that join w.r.t some specific spatio-temporal join predicate.
\begin{fitemize}
  \item to know all pair of individuals that were probably at the same gate when a particular event (terrorist attack) occurred in a large airport.
\end{fitemize}
~\\
Due to tracking uncertainty, only interested in those objects that satisfy the join predicate with some given probability (specified threshold).
\\~\\
The joins are effectively \emph{self-joins} because all tracking data is contained in a single ${OTT}$.

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Problem Definition I}

\textrm{One can apply a join predicate to a time point to find pairs that join at that particular time point...}
\\~\\
\begin{definition}[\ssize{Probabilistic Threshold Indoor Spatio-temporal Join--PTISSJ}]
  \textrm{
  \ssize{
  Given an ${OTT}$, a join predicate ${P}$, a time point ${t}$, and a threshold value ${M \in (0,1]}$, a probabilistic threshold indoor spatio-temporal join  ${\Join_{P,t,M}(OTT) = \{ (o_i, o_j) | o_i, o_j \in O  \wedge o_i \neq o_j \wedge pr(P(o_i, o_j, t)) >M \}}$, where ${pr(P(o_i,o_j,t))}$ is the \textbf{Timeslice Join Probability} of ${o_i, o_j}$ at time ${t}$, i.e., the probability that predicate ${P(o_i,o_j,t)}$ is true.
  }}
\end{definition}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Problem Definition II}

\textrm{It's also interesting to know object pairs satisfy the predicate for some consecutive timestamp...}
\\~\\
\begin{definition}[\ssize{Probabilistic Threshold $k$ Indoor Spatio-temporal Join--PT$k$ISSJ}]
  \textrm{
  \ssize{
  Given an ${OTT}$, a join predicate ${P}$, a time interval ${I = [t_m, t_n] (m < n)}$, an integer ${k(0 < k \leq n - m)}$, and a threshold value ${M \in (0,1]}$, a probabilistic ${k}$ threshold indoor spatio-temporal join
  \begin{equation*}
    \begin{split}
    &{\Join_{P,I,k,M}(OTT) = \{ (o_i, o_j) | o_i, o_j \in O \wedge o_i \neq o_j \wedge } \\
    &{\exists s \in m...n -k + 1 (\forall\delta \in 0...k-1 (pr(P(o_i, o_j, t_{s+\delta})) > M)) \} }
    \end{split}
  \end{equation*}
  }}
\end{definition}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Uncertainty Model for Indoor Tracking}

\textrm{For outdoor moving objects~\cite{cheng2004querying}, \conceptbf{Uncertainty Region}, denoted by ${UR(o_i,t)}$, is a region such that ${o_i}$ must be in this region at time ${t}$.}\\~

In general terms, an object ${o_i}$'s location can be modeled as a random variable ${l}$ associated with a probability density function ${f_{o_i}(l,t)}$ that has non-zero values only in ${o_i}$'s suncertainty region ${UR(o_i, t)}$.~\cite{DBLP:conf/edbt/YangLJ10}

\begin{equation}
  {\int_{l \in UR(o_i,t)} f_{o_i}(l,t) dl = 1}
\end{equation}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Object State in OTT}

\begin{columns}[c]

\column{.45\textwidth}
\begin{figure}[tb]
  \includegraphics[width=\columnwidth]{figures/2-4/2-4-3.pdf}
\end{figure}

\column{.55\textwidth}
\begin{definition}[Active State]
  \textrm{
  \ssize{
  Given an object ${o_i}$ and a time point ${t}$, if a tracking record ${rd_{cov}}$ is found in ${OTT}$ such that ${rd_{cov}.objectID = o_i}$ and ${t \in [rd_{cov}.t_s, rd_{cov}.t_e]}$, ${o_i}$ is in the \conceptbf{active state} at time ${t}$.
  }}
\end{definition}

\end{columns}

\begin{definition}[Inactive State]
  \textrm{
  \ssize{
  Given an object ${o_i}$ and a time point ${t}$, if no record ${rd_{cov}}$ is found in ${OTT}$, ${o_i}$ is in the \conceptbf{inactive state} at time ${t}$. Instead, two tracking records of ${o_i}$ called ${rd_{pre}}$ and ${rd_{suc}}$, can be found in ${OTT}$, such that they are consecutive in the sense that ${rd_{pre}.t_e < t < rd_{suc}.t_s}$ and there is no record for ${o_i}$ between times ${rd_{pre}.t_e}$ and ${rd_{suc}.t_s}$.
  }}
\end{definition}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Uncertainty Region in the Active State}

\begin{columns}[c]
  \column{.52\textwidth}
  \vspace{-10pt}
  \begin{figure}[tb]
    \includegraphics[width=\columnwidth]{figures/2-4/2-4-2.pdf}
  \end{figure}
  \vspace{-15pt}
  \begin{example}
    \textrm{
    \ssize{
    ${t = t_5}$, ${rd_{cov} = rd_3}$ and ${rd_{pre} = rd_1}$, which tells ${o_i}$ left ${dev_4}$'s detection range at time ${t_2}$, and is currently detected by ${dev_2}$.
    }}
  \end{example}

  \column{.48\textwidth}
  \vspace{-10pt}
  \begin{figure}[tb]
    \includegraphics[width=\columnwidth]{figures/2-4/2-4-4.pdf}
  \end{figure}
  \ssize{
  \textbf{Step 1:}
  UR is the detection range of device ${rd_{cov}.deviceID}$, denote as:
  \begin{equation*}
  \begin{split}
    { C_{cov} = } & { Cir(Loc(rd_{cov}.deviceID), }\\
    &{ Rad(rd_{cov}.deviceID)) }
  \end{split}
  \end{equation*}
  ~\\
  \textbf{Step 2:}
  UR should consider the ${rd_{pre}}$'s \emph{maximum speed bounding ring}(MSBR):
  \tiny{
  \begin{equation*}
  \begin{split}
    &{ UR(o_i, t) = C_{cov} \cap Ring(Loc(rd_{pre}.deviceID), } \\
    &{ Rad(rd_{pre}.deviceID), V_i \cdot (t - rd_{pre}.t_e) ) }
  \end{split}
  \end{equation*}
  }
  }
\end{columns}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Uncertainty Region in the Inactive State}

\begin{columns}[c]

  \column{.52\textwidth}
  \vspace{-10pt}
  \begin{figure}[tb]
    \includegraphics[width=\columnwidth]{figures/2-4/2-4-2.pdf}
  \end{figure}
  \vspace{-15pt}
  \begin{example}
    \textrm{
    \ssize{
    ${t = t_{19}}$, ${rd_{pre} = rd_6}$ and ${rd_{suc} = rd_8}$, since ${rd_6.t_e = t_{16} < t_{19} < rd_8.t_s = t_{21}}$. we have ${dev_p = dev_{12}}$ and ${dev_s = dev_{13}}$
    }}
  \end{example}

  \column{.48\textwidth}
  \vspace{-10pt}
  \begin{figure}[tb]
    \includegraphics[width=\columnwidth]{figures/2-4/2-4-5.pdf}
  \end{figure}
  \ssize{
  \textbf{Step 1:}
  Determine the possible cells in which the object can be in the inactive period:
  \begin{equation*}
    { Cells_{mid} = D2C(dev_p) \cup D2C(dev_s)}
  \end{equation*}
  ~\\
  \textbf{Step 2:}
  UR is constrained by two \emph{maximum speed bounding ring}(MSBR)s of ${rd_{pre}}$ and ${rd_{suc}}$:
  \tiny{
  \begin{equation*}
  \begin{split}
    { UR(o_i, t) = \bigcup_{c \in Cells_{mid}} c \cap R_{pre} \cap R_{suc} }
  \end{split}
  \end{equation*}
  }
  }
\end{columns}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Join Probability Evaluation}

\begin{definition}[the \emph{same X} predicate]
  \textrm{
  \ssize{
    termed as ${P_X}$, where ${X}$ represents an indoor region type. ${IR_X}$ represents all ${X}$ type regions (${X}$-regions).
  }
  }
\end{definition}
~\\
\begin{example}[the \emph{same room} predicate]
  \textrm{
  \ssize{
    Given two objects ${o_i, o_j}$ at a time point ${t}$, the \emph{same room} predicate ${P_X(o_i, o_j, t)}$ evaluates to true if both ${o_i, o_j}$ were located in a same room ${rm \in IR_X}$. Other predicates can be \emph{same floor, same reserach group (maps to several rooms)}.
  }
  }
\end{example}
~\\
The \emph{same X} predicates are more practical than Euclidean distance based join predicates in indoor space.

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Join Probability Evaluation}
\vspace{-10pt}
\begin{definition}[``be located at'' predicate probability]
  \textrm{
  \ssize{
    Given an object ${o_i}$, an ${X}$-region ${x_l \in IR_X}$, and a time ${t}$, predicate $\Theta(o_i, x_l, t)$ indicate that ${o_i}$ was located in ${x_l}$ at ${t}$. The probability that ${\Theta}$ is satisfied is defined as:
    \begin{equation*}
      {pr(\Theta(o_i, x_l, t)) = \frac{Area(UR(o_i, t) \cap x_l)}{Area(UR(o_i, t))}}
    \end{equation*}
  }
  }
\end{definition}

\begin{definition}[the \emph{same X} predicate probability]
  \textrm{
  \ssize{
    The probability that ${o_i}$ and ${o_j}$ were located in the same ${x_l}$ at ${t}$, indicated by ${pr(P_{x_l}(o_i, o_j, t))}$ is defined as:
    \begin{equation*}
      {pr(P_{x_l}(o_i, o_j, t)) = pr(\Theta(o_i, x_l, t)) \cdot pr(\Theta(o_j, x_l, t)) }
    \end{equation*}
    Therefore, the porbability that ${o_i}$ and ${o_j}$ satisfy a \emph{same X} predicate at time ${t}$ can be defined as:
    \begin{equation*}
      {pr(P_X(o_i, o_j, t)) = \max_{x_l \in IR_X} pr(P_{x_l}(o_i, o_j, t)) }
    \end{equation*}
  }
  }
\end{definition}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Indexing the Indoor Tracking Data}

\textrm{to determine the \emph{Uncertainty Region} during join processing, it needs to retrieve the records ${rd_{cov}}$ and ${rd_{pre}}$ for active objects or ${rd_{pre}}$ and ${rd_{suc}}$ for inactive state.}
\\~\\
to index ${OTT}$ with an augmented 1D R-tree, where each leaf entry has the form ${(t^{\vdash},t^{\dashv},Ptr_{p},Ptr_{c})}$. ${t^{\vdash} = rd_p.t_e}$, ${t^{\dashv} = rd_c.t_e}$, ${Ptr_p}$ and ${Ptr_c}$ points to ${rd_p}$ and ${rd_c}$ respectively.

\begin{fitemize}
  \item if ${t \geq rd_c.t_s}$, ${o_i}$ is active, ${rd_p \rightarrow rd_{pre}}$ and ${rd_c \rightarrow rd_{cov}}$;
  \item if ${t < rd_c.t_s}$, ${o_i}$ is inactive, ${rd_p \rightarrow rd_{pre}}$ and ${rd_c \rightarrow rd_{suc}}$;
\end{fitemize}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Accessing ${X}$-Regions}

\textrm{object locations are bounded by either device detection ranges or cells.}

\begin{columns}[c]

  \column{.54\textwidth}
  \begin{figure}[tb]
    \includegraphics[width=\columnwidth]{figures/2-4/2-4-6.pdf}
  \end{figure}

  \column{0.48\textwidth}
  \begin{sitemize}
    \item ${CovD2X: D \rightarrow IR_X}$ maps a device to an ${X}$-Region that fully covers the device's detection range;
    \item ${IntD2X: D \rightarrow IR_X}$ maps a device to an ${X}$-Region that only intersects the device's detection range;
    \item ${CovC2X: C \rightarrow IR_X}$ maps a cell to an ${X}$-Region that fully covers this cell;
    \item ${IntC2X: C \rightarrow IR_X}$ maps a cell to an ${X}$-Region that only intersects with;
  \end{sitemize}

\end{columns}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Processing PTISSJ Queries: Partitioning Phase}

\begin{columns}[c]

  \column{.47\textwidth}
  \vspace{-10pt}
  \begin{figure}[tb]
    \includegraphics[width=\columnwidth]{figures/2-4/2-4-7.pdf}
  \end{figure}

  \column{0.53\textwidth}
  \begin{fitemize}
    \item all indoor objects are partitioned into buckets that each refers to a distinct ${X}$-region
    \item first, A1R-tree is searched to get all leaf entries whose interval ${(t^{\vdash},t^{\dashv}]}$ contains the join time ${t}$
    \item second, the spatial examination obtains all relevant ${X}$-region in which ${o_i}$ may be at time ${t}$
    \item the relevant probabilities are evaluated for each object, and the necessary records are generated and added to relevant buckets, for each ${p_l = pr(\Theta(o_i, x_l, t))}$, if it is larger than threshold ${M}$, insert the record into buckets.
  \end{fitemize}

\end{columns}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Processing PTISSJ Queries: Partitioning Phase}

\begin{columns}[c]

  \column{.5\textwidth}
  \textbf{Active State}~\\
  \ssize{
  \textrm{object ${o_i}$ must be in device ${dev}$'s detection range at time ${t}$}.~\\
  \begin{enumerate}
    \item if the detection range is fully covered by an ${X}$-region ${x_l}$, as indicated by ${CovD2X(dev_c) = x_l}$, a record ${(o_i, 1.0)}$ is added to ${x_l}$'s bucket;
    \item otherwise, ${dev_c}$'s detection range intersects with each ${X}$-region in ${CovD2X(dev_c)}$, evaluated the probability, if it is larger than ${M}$, add to the bucket.
  \end{enumerate}
  }

  \column{0.5\textwidth}
  \textbf{Inactive State}~\\
  \ssize{
  \textrm{object ${o_i}$ must be in a cell in ${Cells_{mid} = D2C(dev_p) \cap D2C(dev_c)}$}.~\\
  \begin{enumerate}
    \item if ${Cells_{mid}}$ is the singleton set and the cell is covered by one ${X}$-region ${x_l}$, indicated by ${CovC2X(c)= x_l}$, a record ${(o_i, 1.0)}$ is added to ${x_l}$'s bucket;
    \item otherwise, the single cell ${c}$ in ${Cells_{mid}}$ intersects with several ${X}$-regions (indicated by ${CovC2X(c)}$), or ${Cells_{mid}}$ contains several cells.
  \end{enumerate}
  }

\end{columns}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Processing PTISSJ Queries: Join Phase}

\begin{columns}[c]

  \column{.5\textwidth}
  \vspace{-10pt}
  \begin{figure}[tb]
    \includegraphics[width=\columnwidth]{figures/2-4/2-4-8.pdf}
  \end{figure}

  \column{0.5\textwidth}
  \begin{fitemize}
    \item the records in the same bucket indicate all those objects that may join with other objects in the corresponding ${X}$-region with probabilities greater than ${M}$
    \item the join probability is evaluated according to the equation:
  \end{fitemize}

\end{columns}
~\\
\begin{equation*}
  {pr(P_X(o_i, o_j, t)) = \max_{x_l \in IR_X} pr(P_{x_l}(o_i, o_j, t)) }
\end{equation*}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Processing PT${k}$ISSJ Queries: Partitioning Phase}

\begin{columns}[c]

  \column{.48\textwidth}
  \vspace{-10pt}
  \begin{figure}[tb]
    \includegraphics[width=\columnwidth]{figures/2-4/2-4-9.pdf}
  \end{figure}

  \column{0.52\textwidth}
  \begin{fitemize}
    \item first, A1R-tree is searched to get all leaf entries whose interval ${(t^{\vdash},t^{\dashv}]}$ contains the join interval ${I}$.
    \item second, the spatial examination is conducted on each retrieved leaf entry to obtain all relevant ${X}$-regions for each object.
    \item after the spatial examination,  the bucket of each ${X}$-region ${x_l}$ involved contains a set of records of the form ${(objectID, [t_x, t_y])}$.
  \end{fitemize}

\end{columns}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Processing PT${k}$ISSJ Queries: Join Phase}

\begin{block}{\textrm{Prunning Rule 2}}
  \textrm{A record ${(objectID, [t_x, t_y])}$ is pruned if ${t_y - t_x + 1 < k}$. }
\end{block}
~\\
\begin{block}{\textrm{Prunning Rule 3}}
  \textrm{If a bucket contains only one record, or all its records involve only one object, the bucket is pruned. }
\end{block}
~\\
\begin{block}{\textrm{Prunning Rule 4}}
  \textrm{Two records ${(objectID_1, [t_x, t_y])}$ and ${(objectID_2, [t_u, t_v])}$ do not satisfy the join predicate if ${|[t_x, t_y] \cap [t_u, t_v]| < k}$.}
\end{block}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Processing PT${k}$ISSJ Queries: Join Phase}

\begin{columns}[c]

  \column{.52\textwidth}
  \vspace{-10pt}
  \begin{figure}[tb]
    \includegraphics[width=\columnwidth]{figures/2-4/2-4-10.pdf}
  \end{figure}

  \column{0.48\textwidth}
  \begin{titemize}
    \item first, records with as same ${objectID}$ and adjacent time intervals are merged into one records, after merging, pruning is done on the bucket according to the above-mentioned rules.
    \item next, the ramaining records in ${X}$-region buckets are processed with relevant probabilities evaluated.
    \item \emph{the plane sweep}~\cite{pfoser1999capturing}, only if two object's record pair have their overlapping time interval contain at least ${k}$ timestamps, the probability is evaluated.
    \item if two objects have been found to join in one bucket, skip all record pairs involving the two in all remaining buckets.
    \item skip the remaining evaluation, when the calculated probability (after ${k}$ time points) has already greater than ${M}$, even the whole time interval is not finished.
    \item stop the remaining evaluation, when the calculated probability has already less than ${M}$, even the whole time interval is not finished.
  \end{titemize}

\end{columns}

\end{frame}

%------------------------------------------------

\begin{frame}
\frametitle{Processing PT${k}$ISSJ Queries: Join Phase}

\begin{itemize}
  \item it's of interest to define join predicates beyond the \emph{same X} predicates, available non-spatial properties of objects may be used to define alternative join types.
  \item it's also relevant to use more complex PDFs for indoor moving objects, as well as to take into account possible dependencies between objects.
  \item more general types of queries, e.g., range queries can be defined for indoor moving objects w.r.t. uncertainty analysis.
\end{itemize}

\end{frame}