Scalable Maintenance of Knowledge Discovery in an Ontology Stream

1 Introduction and RelatedWork

Rules are incrementally learnt through approximate specialization. Although such models fits (raw) data streams exposing (syntactic) numeric/symbolic values, they could not cope with semantics captured by ontology streams. Indeed they all fail in interpreting the underlying semantics of data, making knowledge discovery highly subject to changes, and not necessarily accurate, scalable. Facing these limitations, techniques from Knowledge Representation and Reasoning explored ontology-based learning for generating DL axioms [V¨olker and Niepert, 2011], Horn rules [Gal´arraga et al., 2013], DL rules [L´ecu´e and Pan, 2015] from semantic data. All rules are mined from scratch for each update, which is ineffective since it (i) restricts the dynamics of (stream) learning, (ii) neglects previously discovered rules, (iii) intolerably limits its scalability, adaptability and reactivity.

In the semantic Web, the meaning of data streams is represented as ontology streams [Huang and Stuckenschmidt, 2005]. Such streams are dynamic and evolutive versions of ontologies where OWL (Web Ontology Language), which is underpinned by Description Logics (DL) [Baader et al., 2003], is used as a rich description language. From knowledge materialization [Barbieri et al., 2010], to diagnosis or predictive reasoning [L´ecu´e and Pan, 2013], all are inferences where dynamics, semantics of data are exploited for deriving a priori knowledge from pre-established (certain) statements.

From a data-driven perspective, knowledge can be gained a posteriori from uncertainty by learning probabilistic rules or associations across streams [Agrawal et al., 1993]. When a priori and a posteriori knowledge are reunified, the problem of knowledge discovery can be revisited as the problem of discovering stochastic rules with semantic representation of their premises, conclusions [L´ecu´e and Pan, 2015]. In a dynamic context, with highly changing data, it is crucial to ensure scalable knowledge discovery by adjusting and updating all learnt semantic rules rather than re-elaborating potential associations from scratch (exponential in the size of data).

Most of techniques in Database e.g., [Cheung et al., 1996], adapting Apriori [Agrawal et al., 1996] for streams, focus on syntactic representation of data to iteratively identify frequent associations. [Lee et al., 2003] improved its scalability by partitioning all streams using a sliding-window filtering. Approaches in Machine Learning e.g., [Gama and Kosina, 2011] focus on learning decision rules, as a subset of association rules, for classifying data from streams in real-time.

We address "scalable maintenance of knowledge discovery in dynamic semantic data". Given ontology streams, how to ensure scalable identification of dynamic, knowledge associations? This poses problems of dynamically maintaining associations and their interestingness up-to-date in a window sliding over streams. Key contributions include: (1) By exploiting the semantics of ontology streams, we introduce the notions of knowledge similarity, rarity over time, which are logically based and do not only rely on the syntax of axioms. They enable approximation of knowledge discovery while maintaining accuracy. (2) We design the first incremental algorithm which controls the scalability of learning by efficiently maintaining DL rules, as associations across streams.

Next section reviews the adopted logic, ontology stream together with rules representation. In Section 3 we study knowledge similarity and rarity in streams. Section 4 presents how knowledge discovery is incrementally maintained. Finally, we report experimental results on scalability and accuracy with data from Dublin City and draw some conclusions.

2 Background

The semantics of data is represented using an ontology. We focus on DL to define ontologies since this logic offers good reasoning support for most of its expressive families and compatibility to W3C standards e.g., OWL 2. Since our work requires DLs supporting polynomial time reasoning when combined with rules, EL++ [Baader et al., 2005] will be considered for illustration. We review (i) DL basics of EL++, (ii) ontology stream, (iii) EL++ atomsets and association rules.

Figure 1: O .= 〈T ,A〉. Sample of TBox T and ABox A.

2.1 Description Logics EL++

A signature Σ, noted (NC , NR, NI ) consists of 3 disjoint sets of (i) atomic concepts NC, (ii) atomic roles NR, and (iii) individuals NI . Given a signature, the top concept ⊤, the bottom concept ⊥, an atomic concept A, an individual a, an atomic role expression r, EL++ concept expressions C and D in C can be composed with the following constructs:

