Mini-ME Swift: The First Mobile OWL Reasoner for iOS

Semantic Web technologies have been increasingly adopted in resource-constrained volatile environments through the Semantic Web of Things (SWoT) [8, 25], whose goal is embedding intelligence in pervasive contexts. Semantic Web languages underlie knowledge representation and interoperability in the SWoT, particularly the Resource Description Framework (RDF)^{Footnote 1} and the Web Ontology Language (OWL)^{Footnote 2}. Anyway, although mobile devices are even more powerful, porting existing Semantic Web inference engines to mobile operating systems is not a straightforward task and it may result in suboptimal performance. Among the challenges for the next decade of the Semantic Web, Bernstein et al. [3] outlined “languages and architectures that will provide [...] knowledge to the increasingly mobile and application-based Web”. More specifically, Yus and Pappachan [37] pointed out the “lack of semantic reasoners for certain mobile operating systems (such as iOS)” among the problems of developing semantic mobile apps. Several solutions are currently available for Android [4], due to its support for the Java language, allowing to port popular OWL manipulation libraries. Conversely, the Apple iOS mobile platform has been neglected so far, due to differences in architecture and development tools.

Hence, this paper introduces Mini-ME Swift, the first Description Logics reasoner and matchmaker for iOS. It has been developed in Swift 4 language aiming to the Application Programming Interface (API) parity with the Java-based Mini Matchmaking Engine [26], though it has been designed and implemented from scratch to achieve significantly better performance. Logic expressiveness is limited to an OWL fragment corresponding to the \(\mathcal {ALN}\) (Attributive Language with unqualified Number restrictions) Description Logic (DL) on acyclic Terminological boxes (TBoxes). It efficiently implements standard (Subsumption, Satisfiability, Classification, Consistency) and non-standard (Abduction, Contraction, Covering, Difference) inferences. A case study on semantic-enhanced Point of Interest (POI) discovery in Mobile Augmented Reality (MAR) has allowed validating the effectiveness and ease of integration of the proposed matchmaker in iOS apps. Architectural and optimization solutions have been assessed in an experimental campaign, comparing Mini-ME Swift with the Java-based Mini-ME as well as with four popular Semantic Web reasoners. Inference time and memory usage are reported on a conventional desktop testbed, and required computational resources have been evaluated on current mobile devices.

The remainder of the paper is as follows. Section 2 recalls essential background information and relevant related work. Mini-ME Swift design and optimization strategies are discussed in Sect. 3. Section 4 presents the case study, while performance assessment is in Sect. 5, before conclusions.

Related Work. Due to architectural constraints and computational complexity of Description Logics reasoning, the majority of early mobile inference engines provided only rule processing for entailment materialization in a Knowledge Base (KB); proposals include 3APL-M [11], COROR [31], MiRE4OWL [10], Delta-Reasoner [17] and the system in [27]. The \(\mu \)OR reasoner [1] adopts a resolution algorithm on the OWL-Lite\(^{-}\) language, while LOnt [12] works on DL Lite, a subset of OWL-Lite. The mobile OWL2 RL engine in [36] exploits an optimization of the classic RETE algorithm for rule systems. More expressive DLs were supported by exploiting tableau algorithms: Pocket KRHyper [28] adopted the \(\mathcal {ALCHIR+}\) DL, but memory limitations curbed the size and complexity of manageable KBs. Tableaux optimization was exploited in mTableaux [30] to reduce memory consumption. Fuzzy \(\mathcal {ALN}\)(D) was supported in [21] via structural algorithms. Android is currently the most widespread mobile platform and Java is its primary application development language. The majority of state-of-the-art OWL reasoners runs on Java Standard Edition (SE) [14], mature Semantic Web language manipulation libraries are available such as Jena [15] and the OWL API [7]. Anyway, porting existing systems requires significant effort, due to architectural differences and incomplete support of Java SE class libraries under Android. Bobed et al. [4] met such barriers when porting Hermit [6], JFact (a Java variant of Fact++ [34]) and three other OWL reasoners to Android. Jena was ported by AndroJena^{Footnote 3}, albeit with deep re-design and feature limitations. The ELK reasoner has an Android port [9] as well. To the best of our knowledge, no previous reasoner has supported iOS, preventing a relevant segment of users and application developers from exploiting semantic technologies effectively. In fact, a few semantic-based iOS apps and prototypes do exist, but they either exploit remote servers for reasoning [19, 23, 35] or precompute inferences on a conventional computer, storing results on the mobile device [20]. The iOS port of a subset of the OWL API [22] has enabled the development of Mini-ME Swift. From a performance optimization standpoint, TrOWL [33], Konclude [29] and other recent inference engines implement multiple different techniques and then select the best one according to the logical expressiveness of the particular KB and/or the required inference task. Konclude can also exploit parallel execution on multi-core processors and it has been the top performer in latest OWL DL reasoner competitions [18]. Nevertheless, SWoT application surveys [5, 13] evidence inherently unpredictable contexts requiring mobile agents endowed with quick decision support, query answering and stream reasoning capabilities. Specific non-standard inference services may be more suitable than standard ones in those cases [26].

