sec_4_1.tex

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

\emph{Finding Frequently Visited Indoor POIs Using Symbolic Indoor Tracking Data}.~\cite{lu2016finding} \\
H.~Lu, C.~Guo, B.~Yang, C.S.~Jensen.\\~\\

\begin{itemize}
  \item Published at \emph{EDBT' 2016}.
  \item Indoor flow counting methods on symbolic indoor tracking data are defined.
  \item Query related object uncertainty regions are derived by analysing the relationship between queries and tracking data.
  \item Make use of uncertainty analysis results to design algorithms for two specified query types.
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Motivation}

\begin{itemize}
  \setlength{\itemsep}{15pt}
  \item The indoor movements of people are increasingly datafied due to advances in indoor positioning.\cite{InLoc0:online}
    \begin{fitemize}
      \item indoor tracking data is being accumulated in a variety of formats determined by the particular indoor positioning systems.
    \end{fitemize}

  \item Analyzing indoor tracking data can reveal how different parts of an indoor space are used.
    \begin{fitemize}
      \item the number of visits to a particular part of space over time.
    \end{fitemize}

  \item Flow counting in indoor spaces faces new, unique technical challenges.
  \begin{fitemize}
    \item uncertainties in indoor positioning systems
    \item indoor entities like doors and rooms enable as well as constrain the movement of indoor objects~\cite{DBLP:conf/edbt/YangLJ10}
  \end{fitemize}
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Notations}

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

\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}

\begin{itemize}
  \item each indoor POI $p$ has some fixed extend modeled by a polygon.
  \item Given an object $o$, $UR(o, t)$ is $o$'s \conceptbf{snapshot uncertainty region} at time $t$. $UR(o, [t_s, t_e])$ is $o$'s \conceptbf{interval uncertainty region} during time interval $[t_s, t_e]$.
\end{itemize}

\begin{definition}[Object Presence]
  \small
  During a given time interval $[t_s, t_e]$, an object $o$'s interval presence in a POI $p$ is
  \begin{equation*}
    \phi_{t_s, t_e, p}(o) = \frac{area(UR(o, [t_s, t_e]) \cap p}{area(p)}
  \end{equation*}
  Similarly, $\phi_{t, p}(o)$ is defined by replacing $UR(o, [t_s, t_e])$ with $UR(o,t)$.
\end{definition}

\end{frame}

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

\begin{frame}
\frametitle{Problem Definitions}

\begin{definition}[Flow]
  \small
  Suppose $O$ is the set of all objects in an indoor space of interest. Given an indoor POI $p$ and a time interval $[t_s, t_e]$, $p$' interval flow is defined as
  \begin{equation*}
    \Phi{t_s, t_e}(p) = \sum_{o \in O}\phi_{t_s, t_e, p}(o)
  \end{equation*}
  Similarly, $\Phi_{t}(p)$ is defined by replacing $\phi_{t_s, t_e, p}(o)$ with $\phi_{t, p}(o)$.
\end{definition}


\end{frame}

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

\begin{frame}
\frametitle{Problem Definitions}

\begin{problem}[Snapshot Top-$k$ Indoor POIs Query]
  \small
  Given a set $P$ of indoor POIs, a time point $t$, and an integer $k$ ($0 < k \leq |P|$), return a $k$-subset $P_T$ of $P$ such that $\forall p \in P_T (\forall p' \in P \setminus P_T (\Phi_{t}(p) \geq \Phi_{t}(p')))$.
\end{problem}

\begin{problem}[Interval Top-$k$ Indoor POIs Query]
  \small
  Given a set $P$ of indoor POIs, a time interval $[t_s, t_e]$, and an integer $k$ ($0 < k \leq |P|$), return a $k$-subset $P_T$ of $P$ such that $\forall p \in P_T (\forall p' \in P \setminus P_T (\Phi_{t_s, t_e}(p) \geq \Phi_{t_s, t_e}(p')))$.
\end{problem}

\textrm{Most popular shops in a shopping mall / Possible bottlenecks that slow down movement}

\end{frame}

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