The DL ontology O .= 〈T ,A〉 is composed of TBox T , ABox A. A TBox is a set of concept, role axioms. EL++ supports General Concept Inclusion axioms (GCIs e.g. C ⊑ D), Role Inclusion axioms (RIs e.g., r ⊑ s ). An ABox is a set of concept assertion axioms e.g., C(a), role assertion axioms e.g., R(a, b), individual in/equality axioms e.g., a ̸= b, a = b.

Example 1. (TBox and ABox Concept Assertion Axioms) Figure 1 presents (i) a TBox T where DisruptedRoad (??) denotes the concept of "roads which are adjacent to an event causing high disruption", (ii) concept assertions (??-??) denoting the individual r0 having ri,1≤i≤2 as adjunct roads.

All completion rules, which are used to classify EL++ TBox T and entail subsumption, are described in [Baader et al., 2005]. Reasoning with such rules is PTime-Complete.

2.2 Ontology Stream and its Evolution

We represent knowledge evolution by a dynamic, evolutive version of ontologies [Huang and Stuckenschmidt, 2005]. Data (ABox), its inferred statements (entailments) are evolving over time while its schema (TBox) remains unchanged.

Definition 1. (DL L Ontology Stream)

A DL L ontology stream P nm from point of time m to point of time n is a sequence of (sets of) Abox axioms (P nm(m),P nm(m + 1), · · · ,P nm(n)) with respect to a static TBox T in a DL L where m, n ∈ N and m< n.

P nm(i) is a snapshot of an ontology stream (stream for short) P nm at time i, referring to ABox axioms with respect to a TBox in L. We denote by P nm[i, j] i.e., ⋃jk=i P nm(k) a windowed stream of P nm between time i and j with i < j. All windows [i, j] have fixed length. We consider streams P n 0 with [α] .= [i, j], [β] .= [k, l] as windows in [0, n] and i < k.

Example 2. (DL EL++ Ontology Stream)

Figure 2 illustrates EL++ streams P 9 0 , Q90 , R90 , related to events, travel time, buses, through snapshots at time i ∈ {5, 6, 7} (i.e., a view on window [5, 7]). Their dynamic knowledge is captured by evolutive ABox axioms e.g., (??) captures e1 as "a social music event occurring in r1" at time 5 of P 9 0 .

By applying completion rules on static knowledge T and ontology streams P n 0 , snapshot-specific axioms are inferred.

The evolution of a stream is captured along its changes i.e., new, obsolete and invariant ABox entailments from one windowed stream to another one in Definition 2.

Definition 2. (ABox Entailment-based StreamChanges) Let S n 0 be a stream; [α], [β] be windows in [0, n]; T be axioms, G its ABox entailments. The changes occurring from S n 0 [α] to S n 0 [β], denoted by S n 0 [β]∇S n 0 [α], are ABox entailments in G being new (1), obsolete (2), invariant (3).

(1) reflects knowledge we gain by sliding window from [α] to [β] while (2) and (3) denote respectively lost and stability of knowledge. All duplicates are supposed removed. Definition 2 provides basics, through ABox entailments, for understanding how knowledge is changing among windows.

Example 3. (ABox Entailment-based StreamChanges) Table 1 illustrates changes occurring from (Q∪R)90 [5, 6] to (Q∪R)90 [6, 7] through ABox entailements. For instance "r2 as a road with (at least) one congested bus" in window [6, 7] of (Q∪R)90 is invariant with respect to knowledge in [5, 6]. It is entailed using DL completion rules on (??), (??) and (??).

2.3 EL++ Atomsets and Association Rule

We consider EL++ with (i) concept expressions C, role names NR, individual names NI, and (ii) a countable set of first-order variables V.

Atomset: Given terms x1, x2 ∈ V ∪ NI, a concept (role) atom is a formula C(x1) (R(x1, x2)) with C ∈ C (R ∈ NR). We use finite sets (atomsets) B of (concepts, roles) atoms for representing conjunction ∀⃗x. ∧ B where ⃗x .= x1, · · · , xn ∈ V are variables of atoms B ∈ B which could be shared. ξ(A) denotes the set of all atomsets generated from atoms in A w.r.t T . By abuse of notation, we continue to write A for ξ(A).