Inference Services. The proposed reasoner leverages polynomial-complexity structural algorithms exploiting KB preprocessing stages for concept unfolding and Conjunctive Normal Form (CNF) normalization through recursive procedures. In \(\mathcal {ALN}\) CNF, every concept expression is either \(\bot \) (Bottom a.k.a. Nothing) or the conjunction (\(\sqcap \)) of: (possibly negated) atomic concepts; greater-than (\(\ge \)) and less-than (\(\le \)) number restrictions, no more than one per type per role; universal restrictions (\(\forall \)), no more than one per role, with filler recursively in CNF. As said, Mini-ME Swift supplies standard Subsumption and Satisfiability. In advanced scenarios they are not enough, as they provide only a Boolean answer. Therefore, non-standard Concept Abduction (CA) and Concept Contraction (CC) allow extending, respectively, (missed) subsumption and (un)satisfiability, in the Open World Assumption [26]. Based on CNF norm, they also provide a penalty metric evidencing a semantic distance ranking of KB instances (a.k.a. resources in matchmaking settings) w.r.t. a target individual (a.k.a. request). Mini-ME Swift further includes Concept Difference (CD) [32] to subtract information in a concept description from another one. While CA, CC and CD are useful in one-to-one discovery, matchmaking and negotiation scenarios, Mini-ME also includes the Concept Covering Problem (CCoP) non-standard inference for many-to-one composition of a set of elementary instances to answer complex requests [26]. Mini-ME Swift can be also exploited in more general knowledge-based applications, as it provides Coherence and Classification services over ontologies: Coherence is close to Ontology Satisfiability, but it does not process individuals [16]; Ontology Classification computes the overall concept taxonomy induced by the subsumption relation, from \(\top \) (Top a.k.a. Thing) to \(\bot \).

Reasoner architecture

Full size image

Reasoner Architecture. The proposed tool is written in Swift 4. It can be compiled as iOS Framework, i.e., as dynamic linking library. It targets all iOS devices running system version 8 or later, and it also runs unmodified on macOS 10.11 and later. By leveraging the expressive power of the Swift language –particularly its functional features, such as optionals, optional binding and higher order functions^{Footnote 4}– the codebase is still compact, with a good readability. The reasoner architecture, in Fig. 1, has been kept purposefully simple to avoid unnecessary layers of abstraction and the associated overhead. Main components are described hereafter. Particularly, the KBWrapper and SemanticDescription classes implement most of the available reasoning tasks on ontologies and concept descriptions, respectively. The MicroReasoner class acts as a facade hiding the interactions between lower-level components. In detail:

• OWL API for iOS: is the port [22] of the OWL API to the iOS platform, providing support for parsing and manipulating OWL2 KBs in \(\mathcal {ALEN}\) (Attributive Language with unqualified Existential and Number restrictions) DL with RDF/XML syntax.

• MicroReasoner: is the library entry point, exposing KB operations such as parsing the target ontology and loading/fetching instances to be used for matchmaking. It also exposes standard and non-standard inferences.

• KBWrapper: allows KB management, i.e., creation of internal data structures and concept unfolding as well as Classification and Coherence check on ontologies.

  Storage, preprocessing and inference procedures on concept expressions are implemented by methods of different high-level data structures owned by the KBWrapper:

• OntologyEntry: when parsing an ontology, the KBWrapper loads the TBox, whose concepts and associated descriptions are stored as (IRI, OntologyEntry) pairs. OntologyEntry instances encapsulate the information about any concept involved in a reasoning task, e.g., its expression and its normalization cache value (see Sect. 3).

• Taxonomy: models the concept hierarchy as resulting from Classification. It allows manipulating the tree, merging equivalent nodes, and retrieving ancestors or successors of a given node.

• Item: represents matchmaking resources and requests, but it can refer to any named concept expression. It is composed by an IRI and a SemanticDescription.

  TBox and Assertion Box (ABox) manipulation and reasoning are supported by the following low-level data structure layer:

