We report on event recognition within the life logging application IYOUIT for the automatic creation of static diary-like Blogs. Based on the qualitative context histories produced by IYOUIT, we developed pragmatic event modeling and recognition techniques using technology available today. Our approach combines Description Logics with queries and rules to model event recognizers in terms of context ontologies and Allen's temporal interval algebra. We found the ability to efficiently compute Allen relations between events to be crucial for the performance and scalability of the whole approach. Therefore, we evaluate a set of modeling alternatives and give some practical guidance.
Social Web applications like Facebook and Twitter allow people to socialize over a
distance by sharing notes, photos and other personal information with their buddies or the
public. By automating the data gathering via the mobile phone, the IYOUIT4 system
is realizing a sophisticated life logging platform [
To increase the level of abstraction, IYOUIT uses knowledge formalized as OWL
DL ontologies to classify qualitative context w.r.t. situation concepts [
We are assuming familiarity with basic DL notions and Semantic Web query
languages [
Previous work introduced the notion situation [
In order to recognize a situation, defined concepts are exploited, e.g., a business
meeting could be detected with a defined concept such as business meeting _ 3
near by :colleague u 9at place:o ce. Such concepts are called recognizer concepts
in the following. Whereas simple situations can be recognized in the ABox by means
of recognizer concepts, exploiting the standard instance realization service, we prefer a
slightly different representation of situations in the ABox, as in
fsit : situation; (sit; val1) : CA1; val1 : CV 1; : : : ; (sit; valn) : CAn; valn : CV ng
because this more explicit representation allows us to exploit a – concerning the
relational expressivity – much more powerful recognition mechanism, namely grounded
queries and rules.6 Due to the explicit individuals, a standard grounded conjunctive
query [
A NRQL rule is basically a NRQL query, but the query head predicate ans is
replaced by a so-called generalized ABox, which is an ABox whose assertions may
reference variables from the body of the rule. The rule conclusion hateful meeting (x)
would add the concept assertion sit : hateful meeting given the binding x = sit
satisfies the rule body. Similar effects can be achieved in SWRL or SPARQL (using
construct). But unlike SWRL or SPARQL, NRQL also allows to introduce new
ABox individuals. This feature will be exploited in the following. Even more important
in our scenario, NRQL offers some form of epistemic first-order queries [
We call the IYOUIT component which creates an ABox representing the accumulated context data per day the Day Description Generator (DDG) and the generated ABox the Day Description ABox (DDA). The DDG is an external program outside of 5 We are using distinct CA ontologies instead of one big ontology for reasons of modularity. 6 A query can be considered as a special rule whose conclusion consists of a single ans head predicate. the DL system. Whereas in many cases, the value concept is explicitly asserted via vali : CV , sometimes ABox realization and thus inference is required to recognize the CV s. To facilitate this kind of CV inference, the DDA not only contains situation descriptions, but also user profile data, e.g., the social network of a user, as well as other mostly static information, e.g. home country, typical office hours, etc. 3
In [
b) How to define event recognizers?
c) Where do events come from?
Note that we are only interested here in technology that builds on existing DL or OWL
reasoners (such as RACERPRO) to get a working system with good performance today.
Regarding a), the least “ontological commitment” we can make is saying that we want
to represent actual events in the ABox which satisfy the following axiom:
event _ 9start state:state u 9end state:state
We simply state that an event is an “aggregate” which has a start state and an end state,
and that states are basically the situations just described, but augmented with some
temporal information which allows to determine the temporal order between states.
We assume a linear discrete time model, e.g. (IN; <). There are various options for
the representation of the temporal relations between the states; these options will be
discussed in the next section. It is also assumed that start state < end state holds,
for all events. In addition, complex events are composed of (one or several) subevents:
complex event _ event u 9has part :event
Non-complex events are called simple events. Two important specializations are change
events and constancy events. The former witnesses a change of some CV value of some
CA from start state to end state, e.g., if the value of CA = at place changes from
CV = home to CV = o ce, then this change will be reflected by a home2o ce
change event. The witnessing end state should be the smallest successor w.r.t. the
temporal order <. Hence, a change event should have a minimal temporal duration. In
contrast, a constancy event should have maximal duration, and must also be homogeneous
[
By exploiting the epistemic first-order properties of NRQL, maximal and homogeneous events for some some condition are recognized by the following query: ans(s1; s2) state(s1); state(s2); future(s1; s2); some condition(s1); some condition(s2); n (s1) (state(s0); next (s0; s1); some condition(s0)); n (s2) (state(s3); next (s2; s3); some condition(s3)); n (s1; s2) ( state(s3); future(s1; s3); future(s3; s2);
nsome condition(s3))
We assume that future holds between s1 and s2 iff s1 precedes s2 on the time line,
i.e. s1 < s2, and next between s1 and s2 iff s2 is the direct successor of s1 w.r.t.
<. The n is the NAF operator, and is the projection operator. The semantics of
these operators if formally exemplified in terms of FOPL just below. The n : : :
construction realizes a first-order epistemic closed-domain quantifier. The first n : : :
ensures maximality of the interval to the left, the second occurrence maximality of the
interval to the right, and the third occurrence verifies homogeneity, i.e., there is no
state s3 in between s1 and s2 for which one cannot prove some condition, hence,
nsome condition(s3) shall not hold. Note that replacing nsome condition(s3) by
:some condition(s3) would be too strong, since absence of some condition(s3)
does not imply :some condition(s3). We refer to [
The semantics of the NRQL query above is given by evaluating the following firstorder query over the relational structure SA=( I ; CI ; :::; RI ; :::), with I = inds(A), CI = f i j i 2 inds(A); A j= C(i) g , RI = f (i; j) j inds(A); A j= R(i; j) g; for all relevant roles R and all relevant (not only atomic!) concepts C. By construction of SA, NAF negation (n) can be replaced by classical negation (:) as follows, and the universal quantifications :9 : : : stemming from the n : : : occurrences become apparent: f (s1; s2) j 9s1; s2 : state(s1) ^ state(s1) ^ future(s1; s2) ^ some condition(s1) ^ some condition(s2) ^ :9s0 : state(s0) ^ next (s0; s1) ^ some condition(s0) ^ :9s3 : state(s3) ^ next (s2; s3) ^ some condition(s3) ^ :9s3 : state(s3) ^ future(s1; s3); future(s3; s2) ^
:some condition(s3) g Events can be recognized by recognizer concepts, queries or rules. Recognizer concepts solely rely on the ABox individual realization service and thus on explicit ABox individuals and relations between them, which need to be, at least to some extent (modulo inference), explicitly given in the ABox in forms of role assertions, since, with the exception of transitive relations, OWL DL offeres no defined roles. In addition to taking the obvious inferred role assertions into account, a NRQL rule can easly add new ABox (role) assertion, or even introduce new individuals. Moreover, intensional relation are available for queries and rules by means of so-called defined queries which are similar to intensional database relations defined as Datalog rules. For example, the binary recognizer rule for the Allen relation before before(x; y)
event(x); event(y); end state(x; s1); start state(y; s2); future(s1; s2) can either be understood as a rule which adds (“materializes”) before role assertions to the ABox, or as a definition of the query before (i.e., a “query macro”) which is expanded and replaced by its definition whenever it is referenced in some other query body, e.g., in an event recognizer query or rule.7 Hence, a query or rule body referencing before does not necessarily require explicit before role assertions in the ABox, but can work with implicit before relations. As a result of the body expansion, the bodies of the referencing rules can get very complex and become demanding for the query optimizer and processor (an exponential blowup is possible). Defined queries must be acyclic in NRQL. If recursion is required, NRQL rules have to be used instead, and a rule application strategy has to be provided (see below).
In principle it is possible to define complex event recognizers as defined queries rather than rules. But, as there would be no ABox individual representing the complex event itself, these queries would either be n-ary predicates (returning the n subevents which make up the complex event), or binary predicates such as ordinary o ce day (s1; s2) on the states s1 and s2. The n-ary solution is obviously bad, and the binary solution makes it impossible to refer to the individual subevents – only the states would be available (which are obviously required for the computation of Allen relations between the complex event and the other events). Consequently, also the simple events should be modeled as binary predicates. To sum up, this results in an entirely different modeling and is thus not considered further in this paper. Even Allen relations could no longer be understood as roles holding between events, but would become quadrary defined queries for pairs of endpoints of events.
Summary: In principle, Allen relations as well as the events can be recognized by rules
or defined queries. As we want events to be represented explicitly in the ABox, the
later option is dissatisfactory for recognizing events. Recognizing Allen relations
via defined queries was also already investigated in [
Approach 1: Pre-Constructing Events The set of states of a given day is finite. Therefore, one might ask whether it is an option to pre-construct all possible events in the DDA and to rely as much as possible on standard ABox individual realization for the classification of events. For n states, there are at most m0 = n(n 1)=2 simple events. Hence, there are at most 7 This does not work in concepts, e.g., 9before: : : : would not be aware of the defined query. m1 = P2 k m0 mk0 = 2m0 m0 1 complex events that can be constructed from these m0 simple events. These events can in turn become subevents of more complex events, and so on. For 3 states, we already get 120 events for m0 + m1 + m2, and 1329227995784915872903807060280344455 events on the next level. The set of preconstructible events is in fact infinite, but it may be possible to compute an upper bound based on the definitions of the recognizers. Although it seems reasonable to stop at, say, level 3, still the constructed ABoxes are not manageable. With the more realistic assumption of approx. 30 states per day and user in case of IYOUIT, already level 1 becomes infeasible. Even worse, mi2 additional Allen relations have to be asserted.
Since all relevant event aggregates are already explicitly present in the ABox, recognizer concepts become possible:
home2o ce _ 9start state:9at place:home u 9end state:9at place:o ce Unfortunately, certain important event properties, such as maximality and homogeneity, cannot be expressed with concepts. But at least for the basic context attribute values that require no reasoning, these properties can directly be assured and asserted by the DDG.
In most cases, recognizer concepts are insufficient for the representation of complex events. The main limitation is the inability of concepts to describe anything else but tree structures (regarding the role successors). For example, it is impossible to specify that during an in o ce event, a meeting with boss event occurred directly before (meets relation) an meeting with customer event. A modeling attempt: stressful o ce day _ 9has part :( in o ce u 9during 1 :( meeting with boss u
9meets:meeting with customer u : : :))
Obviously, this definition has the defect that it cannot be taken for granted that the
meeting with customer event still takes place during the in o ce event. Other
attempts to define such a concept will have similar defects. Although it is impossible to
fix the start state and end state by means of existentials, the temporal duration of the
complex event as well as the Allen relations to other (possibly complex) events are in
fact known, since the aggregate was constructed by the DDG which asserted start state
and end state. This motivates the has part role. Without the additional individual
representing the complex event, start and end state of the aggregate could not be fixed, and
consequently, Allen relations could not be computed. Moreover, one of its subevents
would have to act as a proxy for the whole aggregate [
Although many temporal constellations between subevents cannot be reliably
recognized with defined concepts since a lot of false positives will be detected, some
complex events can indeed be realized in that way, e.g., those complex events for whose
description a tree-like temporal Allen network is sufficient. Another required provision
to minimize the amount of false positives is that one has to restrict the visibility of Allen
relation successors to those events which are part of the same aggregate – otherwise
the traversal of an Allen role assertion R via 9R: : : : could lead into an event being
subevent of some other complex event, yielding another false positive. However, this
forces the DDG to create copies of subnetworks in order to isolate ABox individuals in
different events and thus increases the ABox size by an additional order of magnitude.
Hence, the approach does not seem reasonable.
Again, a query or rule can help to overcome the expressivity problems:
stressful o ce day(x)
has part (x; p1); has part (x; p2); has part (x; p3);
in o ce(p1); meeting with boss(p2);
meeting with customer (p3);
meets(p2; p3); during(p2; p1); during(p3; p1)
Summary: For complex events, the pre-construction by the DDG causes two
problems. First, the number of precomputed events and Allen relations gets enormous,
and second, it is not always possible to define reasonable expressive recognizer
concepts for complex events. The latter point is not resolvable unless specialized
temporal logics are used, or certain OWL extensions are accepted [
Approach 2: Constructing Events on Demand
In contrast to the approach just described, the other extreme is to have no pre-constructed
events at all in the DDA, but only states with their temporal relations. As a consequence,
the number of recognizer rules gets very large, and rule management becomes an
important issue. The first-order capabilities of the NRQL rules are a big advantage in this
setting. We already demonstrated how to recognize maximal and homogeneous events.
Since only states together with their temporal relations are present in the DDA, non-safe
rules which can introduce new event individuals have to be used. NRQL offers the new
operator that can be understood as a (FOPL) function symbol. A typical basic event
recognizer rule constructing event instances, looks as follows:
start state(new (e; s1; s2); s1); end state(new (e; s1; s2); s2); event (new (e; s1; s2))
state(s1); state(s2); future(s1; s2); : : :
For example, given states s1 = i; s2 = j, it constructs the ABox assertions
fei;j : event ; (ei;j ; i) : start state; (ei;j ; j) : end stateg: Non-safe rules are in
principle subject to termination problems, since new individuals are introduced (on which
rules may fire which introduce individuals, on which rules may fire which introduce
individuals, on which . . . ). In NRQL, this termination problem is delegated to the
client program which has to drive the rule application, since NRQL does not offer
an automatic rule application strategy. The client program thus has to run a loop of
the form “while (applicable-rules()) fexecute-applicable-rules();g”
calling the NRQL rule API functions. Hence, all possible termination problems are
caused by the client which runs the loop. Using NRQL’s non-monotonic features, even
non-safe individual constructing rules can be written in a way which ensures
termination.8 For example, the above rule can disable itself after all constructible events have
been constructed by adding the following conjunct to its precondition:
n (s1; s2) (event (x); start state(x; s1); end state(x; s2))
8 Note that this would not be possible in a monotonic rule language such as SWRL.
The need for an external client program driving the rule application can be seen as a
drawback. However, recently the MINILISP functional expression language for
serverside programming has been added and reached a mature state [
The recognizer rules for complex events look very similar to the stressful o ce day example rule already given above. However, its conclusion has to construct a new event individual and also cannot rely on has part (x; p) for its parts p in the precondition. Note that for each freshly constructed event, the corresponding Allen relations have to be computed. The universal closed-domain quantifier of NRQL is also important for complex event recognizer rules, since the maximality and the absence of certain other events between two subevents has to be enforced.
From a theoretical perspective, this approach is the cleanest and most powerful one.
Only events which have actually been recognized are constructed, in contrast to the
previous approach, where also all kinds of meaningless events are pre-constructed. The
approach described in this section was also chosen in [
Summary: Constructing events with non-safe rules is conceptually very clean. The whole process is driven solely by the ontology (considering rules being part of the ontology). But, this approach does not perform well with current state-of-theart technology. The number of rules becomes very large and thus issues not wellsupported by current DL systems (e.g., rule management) become predominant. Furthermore, Allen relations can no longer be computed in advance by the DDG, but rather have to be recomputed after each rule application cycle. 3.3
Approach 3: The Best of Both Worlds Having analyzed both extremes, we proceed as follows. The DDG pre-constructs all relevant simple events, and only the complex events as well as those simple events whose recognition requires ontology reasoning are constructed via rules. Note that the Allen relations can already be asserted by the DDG for those pre-constructed events. In addition, Allen relations must be computed dynamically after each rule application cycle.
For every s1, s2, CA and CV , the DDG pre-constructs a simple event if and only
if time(s1) < time(s2), the event is homogeneous, and has a maximal temporal extent
w.r.t. the CA CV attribute-value pair. In case the recognition of CA CV requires
reasoning, the event cannot be pre-constructed, and recognition rules (or concepts) have
to be written. In the current IYOUIT scenario, recognizer rules are only required for
complex events. The number of simple events is bounded by jCAjjCV jn(n 1)=2,
where n is the number of states. Since all simple events in the DDA are now maximal
and homogeneous, it becomes reasonable to attach the CA attributes to the event
individuals instead of the states, and use them as primitives instead of the states. For every
possible CA CV pair, a simple event recognizer concept is defined:
eventCA;CV _ event u 9CA:CV :
Consequently, the CV taxonomy is automatically inherited to the taxonomy of
simple events (something we would not get automatically with recognizer rules, although
NRQL is able to compute query and rule subsumption [
The DDG does not pre-construct change events. Their absence is not really a drawback. They can still be recognized, e.g. the change of CA from CV1 to CV2 can be detected with a rule such as : : :
eventCA;CV1 (e1); eventCA;CV2 (e2); meets(e1; e2) if required. Still, some code is needed to drive the rule application. The remarks from the previous paragraph apply.
Summary: This approach seems promising and combines the best of both worlds. It keeps the number of rules maintainable, allows to employ defined concepts as recognizer for simple events and does not lose expressivity. As for the previous approach, the efficient computation of Allen relations is very important. 4
Since the set of states is fixed, the DDG can precompute the temporal order between any
two states by means of role assertions using the roles next ; equal (with next _ prev 1),
and a transitive superrole future, next v_ future, future+ _ future, past _ future 1.
Note that the explicit relation representation in terms of next and equal requires n +
n(n 1)=2 role assertions (and even more if also prev , future and past are made
explicit in case one wanted to get rid of the TBox axioms for the roles). Alternatively, the
DDG can attach a filler of the concrete domain (CD) attribute time to each state. A
NRQL rule can make the next relation explicit, or a defined query could be used:
next (s1; s2)
< (time(s1); time(s2));
n (s1; s2) (< (time(s1); time(s3)); < (time(s3); time(s2)))
The <-atom is a so-called CD constraint checking atom. While the evaluation of this
atom requires concrete domain unsatisfiability checks which may be expensive, there is
also a cheaper option in NRQL, a so-called data substrate query which can check such
constraints on a set of data literals much faster by model checking some data substrate
structure [
In case next is materialized, we also automatically get the relations prev , future, and past , due to the role declarations. However, if the rule is used as a defined query, then some more definitions are required for the other roles, e.g. for future we can simply remove the “n : : :” line from the next definition. The implicit and intrinsic relations between states keep the ABox small in number of role assertions, they are thus worth of
Allen 1
Allen 1 Allen 2 Allen 3 Allen 4 1 10 15 20 25 30
Intervals 35 40 45 50 55 consideration, and should be subject to a benchmark. On the other hand, the explicit relation representation requires bigger ABoxes, but have the benefit to also provide index structures for query answering, and moreover can be used to avoid repeated computations of relations. It is not clear how to proceed without an evaluation of the alternatives. Allen relations are computed from the relations between the states of the events, as already explained in terms of the before relation. The ability to efficiently compute Allen relations is crucial for the performance and scalability of the whole approach. Thus, for the benchmark, we are first evaluating the performance of the Allen computation. A DDA with 50 random intervals is created, which is reduced to 40 intervals by removing 10 intervals, and so on, until only 10 intervals remain. We are considering four different settings for the benchmark:
(one rule per Allen relation and its converse)
Allen 2: implicit state relations via defined query next and CD atom <
Allen 3: implicit state relations via defined query next and data substrate atom <
Allen 4: implicit state relations and computation of the Allen relations with one rule
instead of 7, by means of a MINILISP expression which analyzes the values of the
time attributes of the states of the events e1, e2 and computes the corresponding
Allen relation programmatically (with a simple conditional expression expr that
we do not explicate here in more detail):
(e1; e2) expr
event(e1); event(e2)
While lots of temporal logics have been designed [
In future work, alternative (but implemented) approaches should be checked out,
e.g., instead of using unsafe rules, recent progress regarding multimedia and image
interpretation with horn rules in an abduction framework shall be exploited [
Regarding IYOUIT, there are open challenges. To exploit events for the offering of
context dependent services on a mobile phone, the events have to be recognized
incrementally and online, not offline [