Atomset Binding: Atomsets can be seen as conjunctive queries [Glimm et al., 2007] without non-distinguished variables. We write T ,A |= B[⃗a] to denote that ⃗a ∈ NI is a binding (answer) to atomset (query) B.

Example 4. (Atomset and Binding)

r0 is a binding to atomset {adj(x, r1)} w.r.t. O in Figure 1.

EL++ Rules [Kr¨otzsch et al., 2008] extends EL++ expressivity with rules while maintaining polynomial time reasoning. Given atomsets B, H, and all variables ⃗x ∈ V of atomset B ∪ H, an EL++ rule is a formula B ↠ H, such that B is cycle free and does not contain atom of the form R(x, x).

Example 5. (EL++ Rule)

Below rule denotes "if x3 is adjacent to a x2 where a highly disruptive event x1 occurs then buses are congested in x3".

Association EL++ Rules [L´ecu´e and Pan, 2015] are EL++ rules defined across some associations of axioms in streams. They extend Database association rules [Agrawal et al., 1993] as knowledge from different streams is associated and combined by learning rules. Such rules are modeled in EL++.

Example 6. (Association EL++ Rule)

{(4), (5)} ↠ {(6)} is an association rule from P 9 0 toQ90 ∪R90 . (4-5) are defined in P 9 0 , (6) is inferred fromQ90 ∪R90 .

3 Significance of Knowledge Evolution

We introduce knowledge similarity and rarity, as basis for (i) measuring the significance of knowledge evolution in streams and (ii) controlling when to operate knowledge discovery.

3.1 Knowledge Similarity in An Ontology Stream

Definition 3 revisits stream correlation [L´ecu´e and Pan, 2013] to capture knowledge similarity over windowed streams. It captures what knowledge, through ABox entailments, is common or modified (new or obsolete) over two windows.

Definition 3. (Knowledge Similarity in Ontology Stream)

Let S n 0 be a stream; [α], [β] be windows in [0, n]. The (symmetric) knowledge similarity between S n 0 [α] and S n 0 [β] is:

where the expressions in between | refer to its cardinality i.e., the number of new, obsolete and invariant ABox entailments obtained from S n 0 [α] to S n 0 [β] using DL completion rules.

(7) captures the knowledge similarity of windowed streams S n 0 [α], S n 0 [β] in [0, 1]. The number of invariant ABox entailments emphasizes "common" knowledge while the number of new and obsolete ABox entailments is capturing differentiators in knowledge evolution fromwindow [α] to [β]. Therefore the higher Φ(S n 0 [α], S n 0 [β]) the more similarity between knowledge captured in windows [α] and [β] of S n 0 .

Evaluating (7) is in worst case polynomial time with respect to acyclic T and S n 0 in EL++ since DL concepts expansion, unfolding and subsumption required from Definition 2 are all solvable in polynomial time [Baader et al., 2005].

Example 7. (Knowledge Similarity in Ontology Stream)

For (Q∪R)90 [6, 7]∇(Q∪R)90 [5, 6], all entailments in (Q∪ R)90 [5, 6] and (Q ∪ R)90 [6, 7], derived using DL completion rules, static knowledge (Figure 1), dynamic knowledge (Figure 2), are required. By applying their resulting numbers of 8 invariant, 4 new, 5 obsolete entailments in (7), knowledge similarity of (Q∪R)90 in [6, 7] with [5, 6] is 0.47 cf. Figure 3.

3.2 Knowledge Rarity in An Ontology Stream

Knowledge rarity or the state of knowledge of being infrequent, is a strong indicator of (i) knowledge representativity and thus of (ii) significance for knowledge discovery. Definition 5 revisits the concept of rarity for ontology streams as the proportion of its rare knowledge (Definition 4) i.e., knowledge occurring over a pre-determined number of snapshots.

Definition 4. (ε-Rare Knowledge in Ontology Stream)

Let S n 0 be a stream; T , A be static axioms; [α] be a window in [0, n]. An ABox assertion a is ε-rare in [α] for integer ε if:

where i is an instant in [α] and S n 0 (i) is a snapshot of S n 0 [α].

Assertion a is ε-rare if a can be entailed over ε snapshots of [α]. We denote by ε-rare(S n 0 [α]) the set of ABox assertions which are ε-rare in [α] of S n 0 , by |ε-rare(S n 0 [α])| its cardinality. Let |distinct(S n 0 [α])| be the number of distinct ABox assertions entailed in [α] of S n 0 . Thus, knowledge rarity is characterized by the ratio of rare to distinct ABox assertions.