• SemanticDescription: models an \(\mathcal {ALN}\) concept expression in CNF as conjunction of \(C_{CN}\), \(C_{\ge }\), \(C_{\le }\), \(C_{\forall }\) components, stored in collections of AtomicConcept, GreaterThanRole, LessThanRole and UniversalRole Swift class instances, respectively.

• Abduction, Contraction, Composition: model the results of CA, CC and CCoP, respectively. Abduction and Contraction include a penalty score [26].

Optimization Strategies. Some of the lower-level optimizations in Mini-ME Swift have been achieved thanks to specific characteristics and implementation details of the programming language. The implicit use of Copy on Write (CoW) for Swift collections –transparent to the developer– has enabled a straightforward performance improvement in algorithms heavily relying on conditionally mutating collections (concept unfolding and normalization). Further benefits stem from the adoption of structs instead of classes for some of the lower-level data structures, since they are often allocated on the stack rather than on the heap. However, Automatic Reference Counting (ARC)^{Footnote 5} –the memory management strategy employed by the Swift compiler– sometimes would have led to performance degradation in critical code sections. As an example, one of the recursive tree traversal algorithms implemented in Mini-ME Swift originally spent about 80% of its total CPU time in retain and release function calls on the nodes of the tree. This has been addressed by leveraging unmanaged references^{Footnote 6} wherever needed. High-level optimization has also been carried out in order to improve both inference turnaround time and memory usage. Enhancements concern:

• Ontology loading and preprocessing: once Mini-ME Swift is instantiated, the target ontology is loaded into the internal data structures and preprocessed. At this stage, terminological equivalences are transitively unfolded and merged in single entries (e.g., if \(C \equiv D\) and \(D \equiv E\), then \(C \equiv D \equiv E \equiv C \sqcap D \sqcap E\)), saving memory and processing time. Furthermore, told subsumption cycles [34] are identified and marked in order to be efficiently solved while classifying. These are the only possible cyclic references supported by Mini-ME Swift. Finally, concept and role names are translated to internal numerical identifiers, allowing for more efficient storage and processing. In particular, memory addresses are exploited as IDs, leveraging the uniqueness of IRI in-memory instances obtained from the OWL API iOS port [22].

• Concept unfolding and normalization: the unfolding and CNF normalization algorithms were initially optimized by caching completely unfolded and normalized concepts. However, it soon became evident that caching could be extended to intermediate unfolded concepts as well: given an acyclic concept B, every other concept C recursively unfolded as part of the unfolding of B is also completely unfolded, making it suitable for caching. However, C is not yet in normal form, therefore the concept cache must keep track of whether stored concepts have been only unfolded or both unfolded and normalized. This strategy has two benefits: (i) it enables the reuse of the unfolded description of C as part of the normalization of further concepts; (ii) it minimizes computation when C needs to be normalized, since the unfolding step is executed just once.

• Classification: Mini-ME Swift adopts a variant of the enhanced traversal algorithm in [2], which also accounts for subsumption cycles detected while preprocessing the ontology. Subsumption check results are cached, as customary for OWL reasoners, though significant effort went in ensuring checks are avoided whenever possible: classification is performed according to the concept definition order [2], which allows skipping the bottom search step for primitive concepts having acyclic descriptions. The exploitation of told disjoints [34] and told subsumers has been implemented. Moreover, synonym merging (e.g., if it is inferred that \(B \equiv C\), then the taxonomy nodes for B and C are merged) reduces memory usage and search time by making the tree smaller.

• Ontology Coherence: a naive approach involves performing CNF normalization for every concept in the TBox [26]. However, earlier experimental results showed this process is time consuming (particularly for larger TBoxes). This could be smoothed by adopting forceful caching policies for unfolded concepts, albeit paying additional occupancy of memory. Mini-ME Swift sidesteps this problem by computing the Coherence check through a modified version of the Classification algorithm, which stops as soon as an unsatisfiable concept is detected. Since normalization is lazy –i.e., it is computed only when needed for an inference task– and Classification explicitly avoids subsumptions as much as possible, the overall number of performed normalizations is also reduced. This results in significantly improved time and memory efficiency w.r.t. the naive approach. Furthermore, the Coherence check of a TBox \(\mathcal {T}\) can be skipped in the following cases: (i) \(\mathcal {T}\) is trivially incoherent if \(\exists \) a concept expression C in \(\mathcal {T}\) \(\vert \ C \sqsubseteq \bot \); (ii) \(\mathcal {T}\) is trivially coherent if \(\mathcal {T}\) contains no disjoint concept axioms and number restrictions are either absent or all of the same type (i.e., either minimum or maximum cardinality). Both conditions can be verified inexpensively while loading the KB, since this only entails checking whether given constructors are in the TBox.

