Database Reference
In-Depth Information
1.0
0.2
0.1
1.0
0.4
0.5
0.1
0.9
0.9
0.2
0.3
0.2
0.2
1.0
Figure 6.2:
A Small Markov Sequence from RFID. Figure from
Kimelfeld and Ré
[
2010
].
In our example, we consider the transmissions of a specific crash cart. Based on the relevant
transmissions, a prediction of the location of the cart at each point in time is made. Note that an
actual location of the cart is typically uncertain, for several possible reasons. For instance, physical
limitations may lead to erroneous reads or, more commonly, missed readings. As another example,
the locations of sensors can easily introduce ambiguity (e.g., sensors located near passages or close
sensors that simultaneously read the same signal). More subtly, the antenna readings themselves are
at a very low-level, and there may be no 1-1 mapping to higher-level events, e.g., the same sequence
could correspond to entering either of Room 1 or Room 2. Such a prediction is done by viewing the
transmissions as a sequence of observations in a
hidden Markov model
(HMM) and translating this
HMM into a Markov sequence.
Figure 6.2
shows a tiny example
μ
of the resulting Markov sequence. In this figure, we consider
two rooms, numbered 1 and 2, and a lab. Each of the three contains two locations (each has a sensor).
For example, Room 1 has sensors in locations
r1a
and
r1b
, and the lab has sensors in locations
la
and
lb
. The set
μ
of state nodes comprises the six locations (i.e.,
r1a
,
r1b
, etc.). The states are
represented by rectangles (with rounded corners). The functions
μ
0
→
and
μ
i
→
are represented by
directed edges that are labeled with probabilities. Note that some edges are missing, and we implicitly
assume that they have a zero probability. As an example,
μ
0
→
(
r1a
)
=
0
.
7 is indicated by the upper
edge emanating from the filled circle on the left. As another example,
μ
3
→
(
la
,
lb
)
=
0
.
1 is indicated
by the edge from the
la
rectangle to the
lb
rectangle between variables
S
3
and
S
4
(which we discuss
later). Note that the sum of edges emanating from each object is 1 (as we require in a Markov
sequence).
Continuing the previous example, a hospital administration can now ask queries to monitor
the operation of the hospital without having to make reference to low level antenna readings. For
example, we want to detect the sequence of rooms that a crash cart has visited (e.g., to detect a source
of infection). This query is cumbersome to express in SQL because it requires that we combine events
from several points in time. Instead, sequential probabilistic data management systems use languages
that make it easy to specify sequential relationships.