\begin{frame}
\frametitle{Tracking States~\cite{DBLP:conf/cikm/YangLJ09}}

  \begin{figure}[tb]
    \includegraphics[width=0.6\columnwidth]{figures/2-2/2-2-3.pdf}
  \end{figure}
  \vspace{-10pt}

  \begin{itemize}
    \item An object is in an \conceptbf{active state} when it is inside the activation range of a positioning device.
    \item Otherwise the object is in an \conceptbf{inactive state}
    \item When an object is in the inactive state it is
      \begin{itemize}
        \item \conceptbf{nondeterministic} if it can be in more than one cell
        \item \conceptbf{deterministic} if it is in one specific cell
      \end{itemize}
  \end{itemize}


\end{frame}

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

\begin{frame}
\frametitle{Snapshot Uncertainty Regions}

\textrm{Two cases for snapshot uncertainty region.~\cite{DBLP:conf/icde/LuYCJ11}}

\begin{columns}[c]

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

  \column{.7\textwidth}
  \begin{block}{}
    \ssize{
      In this case, $UR(o,t) = Ring(dev_{pre}, V_{max} \cdot (t - rd_{pre}.t_e)) \cap dev_{cov}.Range$. $o$'s uncertainty region is the intersection of $dev_{cov}$'s detection range and the ring in which $o$ can be after leaving $dev_{pre}$'s detection range.
    }
  \end{block}


\end{columns}

\begin{columns}[c]

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

  \column{.7\textwidth}
  \begin{block}{}
    \ssize{
    In this case, $UR(o,t) = Ring(dev_{pre}, V_{max} \cdot (t - rd_{pre}.t_e)) \cap Ring(dev_{suc}, V_{max} \cdot (rd_{suc}.t_s - t))$. $o$'s uncertainty region is the intersection of two rings that are determined by the previous reading's and successive reading's detection ranges respectively.
    }
  \end{block}

\end{columns}

\end{frame}

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

\begin{frame}
\frametitle{Uncertainty Regions Involving Two Consecutive Readings}

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

For time interval $[rd_i.t_e, rd_j.t_s]$ ($rd_i$ and $rd_j$ are two consecutive readings), object $o$'s location can be constrained by an ellipse, the length of the ellipse's major axis is $2a = V_{max} \cdot (rd_j.t_s - rd_i.t_e)$. Such a region covered by the ellipse is denoted by $\Theta(dev_i, dev_j, rd_i.t_e, rd_j.t_s)$.

\end{frame}

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

\begin{frame}
\frametitle{Interval Uncertainty Regions}

\begin{block}{Notations}
  \begin{sitemize}
    \item $rd_s$ and $rd_e$ to represent the start and end records of the detection chains respectively.
    \item $rd_b$ to represent the a concrete record between $rd_s$ and $rd_e$.
  \end{sitemize}
\end{block}

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

\end{frame}

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

\begin{frame}
\frametitle{Interval Uncertainty Regions: Case I}

\begin{block}{Case I}
  \footnotesize
  Object $o$ is active at both $t_s$ and $t_e$, i.e., $rd_s = rd_{cov}(t_s)$ and $rd_e = rd_{cov}(t_e)$. $R = \langle rd_{cov}(t_s), rd_{b1}, \ldots, rd_{cov}(t_e) \rangle$.
  \begin{equation*}
    UR(o, [t_s, t_e]) = \bigcup_{i = 1..|R-1|}\Theta(dev_i, dev_{i+1}, rd_i.t_e, td_{i+1}.t_s).
  \end{equation*}
\end{block}

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

\end{frame}

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

\begin{frame}
\frametitle{Interval Uncertainty Regions: Case II}

\begin{block}{Case II}
  \footnotesize
  Object $o$ is inactive at $t_s$ but active at $t_e$, i.e., $rd_s = rd_{pre}(t_s)$ and $rd_e = rd_{cov}(t_e)$. $R = \langle rd_{b1}, \ldots, rd_{cov}(t_e) \rangle$.
  \begin{equation*}
    \begin{split}
    & UR(o, [t_s, t_e]) = (\Theta_s \cap Ring_s) \cup \bigcup_{i = 1..|R-1|}\Theta(dev_i, dev_{i+1}, rd_i.t_e, td_{i+1}.t_s).\\
    & \Theta_s = \Theta(dev_s, dev_{b1}, rd_s.t_e, rd_{b1}.t_s) \\
    & Ring_s = Ring(dev_{b1}, V_{max} \cdot (rd_{b1}.t_s - t_s))
    \end{split}
  \end{equation*}