Definition 5. (ε-Rarity of Knowledge in Ontology Stream) Let S n 0 be a stream; [α] be a window in [0, n] of S n 0 . The ε-rarity of knowledge in [α] of S n 0 is defined as the ratio:

1-rarity ϱ1 is the fraction of knowledge appearing uniquely in [α]. ε-rarity measures knowledge repeating ε times within [α]. Evaluating (9) is in worst case polynomial time cf. (7).

Example 8. (ε-Rarity of Knowledge in Ontology Stream) Suppose (Q∪R)90 over [6, 7] in Figure 2. ∃travel.Stop(r2) is 1-rare while ∃with.CongestedBus(r2) is 2-rare as they are respectively entailed in snapshots {7} and {6, 7}. Given the number of distinct, 1-rare and 2-rare knowledge being respectively 12, 4, 8 in [6, 7], 1-rarity and 2-rarity of knowledge in [6.7] of (Q∪R)90 are respectively 1/3, 2/3 cf. Figure 3.

We will apply (8-9) with atomsets in S n 0 rather than its ABox assertions, as they are representative of DL rules.

4 Incremental Maintenance of Knowledge

Scalable maintenance of knowledge in streams aims at keeping (discovered) association EL++ rules over a sliding window up-to-date rather than re-elaborating associations from scratch. Let S n 0 in Figure 4 be a set of streams that could be associated e.g., streams in Figure 2. ∆- , ∆+ are respectively knowledge removed and added by sliding from ∆-∪S to S∪∆+ while S captures what remains unchanged. The complexity of this problem is exponential in the number of atoms (to be composed by rules) in streams [L´ecu´e and Pan, 2013]. We present some heuristics, illustrated in Algorithms 1, 2 and 3, that drastically reduce computation time in practice. Our approach is: (i) updating the interestingness of rules R- discovered in ∆- ∪S, (ii) expanding rules R- to cover incoming knowledge ∆+ , (iii) actioning maintenance only when accumulated knowledge update is significant. The approach benefits from EL++ as consistency checking of atomsets, together with atomset binding are polynomial [Bienvenu et al., 2012].

4.1 Updating Interestingness of EL++ Rules

The interestingness of association EL++ rules is measured by the support of its atomsets and its confidence.

Definition 6. (Atomset Support)

Given axioms O .= 〈T ,A〉, stream S n 0 , atomset B. The support of B, noted σ(B), is defined by |{i ∈ [0, n] | ∃⃗a ∈ NI :O, S n 0 (i) |= B[⃗a]}| as the number of snapshots where B has at least a binding ⃗a in A ∪ S n 0 with respect to T .

We say that B is supported (or true) over σ(B) snapshots in [0, n] of S n 0 . The support of any atomset in a stream can be computed as the sum of its supports on windowed streams.

Definition 7. (Confidence of an Association EL++ Rule) Let ρ : B ↠ H be an association EL++ rule in S n 0 . The confidence γ of ρ, noted γ(ρ), in (0, 1] is defined by σ(B ∪ H)/σ(B) i.e., the proportion of snapshots in S n 0 where B ∪ H has at least one binding with regard to those where B has a binding.

The confidence is defined as the conditional probability of inferring H(⃗a) given that we know B(⃗a). We denote by σ(B)|S n 0 [α] and γ(ρ)|S n 0 [α] the support of atomset B and confidence of rule ρ in windowed stream S n 0 [α].

Example 9. (Confidence of an Association EL++ Rule) Let S 9 0 be (P ∪Q∪R)90 in Figure 2. The confidence of rule γ(B ↠ H) with B: {(4), (5)}, H: {(6)} in [5, 6] of S 9 0 is:

B ↠ H is bound in 1/2 of snapshots of S9 0 [5, 6].

Algorithm 1 (A1) updates interestingness of rules (learnt) in ∆- ∪S to be suitable in S. All (line 5) are evaluated against ∆- (line 7), the part removed by sliding from∆-∪S to S∪∆+ . If rules are applicable (lines 9-10), their support, confidence are updated. Otherwise ∆- does not impact the interestingness of rules, which remain the same (line 11).