MAR POI semantic discovery prototype

Full size image

In order to validate the effectiveness and the ease of use of Mini-ME Swift in ubiquitous computing applications, the existing Android framework in [24] has been rewritten in Swift as a prototypical iOS app. The tool leverages crowd-sourced OpenStreetMap^{Footnote 7} (OSM) cartography, annotated exploiting Semantic Web technologies to provide POIs with rich structured descriptions. Figure 2a illustrates application components. The mobile client communicates with an OSM server, providing map elements enriched with formal machine-understandable metadata. The app uses Mini-ME Swift to execute semantic matchmaking [26] between an annotated user profile and POIs in the area surrounding user’s location. Position is obtained from embedded smartphone devices, including accelerometer, compass and Wi-Fi trilateration. IndoorAtlas^{Footnote 8} toolkit, relying on the device magnetometer, provides accurate localization in indoor contexts. As shown in Fig. 2b, semantic matchmaking outcomes are displayed as color-coded markers in a MAR graphical UI leveraging ARKit^{Footnote 9} iOS library. Colors from green to red represent semantic distance, from full to partial matches. The user can touch a marker to access result explanation, in terms of missing and/or conflicting characteristics between her profile and the POI. Due to lack of space, the reader is referred to [24] for details on the map annotation method and POI discovery algorithm. By following iOS developer guidelines, the integration of Mini-ME Swift, IndoorAtlas and ARKit has been straightforward.

An experimental evaluation of the proposed system has been carried out on desktop and mobile devices, for standard and non-standard inference services, by means of a bespoke test framework^{Footnote 10}. Desktop tests have been performed on a 2009 Mac Pro^{Footnote 11}, while mobile experiments on an iPhone 7^{Footnote 12}, an iPad Mini 4^{Footnote 13} and an iPhone 5s^{Footnote 14}. Correctness and completeness of inference services have been checked by comparing obtained results with other state-of-the-art reasoners, used as test oracles. Outcomes returned by Mini-ME Swift have been considered correct in case of unanimous match with all the oracles and incorrect in case of no match; manual investigation has been performed for partial matches. Performance evaluation has been focused on turnaround time and peak memory usage for each inference task: results are the average of five repeated runs, with a timeout of 30 min for each run. Reported memory peak values represent the maximum resident set size (MRSS) for the process, extracted via BSD time on Mac, and equivalently through the getrusage POSIX call on mobile. The reader can refer to the Mini-ME Swift Web page^{Footnote 15} for getting the reasoner and in-depth documentation on how to reproduce the benchmarks reported hereafter.

Performance results for the classification task on desktop and mobile devices

Full size image

5.1 Standard Inference Services

Ontology Classification and Coherence have been evaluated on a set of 1364 KBs, obtained from the 2014 OWL Reasoner Evaluation Workshop competition reference dataset^{Footnote 16} considering all the KBs supported by Mini-ME Swift (e.g., having at most \(\mathcal {ALN}\) as indicated expressiveness, without general concept inclusions and other unsupported logic constructors). The following reasoners have been used as test oracles of correctness and completeness, as well as references for performance comparison: Fact++ (version 1.6.5) [34], HermiT (1.3.8) [6], Konclude (0.6.2-544) [29], TrOWL (1.5) [33] and Mini-ME Java (2.0) [26]. Before presenting the results of the experimental campaign, it is important to point out that:

• Since Konclude can only parse ontologies in OWL functional syntax and Mini-ME Swift currently only supports the RDF/XML serialization, RDF/XML parsing has been restricted to Mini-ME Swift only, and every other reasoner has been configured to use the functional syntax. This is a worst-case scenario w.r.t. turnaround time, since in general the functional representation is shorter and easier to parse than the equivalent RDF/XML. This is evident in Fig. 3 particularly for the smallest and the largest ontologies, where data points for Mini-ME Swift appear shifted to the right.

• Mini-ME does not process the ABox when computing standard inferences, therefore Ontology Coherence has been informally compared to Consistency as supported by other reasoners, and mismatches have been manually analyzed in order to evaluate the correctness of the reasoner output.

• Since the coherence check is based on a modified version of the Classification algorithm (as stated in Sect. 3), the Ontology Coherence performance results are similar to Classification, hence they have not been reported here.

Correctness. Mini-ME Swift has classified all the 1364 ontologies correctly. The Coherence test has returned matching results for 1353 ontologies (99.2% of the dataset). The remaining 11 ontologies contain unsatisfiable classes with no instances, resulting in being considered incoherent by Mini-ME but consistent by other reasoners.