\end{block}

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

\end{frame}

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

\begin{frame}
\frametitle{Interval Uncertainty Regions: Case III}

\begin{block}{Case III}
  \footnotesize
  Object $o$ is active at $t_s$ but inactive at $t_e$, i.e., $rd_s = rd_{cov}(t_s)$ and $rd_e = rd_{suc}(t_e)$. $R = \langle rd_{cov}(t_s), rd_{b1}, \ldots, rd_{b2} \rangle$.
  \begin{equation*}
    \begin{split}
    & UR(o, [t_s, t_e]) = (\Theta_e \cap Ring_e) \cup \bigcup_{i = 1..|R-1|}\Theta(dev_i, dev_{i+1}, rd_i.t_e, td_{i+1}.t_s).\\
    & \Theta_e = \Theta(dev_{b2}, dev_e, rd_{b2}.t_e, rd_e.t_s) \\
    & Ring_e = Ring(dev_{b2}, V_{max} \cdot (t_e - rd_{b2}.t_e))
    \end{split}
  \end{equation*}

\end{block}

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

\end{frame}

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

\begin{frame}
\frametitle{Interval Uncertainty Regions: Case IV}

\begin{block}{Case IV}
  \footnotesize
  Object $o$ is inactive at both $t_s$ and $t_e$, i.e., $rd_s = rd_{pre}(t_s)$ and $rd_e = rd_{suc}(t_e)$. $R = \langle rd_{b1}, \ldots, rd_{b2} \rangle$.
  \begin{equation*}
    \begin{split}
    & UR(o, [t_s, t_e]) = (\Theta_s \cap Ring_s) \cup (\Theta_e \cap Ring_e) \\
    & \cup \bigcup_{i = 1..|R-1|}\Theta(dev_i, dev_{i+1}, rd_i.t_e, td_{i+1}.t_s).
    \end{split}
  \end{equation*}

\end{block}

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

\end{frame}

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

\begin{frame}
\frametitle{Indoor Topology Check}

\begin{columns}[c]

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

  \column{.7\textwidth}
  \begin{example}[Snapshot UR]
    \ssize{
      $o$ is inactive at time $t$, it was detected by device 1 at time $t_1 < t$ and then by device 3 after $t$. The shadow part should be excluded as it's too far away for $o$ to be able to reach through the door.
    }
  \end{example}

\end{columns}

\end{frame}

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

\begin{frame}
\frametitle{Indoor Topology Check}

\begin{columns}[c]

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

  \column{.7\textwidth}
  \begin{example}[Interval UR]
    \ssize{
      $o$ is detected by device 1 and 4, and then 2. Due to the maximum speed constraint, the object cannot entered the shaded regions. Otherwise, the flows of rooms 4 and 5 would be incorrectly increased and they may enter the top-$k$ result as false positives.
    }
  \end{example}

\end{columns}

\end{frame}

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

\begin{frame}
\frametitle{Indexes}

\begin{block}{Augmented 1D R-tree -- A1R-tree~\cite{DBLP:conf/mdm/JensenLY09}}
  \ssize{
  Let $rd_c$ be a tracking record in $OTT$, such a record $rd_c$ is indexed by an A1R-tree leaf entry of the form $(t^{\vdash}, t^{\dashv}, Ptr_p, Ptr_c)$. $Ptr_c$ is a pointer to record $rd_c$, and $Ptr_p$ points to record $rd_p$ that is $o$'s previous record in $OTT$. A non-leaf leaf entry is of the form $(t^{\vdash}, t^{\dashv}, cp)$, where $cp$ is a pointer to a child node and $[t^{\vdash}, t^{\dashv}]$ is the minimum bounding interval that contains all time intervals in the child node.
  \begin{sitemize}
    \item inactive at $t$ if $le.Ptr_p.t_e < t < le.Ptr_c.t_s$, $le.Ptr_p$($le.Ptr_c$) points to $rd_{pre}$ ($rd_{suc}$).
    \item active at $t$ if $le.Ptr_c.t_s \leq t \leq le.Ptr_c.t_e$, $le.Ptr_c$ points to $rd_{suc}$.
  \end{sitemize}
  }