Remark 1. (Rule Interestingness when Adding Snapshots) If snapshots ∆+ are added to S, the interestingness is updated by applying A1 with parameters 〈O, S n 0 ,∆+ , S ∪∆+ 〉, and upgrading (i) - to + in lines 9-10, (ii) ∆- ∪S to S.

Example 10. (Updating Interestingness of EL++ Rules)

By sliding from [5, 6] to [6, 7], the confidence of B ↠ H in Example 9 requires an update. B∪H and B are supported at time {6, 7}, {5, 6, 7}. Thus, removing ∆- : S 9 0 (5) from ∆- ∪ S : S 9 0 [5, 6] (lines 9-10) and adding ∆+ : S 9 0 (7) to S : S 9 0 (6) (lines 9-10 by applying Remark 1) update its confidence to 1.

4.2 Approximating Expansion of EL++ Rules

Algorithm 2 (A2) expands rules in S (output of A1) to S∪∆+ (lines 5-10). Atomsets in S (line 5) are expanded with atomsets in ∆+ if bindable (line 7). Such rules cover knowledge uniquely present in ∆+, not in S. Only ε-rare atomsets, with ε parameterizable in E ⊆ {1, ..., |S|}, are considered (line 5) to limit the search space. This benefits scalability while not sacrificing significant rules (rules with minimum support, confidence) cf. Section 5. Finally, all potential rules in S∪∆+ are evaluated against the minimum confidence (lines 8-10).

Algorithm 2: [A2]RuleExpansion〈O, S n 0 , S, ∆+ , E, γmin〉 1 Input: (i) Axioms O .= 〈T ,A〉, (ii) Streams S, S ∪∆+ in S n 0 , (iii) Integer ε ∈ E ⊆ {1, ..., |S|} with |S|: number of snapshots in S, (iv) Min. threshold of confidence γmin. 2 Result: R: Rules expanding S with ∆+ with min. thres. γmin. 3 begin 4 R← ∅; % Initialization of expanded rules R in S ∪∆+ . 5 foreach B ∈ ε-rare(S) do % ε-rare Atomsets in S. 6 % Identification of an expansion of B in S withH in∆+ . 7 if ∃H ∈ ∆+ ,H /∈ S | ∃⃗a ∈ NI : O,∆+ |= (B∪H)[⃗a] then %Rule B↠Hwith min. confidence in S∪∆+ . 8 if σ(B∪H)/σ(B) > γmin then R←R∪{B↠H}; 9 %Rule H↠Bwith min. confidence in S∪∆+ . 10 if σ(B ∪ H)/σ(H) > γmin then R ← R∪ {H ↠ B}; 11 returnR; %Rules expanding S with ∆+ with conf. γmin.

Lemma 1. (Non-Expandable Association EL++ Rules) No rule in S can be expanded with ∆+ (with respect to A2) if S and ∆+ have no similarity i.e., Φ(S, ∆+ ) = 0.

Proof. Since Φ(S,∆+ ) = 0, there is no invariant entailments between S and ∆+ i.e., no instance of S (resp. ∆+ ) is in an ABox assertion of ∆+ (resp. S). Thus, none of atom(sets) in S (resp. ∆+ ) is bind-able in ∆+ (resp. S). Condition line 7 is never satisfied: no rule can be expanded from S with ∆+ .

Example 11. (Approximate Rule Expansion)

Let C : {∃travel.Stop(x2)}. By applying A2 (E = {1}) to extend S : S 9 0 (6) with ∆+ : S 9 0 (7), {(4), (5)} is expanded (lines 5-10) with C to capture {(4), (5)} ↠ C with confidence 1/2. Rules such as occur(x2, x1) ↠ Event(x1), including 2-rare atomsets in S cannot be discovered due to E.

4.3 Incremental Knowledge Discovery (InKD)