Desktop Performance. Figure 3a plots Classification turnaround times as a function of the ontology size. The time axis scale is limited to 600 s since all reasoners are able to process each ontology in the dataset well within the imposed timeout; the only exceptions are Mini-ME Java and TrOWL, which have reached the timeout on 8 and 1 ontologies, respectively. Mini-ME Swift outperformed all reference systems for ontologies smaller than 200 kB ca.; for larger input, Konclude and Mini-ME Swift have similar performance, both substantially faster than the other reasoners. Although Mini-ME Swift has the advantage of focusing on a smaller OWL2 fragment than the other reasoners, results are influenced by parsing, where Mini-ME Swift is disadvantaged due to RDF/XML adoption. Table 1 displays the cumulative classification performance on the 1301 ontologies correctly classified by all systems within the timeout, and the number of cases where each reasoner was the fastest one; Mini-ME Swift exhibits the lowest overall time by a significant margin, if parsing is factored out. Figure 3b shows the peak memory usage: it is consistently and significantly lower for Mini-ME Swift than the reference tools. Specifically, as reported in Table 1, both the minimum and maximum peaks over the dataset are at least 50% lower than the next-best result for Classification.

Performance statistics for classification on both desktop and mobiles

Full size image

Mobile Performance. Mini-ME Swift has successfully executed the standard inferences on the same dataset of desktop testbed for all tested mobiles except iPhone 5s, where it failed to process KBs larger than 100 MB ca. due to its low memory availability. Turnaround time and peak memory results shown in Table 1 and Figs. 3c and 3d follow the hardware availability, i.e., devices with faster CPUs have lower turnaround times and those with larger RAM have been granted more memory by the OS. An interesting result is that the Mac Pro, plotted alongside the mobile devices in Fig. 3c, has been quicker than the iPhone 7 when reasoning over smaller ontologies, but it has been clearly outperformed starting from medium-sized ones. This is likely due to the implemented algorithms being single-threaded, not exploiting the higher level of parallelism in the desktop CPU w.r.t. mobile ones. Furthermore, Fig. 3d shows lower memory peaks for small ontologies on the Mac Pro: since all iOS applications must have a graphical user interface, mobile tests are affected by a systematic memory overhead w.r.t. tests executed through command line interface on the Mac^{Footnote 17}. In order to provide further insight, Fig. 4 compares all reasoners (on workstation and mobile) on the whole set of KBs which have been correctly processed by all tools. The area with blue background encloses Mini-ME Swift instances running on desktop and mobile devices. In Fig. 4a inference tasks are split in ontology parsing and actual reasoning; the overall time spent in each step is displayed on the axes. Figure 4b shows on both the axes the lowest and highest memory peak values across the whole dataset. Although iPhone 5s maximum peak value is biased by failed tests, the overall results highlight Mini-ME Swift has a comparatively low memory footprint.

5.2 Non-standard Inference Services

Non-standard inference services have been evaluated on four \(\mathcal {ALN}\) KBs. Their features are summarized in the upper section of Table 2: size, number of concepts, roles, instances and number of matchmaking tasks to be performed in the tests, where each task has been executed on a \(\langle \)request, resource\(\rangle \) pair involving the following steps: (i) resource and request are checked for compatibility; (ii) if they are compatible, CA is performed; otherwise CC is executed, followed by CA on the compatible part of the request [26]. Mini-ME Java has been used as test oracle and reference for performance comparison, because other reasoners evaluated in Sect. 5.1 do not provide Concept Abduction and Contraction.

Correctness. Mini-ME Swift has correctly performed the CA and CC tests for all the pairs of individuals in the test set.

Performance. As shown in Fig. 5 (average time per matchmaking task) and the lower section of Table 2 (memory peak), Mini-ME Swift significantly outperforms its Java counterpart on the desktop. Memory usage is an order of magnitude lower, also due to the overhead induced by the Java Virtual Machine.

Average time per matchmaking task (\(\mu \)s)

Full size image

The paper introduced Mini-ME Swift, the first OWL reasoner for iOS. It runs natively on iOS for SWoT scenarios, as well as on macOS for classical Semantic Web use cases, providing standard and non-standard inference services. Several optimization techniques have allowed for satisfactory time and memory performance, as evidenced in a comparative assessment with popular Semantic Web reasoners on desktop and mobile testbeds.

Future work concerns the extension of the supported logic language with concrete domains and \(\mathcal {EL}\) (Existential Languages) family. Furthermore, implementing an OWL functional syntax parser will enable performance improvements. Concerning the prototype in Sect. 4, early investigations are ongoing on the integration of semantic-enhanced navigation by embedding inferences within the GraphHopper routing engine for iOS^{Footnote 18}.