\end{block}

\begin{block}{R-tree for POIs}
  \ssize{
  The set of indoor POIs is indexed by another R-tree, called $R_P$. The spatial index can be extended to multiple floors.
  }
\end{block}

\end{frame}

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

\begin{frame}
\frametitle{Snapshot Query Algorithms: Iterative Algorithm}

\begin{columns}[c]

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

  \column{.45\textwidth}
  \begin{fitemize}
      \item Lines 1--2: use a hash table $flows$ to keep flow values for all POIs.
      \item Lines 4--5: derive the uncertainty region $UR(o,t)$ for either an inactive states (Lines 6--9) or an active state (Line 11).
      \item Lines 12--14: all POIs that intersect $UR(o, [t_s, t_e])$ are founds and add the presence to each $p$.
  \end{fitemize}

\end{columns}

\end{frame}

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

\begin{frame}
\frametitle{Snapshot Query Algorithms: Join Algorithm (I)}

\begin{columns}[c]

  \column{.35\textwidth}
    \vspace{-18pt}
    \begin{figure}[tb]
      \includegraphics[width=\columnwidth]{figures/4-1/4-1-13.pdf}
    \end{figure}

  \column{.65\textwidth}
    Lines 1--11: build an in-memory aggregate R-tree $R_I$ for all objects whose augmented tracking interval covers query time $t$.
    \begin{sitemize}
        \item Line 5: if object is inactive, obtain the MBRs of the two proximity detection devices' detection ranges.
        \item Lines 6--8: extend each of them by the corresponding maximum possible distance (merge them to form the object's MBRs).
        \item Lines 10: otherwise, the MBR of device $dev_{cov}$'s detection range is used for active state.
    \end{sitemize}

\end{columns}


\end{frame}

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

\begin{frame}
\frametitle{Snapshot Query Algorithms: Join Algorithm (II)}

\begin{columns}[c]

  \column{.35\textwidth}
    \vspace{-18pt}
    \begin{figure}[tb]
      \includegraphics[width=\columnwidth]{figures/4-1/4-1-13.pdf}
    \end{figure}

  \column{.65\textwidth}
    Lines 12--18: the initialization for joining the POI R-tree $R_P$ and the aggregate object R-tree $R_I$.
    \begin{sitemize}
        \item Line 12: a priority queue $Q$ is initialized that gives higher priority to $R_P$ node entries (group of POIs) that potentially have higher flow values.
        \item Lines 13--18: when two tree roots are joined initially, the $count$ values in the $R_I$ entries are used to upper bound the flow values as an object's presence in any POI never exceeds 1.
    \end{sitemize}

\end{columns}


\end{frame}

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

\begin{frame}
\frametitle{Snapshot Query Algorithms: Join Algorithm (III)}

\begin{columns}[c]

  \column{.35\textwidth}
    \vspace{-18pt}
    \begin{figure}[tb]
      \includegraphics[width=\columnwidth]{figures/4-1/4-1-13.pdf}
    \end{figure}

  \column{.65\textwidth}
    Lines 19--48: the join phase.
    \begin{sitemize}
        \item Lines 20--21: the join order is controlled by priority queue $Q$.
        \item Lines 24--25: if the leaf node $e_P$'s join list is empty, the concrete flow value was calculated, add it to the result; terminate if $k$ have been found.
        \item Lines 28--32: otherwise, if the list contain leaf entries, derive the uncertainty region and presence for each object in the join list.
        \item Line 35: procedure expandList is called to join $e_P$ with sub-entries from the join list.
        \item Lines 37--43: if the current $e_P$ is non-leaf node and the join list contains leaf entries, the join algorithm overestimates the flow value for each of $e_P$'s sub-entries when joining them with the relevant entries.
        \item Lines 47--48: procedure expandList is called.
    \end{sitemize}

\end{columns}


\end{frame}

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

\begin{frame}
\frametitle{Snapshot Query Algorithms: expandList}

\begin{columns}[c]

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

  \column{.5\textwidth}
  \begin{fitemize}
    \item Line 4: $e_P$ is only associated with those $R_I$ entries whose MBRs intersect $e_P$'s.
    \item Line 5: uses the $count$ values in the $R_I$ entries to estimate the upper bound of $e_P$'s flow value.
  \end{fitemize}

\end{columns}


\end{frame}

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

\begin{frame}
\frametitle{Interval Query Algorithms: Iterative Algorithm}

\begin{columns}[c]

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

  \column{.45\textwidth}
  \begin{fitemize}
      \item Line 3: use a range query on A1R-tree to obtain the relevant leaf entries and objects that overlap the query time interval.
      \item Lines 4--6: a hash table to form the sequences for all objects obtained.
      \item Lines 8--9: the uncertainty region of each object is calculated.
  \end{fitemize}

\end{columns}

\end{frame}

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

\begin{frame}
\frametitle{Interval Query Algorithms: Join Algorithm}

\begin{columns}[c]

  \column{.38\textwidth}
    \vspace{-16pt}
    \begin{figure}[tb]
      \includegraphics[width=\columnwidth]{figures/4-1/4-1-16.pdf}
    \end{figure}

  \column{.62\textwidth}
    Basic Framework:
    \begin{fitemize}
        \item Lines 1--9: aggregate object R-tree $R_I$ construction.
        \item Lines 10--16: join initialization.
        \item Lines 17--46: join processing.
    \end{fitemize}
    \vspace{20pt}
    \fsize{
      \textrm{the differences here lie mainly in the first phase and in the details of deriving the uncertainty regions for objects in a join list in the third phase.}
    }

\end{columns}


\end{frame}

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

\begin{frame}
\frametitle{Interval Query Algorithms: Join Algorithm}

\textbf{Improvement 1: The Phase 1}

\vspace{15pt}

\begin{itemize}
  \setlength{\itemsep}{10pt}
  \item The uncertainty region in an interval query may involve considerable dead space compared to a snapshot query.
  \item Instead of using a single but large MBR to represent an object's trajectory during $[t_s, t_e]$, it uses a series of much tighter MBRs, each is created by two consecutive records.
  \item Insert the overall MBR to $R_I$ but maintain a pointer to link to all the small MBRs so that it would be easy to access all the small MBRs.
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Interval Query Algorithms: Join Algorithm}

