Recently an approach has been devised how to employ concept similarity measures (CSMs) for relaxing instance queries over EL ontologies in a controlled way. The approach relies on similarity measures between pointed interpretations to yield CSMs with certain properties. We report in this paper on Elastiq, which is a rst implementation of this approach and propose initial optimizations for this novel inference. We also provide a rst evaluation of Elastiq on the GeneOntology.
yields, for a pair of concepts, a value from the interval [0; 1]|indicating how similar the concepts are. To answer a relaxed instance query is to compute for a given concept C, a CSM , and a threshold t between 0 and 1, a set of concepts such that each of these concepts are similar to C by a threshold of at least t, if measured by the CSM , and then nding all their instances.
Concept similarity measures are widely used in ontology-based applications.
For ontologies from the bio-medical eld, such as the GeneOntology ontology
[
We investigated algorithms for computing answers to relaxed instance queries
for EL. This DL has good computational properties and large, well-known
biomedical ontologies such as the GeneOntology [
Now, for computing answers to relaxed instance queries, the similarity values for all pairs of elements between the two canonical models need to be computed in the worst case. Thus a naive implementation would hardly be e cient. We report in this paper in rst optimizations for this novel inference, which we have implemented in the system Elastiq (EL answering of similarity-threshold instance queries). A rst evaluation on the GeneOntology shows that the proposed optimizations are vital for this kind of inference, but that response times for a single query over large ontologies are still about a second.
The remainder of the paper in structured as follows. Next, we give an introduction to the technical terms used and the relaxed instance inference. In Section 3 we discuss the algorithm for computing relaxed instances and the similarity measures employed for it. The Elastiq reasoner is introduced in Section 4 together with some optimizations and the evaluation of its performance on the GeneOntology. The paper ends with conclusions and future work. 2
EL-concepts are built from two mutually disjoint sets NC of concept names, and NR of role names using the syntactic rule: C; D ::= > j A j C u D j 9r:C, where A 2 NC and r 2 NR. The semantics of EL-concepts are de ned by means of interpretations, in which concept names are interpreted as subsets of the interpretation domain and roles as binary relations. The semantics are extended to complex concepts as usual. An EL-TBox consists of a nite set of general concept inclusion axioms (GCIs) of the form C v D. An interpretation is a model for a TBox if it satis es all its GCIs. An EL-ABox describes individuals from a set NI of individual names using concept assertions of the form C(a) and role assertions of the form r(a; b). Again, an interpretation is a model for an ABox if it satis es all its assertions. An EL-knowledge base (KB) is a pair K = (T ; A) of a TBox T and an ABox A.
The following commonly used reasoning tasks are implemented in most DL reasoning systems. Concept subsumption C vT D asks, for a TBox T and two concepts C and D, if CI DI for all models I of T . Given an individual a, a concept C, and a KB K, a is called an instance of C w.r.t. K, denoted K j= C(a), i aI 2 CI for all models I of K. Given a KB K = (T ; A) and a concept C, instance retrieval returns all individuals from A that are instances of C.
For the DL EL, the polynomial-time complexity of most reasoning procedures rely on the fact that canonical models can be built, from which it is possible to read o entailments directly. These canonical models represent the most general model for a concept or the individuals of an ABox w.r.t. to a TBox. Before we can formally de ne these canonical models, we need to introduce some notation. If X is a concept, TBox, ABox, or KB, then: { Sig(X) denotes the signature of X; that is, the set of concept, role, and individual names appearing in X, and { sub(X) is the set of all sub-concepts of concepts occurring in X. De nition 1. (canonical models) Let C be an EL-concept and K = (T ; A) an EL-KB. The canonical model IC;T = ( IC;T ; IC;T ) of C w.r.t. the TBox T is: { IC;T = fdC g [ fdD j 9r:D 2 sub(C) [ sub(T )g { AIC;T = fdD j D vT Ag, for all concept names A, and { rIC;T = f(dD; dE ) j D vT 9r:Eg for all role names r.
The canonical model IK = ( IK ; IK ) of the KB K = (T ; A) is de ned as follows: { IK = fda j a 2 Sig(A) \ NI g [ fdC j 9r:C 2 sub(A) [ sub(T )g, { AIK = fdD j D vT Ag [ fda j K j= A(a)g, { rIK = f(dD; dE ) j D vT 9r:Eg [ f(da; dD) j K j= 9r:D(a)g [ f(da; db) j r(a; b) 2 Ag.
Note that canonical models for EL are always nite. Canonical models can be
used to decide instance checking problems since a is an instance of C w.r.t.
a KB K if and only if aIK is an element of CIK in the canonical model IK
[
Instance checking can be relaxed by using a concept similarity measure. Such
a measure is a function that assigns to each pair of concepts (w.r.t. a TBox T )
a similarity value from the interval [0; 1] with C C = 1 for all concepts C. A
value C D = 0 means that the concepts C and D are totally dissimilar, while a
value of 1 indicates total similarity. A set of properties for CSMs was presented in
[
In [
i to be de ned depends on three parameters: 1. A primitive measure p : NC NC [ NR NR ! [0; 1] assigns a similarity value to each pair of concept names and each pair of role names. Any primitive measure has to satisfy that x p x = 1 for any concept or role name x. Additionally, for the similarity measure i to be symmetric, p needs to be symmetric as well. We give a default primitive measure, that simply assigns similarity 0 to pairs of di erent concept or role names x and y: x default y = (1 if x = y
0 otherwise However, other primitive measures are imaginable and useful. For example, one might want to express that two amounts Medium and High are more similar than Low and High, which can be achieved by using a primitive measure with Medium p High = 0:5 and Low p High = 0. 2. A weighting function g : NC [NR ! R>0 to prioritize di erent features in the similarity measure. We give a default weighting function gdefault, that assigns 1 to every concept and role name, but again, other weighting functions can be useful for certain cases. 3. A discounting factor w is a constant that allows for discounting of successors, and should have a value 0 < w < 1.
De nition 3. Given a primitive measure p, a weighting function g and the discounting factor w, the interpretation similarity measure i is de ned as: p i q = simCN(p; q) + simCN(q; p) + simSC(p; q) + simSC(q; p)
If all of the sets CN(p), CN(q), SC(p), and SC(q) are empty for pointed interpretations p; q, we de ne p i q = 1.
Note that i does not necessarily yield an equivalence closed or equivalence invariant CSM. To regain these properties, one can rst normalize the interpretations before applying the i. An interpretation I = ( I ; I ) is in interpretation normal form if there are no elements a; b; c 2 I , b 6= c, such that f(a; b); (a; c)g rI and for all concepts C with b 2 CI also c 2 CI holds; i.e., no node has two successors for the same role name whose instantiators are in a subset relation3. Any interpretation I can be transformed into normal form in polynomial time by removing all redundant successors.
Let IC0;T and ID0;T denote canonical models in interpretation normal form, then the CSM c is de ned as follows:
C
c D = (IC0;T ; dC ) i (ID0;T ; dD): c is indeed symmetric, equivalence invariant, and equivalence
Cex = Server u 9hasLoad:Medium u 9provides:(VideoStreamService u Service) and
Dex = Server u 9hasLoad:Low u 9provides:(DBService u Service u 9queryLang:SQL).
We use the primitive measure p, which is almost the default primitive
measure, except for Low p Medium = Medium p High = 0:5 instead of 0. We also
3 Formally, one describes this using the notion of a simulation between b and c in I,
see [
Cex c Dex = 1 + 1 + 2 + 2 = 0:707:
The procedure to compute relaxed instances of a query concept Q w.r.t. a
KB K = (T ; A), a threshold t, and the CSM c has the following steps [
ABox A w.r.t. the TBox T . 2. Transform these models into IQ0;T and IK0. 3. De ne a maximal interpretation similarity imax between the normalized canonical models. The measure imax is behaves like i, but chooses a subset of the concept names and successors for elements in the canonical model IK in a way to maximize the similarity value. 4. For each individual a occurring in K, check if the maximal interpretation similarity between the element dQ in IQ0;T and the element da in IK0 is larger than the given threshold t. If so, a is a relaxed instance and is returned. Formally, imax is de ned as the unique solution of the following equation system: simCN CN(p); Cq + simCN Cq; CN(p)
+ simSC SC(p); Sq + simSC Sq; SC(p) where simCN(C1; C2) =
X max g(A)(A
We showed that using the maximal interpretation similarity indeed solves the
problem of answering relaxed instance queries correctly, see [
Theorem 1 ([
We showed an upper complexity bound of NP by (non-deterministically) translating the equation system that de nes (IQ0;T ; dQ) imax (IK0; da) into a linear programming problem of polynomial size and solving it. However, this approach is not practical. Instead, Elastiq implements an iterative approach, that re nes the similarity values and converges to imax in the limit. This approach which we present next is sound, as it converges from below, but not necessarily complete. 4
Elastiq is the rst implementation for answering instance queries relaxed by a similarity measure. Given an EL-ontology, an EL-query concept, an instantiation of c and a value for a threshold, Elastiq computes a result set of ABox individuals, where each of these individuals is relaxed instance. The CSM employed here is xed to c as de ned in Section 3, but it and can be adjusted by a custom weighting function, primitive similarity measure and the discounting factor. Computing an answer to a relaxed instance query by Elastiq consists of four main steps.
Step 1: Global preprocessing. The canonical model IK of the ABox and the TBox
is generated by the use of a standard DL reasoner, currently Elastiq uses the
Elk system [
Step 2: Local preprocessing. The canonical model of the query concept w.r.t. the TBox IQ;T is generated|as in Step 1 by the use of Elk.
Elastiq distinguishes the two preprocessing steps for the sake of computing
several relaxed instance queries against the same KB faster. Obviously, IK does not
depend on the query concept and can therefore be reused for every subsequent
queries. The model IQ;T , however, needs to be recreated for every di erent query
concept Q. In both steps we use the Elk reasoner [
Each iteration j + 1 creates a new matrix Mj+1, and computes the values by applying Equation (1) to the values in Mj . Elastiq needs only to keep the current matrix Mj+1 and the last one Mj (j 0) in memory. The iterations for the re nement of similarity values proceeds until one of the following termination criteria is met: { the maximal amount of iterations imax speci ed by the user is reached; or { no interesting similarity value (dQ; da) has changed during the last iteration by more than a relative factor speci ed by the user.
Step 4: Comparison with t. After the iteration stopped, the interesting similarity values Mj (dQ; da) are compared to the input threshold t and the answer set of individuals is compiled. This set is then listed in descending order of similarity. 4.1
A naive implementation of the algorithm can hardly compute relaxed instances for reasonably large ontologies in acceptable time. As mentioned before, a highly e ective optimization is the reuse of IK for multiple queries. Since ABoxes are usually much larger than query concepts, the model IK is also be much more costly to create than the models IQ;T . Additionally, the normalization of canonical models can be done more e ciently than by computing simulations to determine unnecessary role-successors. Before adding a domain element dC as an r-successor to some element dD Elastiq checks whether there already exists an r-successor dE for dD such that E v C. In this case normalization would eliminate dC , thus avoiding the introduction of dC (and its role successors) improves the runtime of canonical model generation further. Similarly, when adding dC as an r-successor to dD, Elastiq eliminates all r-successors dE of dD if C v E.
During the generation of the canonical models Elastiq performs many subsumption checks. Although Elk is currently one of the fastest reasoners for EL, caching of sub- and superclass relations yielded a great performance boost, since Elastiq needs to access sub- and superclass relationships for the same class several times.
The algorithm from Section 3 suggests to iterate over all subsets of CN and SC successors in order to nd the maximal similarity. This exponential procedure can be improved by looking at the primitive similarities between elements. Let d 2 IQ;T and e 2 IK. By de nition of imax we are looking for those subsets of the concept names and successors of e that maximize the similarity. Instead of iterating over all subsets of CN(e) to nd the best pairing, we showed that if B 2 CN(e) such that 9A 2 CN(d) with A p B = 1, we can always keep B in the subset of CN(e), because it will always increase the similarity. Conversely, if B0 2 CN(e) such that 8A 2 CN(d), then A p B0 = 0, and B0 can be left out of the subset of CN(e), since it cannot increase the similarity. Analogously, we can remove (s; q) from SC(e) if for all (r; p) 2 SC(d) we have r p s = 0. This can dramatically reduce the number of subsets to be checked. In fact, for the default primitive measure, this means that the best subset of concept names can always be computed in linear time by checking each concept name in CN(e) separately. 4.2
Our preliminary performance evaluation of Elastiq used di erent versions of the GeneOntology that describe schizosaccharomyces pombe|some species of yeast. These ontologies ranged from 9,157 concept names and 34,875 individuals in the rst version to 51,949 concept names and 289,206 individuals for the 15th version. The sizes of canonical models ranged from 77,941 to 602,548 elements.
We obtained our test ontologies by custom dataset generation provided by
the Manchester OWL Corpus [
Our test suite contains 10 randomly generated query concepts with increasingly complex structures. These queries were built over the common signature of versions 1{15 of the GeneOntology (approximately 1,000 concept names and 4 roles). The smallest query (Query 1) only contained 6 concept and role names and had a role-depth of 2, while the Query 10 had a size of 670 and a roledepth of 5. Due to the plain structure of concept assertions we wrapped each query concept Qi with 9is a:Qi in order to provoke a more complex computation. For these queries, the sizes of the canonical models IQ;T ranged from 2 to 236 elements. We evaluated the queries for the default primitive measure and weighting function, and counted the number of relaxed instances for a threshold of t = 0:333. The test system had a 1800 MHz dual core processor AMD Turion II Neo and 6 GB of RAM. Figure 1 shows the runtime of Elastiq for answering all 10 relaxed instance queries w.r.t. each ontology version. The high runtimes for ontology versions 11, 12, and especially 13{15 is mainly due to the increase of the size of the canonical model IK. Most queries returned a lot more relaxed instances for the ontologies 11{15 than for ontologies 1{10. Queries 8 and 9 returned the largest number of relaxed instances, up to over 200,000 for Query 8 evaluated on nnotations15.owl.
When breaking down the times for preprocessing and the query answering further, it shows that the preprocessing time is dominated by the attening of the ontology, the reasoning done by Elk, and the construction of the canonical model IK, while the time to construct the canonical models IQ;T is negligible. However, the overall query answering time is largely spend on Step 3, i.e., the iterations to compute the maximal similarity.
Elastiq performs ABox realization to obtain IK and in addition a kind of relaxed ABox realization for the query concepts in the test suite. Now, while it is clear that Elastiq is slower than Elk for ABox realization, it showed, suprisingly, that this does not need to be the case for other optimized DL reasoners. We compared Elastiq's overall reasoning times with the ABox realization times of the commonly used FaCT++ reasoner [18]. Figure 2 shows that Elastiq mostly performed better than FaCT++, although solving a more complex task.4 However, computation times of more than a minute for 10 relaxed queries over ABoxes with 1,000 individuals still calls for further improvement. 5
In this paper we investigated the novel inference of answering relaxed instance queries. These queries can be gradually relaxed by varying the threshold, while 4 Note that FaCT++ classi cation resulted in an error for ontologies 13{15. the similarity measure allows to specify which parts of the query can be relaxed and which should be kept. We devised a concept similarity measure, c, that works for general EL-TBoxes, and showed how to relax instance queries using this measure. We presented Elastiq, a prototype sytem for relaxed instance query answering, some straight-forward, but highly e ective optimization techniques, and gave a rst performance evaluation using di erent queries on increasingly complex versions of the GeneOntology.
It turned out that for ontologies with large ABoxes, Elastiq is still not fast enough. We want to explore further optimizations for the computation of imax. Currently, the matrices converge to imax from below. With upper bounds on the maximal similarity, it would be possible to prune computation early on individuals that are certainly not relaxed instances. While currently the algorithm decides which individuals are certainly relaxed answers, an upper bound could also be used to determine which individuals are certainly not relaxed answers, therefore making the approach not just sound, but complete. We also need to perform further evaluations for the performance on ontologies and query concepts from other domains, but also to evaluate the quality of the answers returned by Elastiq in regard of the di erent CSMs in use.
Currently, one needs to specify a threshold, above which individuals are considered as relaxed answers. This threshold approach guarantees a minimal similarity and hence quality of the result, but it is hard to predict how many relaxed answers a query would return for a certain threshold. In cases where just the rst few most similar relaxed answers are of interest, top-k answering would be more useful. We are investigating to e ciently implement this type of answering mechanism. Finally, it would be useful to not just consider instance queries, but more expressive query types as well. We are currently working on the theoretical basis for relaxing conjunctive queries. 17. S. Tongphu and B. Suntisrivaraporn. On desirable properties of the structural subsumption-based similarity measure. In T. Supnithi, T. Yamaguchi, J. Z. Pan, V. Wuwongse, and M. Buranarach, editors, Proceedings of the 4th Joint International Conference on Semantic Technology, (JIST 2014), volume 8943 of LNCS, pages 19{32. Springer, 2014. 18. D. Tsarkov and I. Horrocks. Fact++ description logic reasoner: System description. In Proceedings of the Third International Joint Conference on Automated Reasoning, IJCAR'06, pages 292{297, Berlin, Heidelberg, 2006. Springer-Verlag.