Algorithm 3 (A3) ensures incremental maintenance of association EL++ rules from ∆- ∪S to S ∪∆+ . A3 is actioned only if knowledge removed ∆- and added ∆+ from S have significative dissimilarities (line 6). Any update ∆+ , which is primarily 1-rare, is not considered for maintenance since the more rare knowledge the less significant associations, generalization and rules. Alternatively all rules in ∆- ∪S are used as approximation for S ∪∆+ (line 14). For significative update, the interestingness of rules, valid in ∆- ∪S and S∪∆+ , are revised (line 8). Rules from S are expanded with ∆+ (line 11) when S, ∆+ have similarities (line 9 - Lemma 1). A3 completes the process (line 13) by mining rules in ∆+ ×∆+ using ap-genrules [L´ecu´e and Pan, 2015], noted a-gr.

Algorithm 3: [A3]InKD〈O, S n 0 , ∆- , S, ∆+ , E, ϱmin, γmin, Φmin〉

1 Input: (i) Axioms O : 〈T ,A〉, (ii) Streams S, ∆- ∪S, S ∪∆+ in S n 0 , (iii) a set of integers E ⊆ {1, ..., |S|}, (iv) Min. rarity ϱmin, confidence γmin, similarity Φmin. 2 Result: R: Rules with min. threshold γmin covering S∪∆+ . 3 begin 4 R← ∅; % Initialization of rules R in S ∪∆+ . 5 %Min. dissimilarity of ∆- and ∆+ . Min. non-rarity of ∆+. 6 if Φ(∆- , ∆+ ) < Φmin ∧ ϱ1(∆+) > ϱmin then 7 %Update of rules when adding ∆+ and removing ∆- . 8 R←A1〈O, S n 0 , ∆- , S〉 ∪ A1〈O, S n 0 ,∆+ , S∪∆+ 〉; 9 if Φ(S, ∆+ ) ̸= 0 then % Some similarities of S and ∆+ 10 % Expansion of rules from S to S ∪∆+ . 11 R ← R ∪ A2〈O, S n 0 , S, ∆+ , E, γmin〉; 12 %Mining of rules through associations uniquely in ∆+ . 13 R←R∪ {a-gr(∆+ ×∆+ , γmin)} 14 else R← {ρ : B↠H in S ∪∆- }; %All rules in S ∪∆- . 15 returnR; %Rules with confidence γmin covering S∪∆+ .

5 Experimental Results

We report scalability, accuracy results by studying the impact of knowledge similarity, ε-rarity on A3. The system is tested on: 4 Intel(R) Xeon(R) X5650, 2.67GHz cores, 6GB RAM.

5.1 Context

• Data: Data streams (Table 2) related to road weather, travel time, incident, event, bus location in Dublin are transformed in EL++ ontology streams using mapping techniques [L´ecu´e

• et al., 2014]. An ontology with 55 concepts, 19 roles and 25, 456 ABox axioms is considered for semantic enrichment. · Settings: The evaluation is achieved using a variable (i) size of stream window (i.e., snapshots) |w| ∈ {100, 500, 1000}, (ii) sliding k in {1/3, 2/3, 1} of |w|; a variation of min. thresholds of (iii) knowledge similarity in {1/3, 2/3, 1}, ε-rarity with ε ∈ E ⊆ {1, ..., |w|}, (iv) support, confidence as in Table 3. · Baseline Methods: L15 [L´ecu´e and Pan, 2015] for mining EL++ rules from scratch, G11 [Gama and Kosina, 2011] for learning decision rules i.e., subset of association rules, L03 [Lee et al., 2003] for incremental syntactic update, are compared. We restricted EL++ rules from A3, L15 to have a single concept atom in head similarly to G11. All rules from L03, G11 are uplifted using EL++ descriptions in ontologies. Its computation time is not reported for fair comparison. · Objective: The objective is to maintain association (EL++ rules) of knowledge across streams up-to-date while minimizing computation time and maximizing accuracy. Such rules
• empower reasoning with learning e.g., for prediction.

5.2 Scalability