\textbf{Improvement 2: The Procedure that expands the join list}

\vspace{15pt}

\begin{itemize}
  \setlength{\itemsep}{10pt}
  \item Instead of simply check whether two MBRs intersect, it does additional checks when a leaf node entry $e'_I$ is taken from $R_I$.
  \begin{fitemize}
    \item if $e'_I$ is a leaf node entry and its MBR intersects $e_P$'s, continue to check $e_P$'s MBR against the smaller MBR covered by $e'_I$ as described above.
  \end{fitemize}
  \item In similar fashion, apply the additional MBR intersection checks to the Join Algorithm  when it processes leaf entries from $R_I$.
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Interval Query Algorithms: Join Algorithm}


\begin{columns}[c]

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

  \column{.5\textwidth}
  \begin{example}
    \footnotesize
    Object $o$'s overall MBR, whose dead space is indicated by the shaded parts, overlaps a POI $p$, and therefore $o$ is included in $p$'s join list initially. If we represent the overall MBR with three smaller MBRs, each of which bounds the ellipse corresponding to a pair of consecutive tracking record. $o$ will be excluded from $p$'s join list if using the smaller MBRs.
  \end{example}

\end{columns}

\end{frame}

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

\begin{frame}
\frametitle{Conclusion}

\begin{itemize}
  \setlength{\itemsep}{15pt}
  \item Two types of queries to find the top-$k$ frequently visited indoor POIs, the snapshot and interval query.
  \item Appropriate ways to quantify how frequently an indoor POI is visited by probabilistically counting objects' presences in the POI.
  \item Algorithms for both defined types, a detailed analysis on the uncertainty region of indoor moving objects.
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Future Work}

\begin{enumerate}
  \setlength{\itemsep}{15pt}
  \item To consider an object's dwell time when calculating its interval presence in a POI.
  \item To extend the uncertainty analysis to support multiple floors. The challenge is to track object's movement between floors.
  \item To investigate how to solve the problems addressed in the paper using other types of indoor tracking data.
  \item To develop techniques for finding the current crowded indoor POIs by using tracking data.
  \item To evaluate the query results against real indoor POIs in order to see how effective the algorithms are.
\end{enumerate}

\end{frame}