Database Reference
In-Depth Information
r
1
a
,
r
1
b
,
r
2
a
,
r
2
b
:
q
0
l
a
,
l
b
:
q
λ
q
1
q
2
r
1
a
,
r
1
b
:
1
r
1
a
,
r
1
b
:
r
2
a
,
r
2
b
:
r
2
a
,
r
2
b
:
2
Figure 6.3:
An example transducer that detects the sequence of rooms that a crash cart has visited (see
Example
6.6
).
string
value
probability
output
s
r
1
a
l
a
l
a
r
1
a
r
2
a
0
.
567
12
t
0
.
007
r
1
a
r
1
a
l
a
r
1
a
r
2
a
12
u
l
a
r
1
b
r
1
b
r
1
a
r
2
a
0
.
002
12
v
0
.
0315
2,1
,λ
r
1
a
l
a
r
2
a
r
1
b
l
b
w
r
1
b
r
1
b
l
a
l
b
l
b
0
.
0032
x
r
1
a
r
1
a
r
2
b
r
1
b
r
1
b
0
.
007
N/A
Figure 6.4:
Random strings of the Markov sequence
μ
of
Figure 6.2
, their probabilities, and the output
strings into which they are transduced.
Sequence with probability 0
.
567. On this run, the first reading is in a room, and so the crash cart
has not yet visited a lab. Thus, the transducer remains in
q
0
and emits an empty string. Then, the
crash cart does visit a lab followed by a sequence of rooms 1 and 2. Hence, the transducer emit
1, 2
on this run.
This simple transducer already exhibits some of the challenges in query evaluation. First, there
may be a huge number of possible answers (sequences of rooms) with different probabilities, and it
may well be the case that most of the answers have a confidence that is too low to be of interest.
Second, many possible worlds of the Markov sequence can result (i.e., be transduced into) the same
answer, as such worlds may differ in the duration of staying at each room as well as the different
sub-locations inside each room (e.g., the main area versus the restroom). Initially, the
LAHAR
system
processed a restricted subset of alert queries. Only recently have the algorithms for more sophisticated
queries been discovered [
Kimelfeld and Ré
,
2010
].