· Dynamics: Figure 5 reports scalability with (i) variable size |w|, sliding k, (ii) fixed E i.e., E1 : {1, ..., ⌈|w|/2⌉}, γmin : .8, Φmin : .6. The scalability decreases with the size of windows and axioms. A3 is the most scalable in both contexts of increasing windows (i.e., more axioms) and sliding (i.e., less common knowledge) size. This remains valid even when windows do not share snapshots (k : 1), which shows the benefits of knowledge similarity and rarity. L15 is the least scalable for large windows since all rules are re-elaborated from scratch in each update. Its performance remains unchanged for any variation of k since the interleaving of windows is not exploited. On contrary L03 and G11 benefit from k i.e., the more interleaving snapshots the more scalable. G11 reaches comparable performances with A3 for large windows but fail to scale otherwise since all rules are systematically retrieved. · Knowledge: Figure 6 reports scalability of A3 with different knowledge similarity Φ and ε-rarity: E1, E2 :{⌈|w|/2⌉ + 1, |w|}, E3 :{1, ..., |w|}, with fixed |w|:1000 and k:1/3. The scalability decreases with the dissimilarity of updates, limiting the benefits of rules expansion and favoring a time consuming fresh discovery (line 13 of A3). E2 has a slightly better impact on A3 than E1 while E3 does not impact it dramatically. These are caused by the number of ε-rare atomsets derived from E which dropped from E1 to E2. Indeed the number of ε-rare atomsets statistically decreases when ε is approaching |w|. A3 scales the most when stream updates have similarities whatever the rarity of its knowledge.

5.3 Accuracy

Figures 7 and 8 reports accuracy by (syntactically) comparing the rules discovered in A3, G11, L03 with L15 (as baseline).

• Interestingness: Figure 7 considers (i) variable support, confidence (Table 3), and (ii) fixed |w| : 1000, k : 1/3. E : {1, ..., ⌈|w|/2⌉} and Φ : .6 are fixed for A3. In all cases the accuracy is more (positively) impacted by support than confidence. This is especially valid for A3 since the support directly limits insignificant knowledge association, which reduces the number of rules and their approximation. G11 is the least accurate since the rules expansion is probabilistic. Interestingly the (negative) effect of approximation, through similarity, rarity, is absorbed by the quality of support, confidence. Thus, accuracy can reach 91% since over-generalization / specialization, which drive insignificant updates, are pruned. · Knowledge (Figure 8): Same configuration as Figure 6 except Φ fixed to .6, ε-rarity extended with E4:{1, ..., ⌈|w|/3⌉}, E5:{⌈|w|/3⌉+1, ..., ⌈2 × |w|/3⌉}, E6:{⌈2 × |w|/3⌉+1, ..., |w|}. The accuracy with E1 (.89) and E3 (.93) are very close, which demonstrates that most of ε-rare knowledge, with ε > ⌈|w|/2⌉, could not be significantly associated with knowledge from the stream update. The results with E4, E5, E6 also emphasize the more rarity the more accurate is A3. This is even more significative in a context of "concept drift" i.e., when
• knowledge drastically changes over windows (Φ ≈ 0).

5.4 Lessons Learnt

Knowledge similarity, ε-rarity benefit scalability since they prune the time-consuming steps of (i) over-generalization, (ii) over-specialization, (iii) reaction to insignificant changes. Our approach scales the most when rare knowledge is discarded in line 7 of A2 (cf. E2 in Figure 6). However it is preferred to perform A3 with rare knowledge (cf. E1 in Figure 8) since the accuracy is not sacrificed with rarity. Indeed the gain of scalability is only of 11.4% for a loss of 61.7% in accuracy by discarding rare knowledge (from E1 to E2). In addition the gain of accuracy is only of 2.1% for a loss of 34.4% in scalability by considering all knowledge (from E1 to E3). Considering more expressive DLs would have decreased scalability due to binding, consistency checking. All approaches have been over-performed by A3 in large-scale contexts even when knowledge drastically changed over time.

6 Conclusion and FutureWork

Our approach, exploiting the semantics of data streams, discovers knowledge by incremental learning of association EL++ rules across DL-augmented stream data. The incremental maintenance of knowledge discovery, using systematic rules update and expansion, ensures scalability while efficiently maintaining accuracy. Semantics was essential for (i) capturing knowledge association as reusable EL++ rules across streams, (ii) identifying the properties of similarity and rarity in ontology streams which favor approximation and scalability of knowledge discovery. Experiments have shown highly scalable and accurate knowledge discovery in Dublin.

In future work we will investigate compact representations of ontology streams to support highly changing dynamic data.

Acknowledgments

The research leading to these results has received funding from the European Unions Seventh Framework Programme (FP7/2007-2013) under grant agreement ID 318201 (SIMPLI-CITY).