as shown in [1]}, the results in terms of coverage of state-of-the-art partitioning methods (e.g., [2]}, [3]}) are very low for the OAEI largebio track (\(0.76\) , \(0.59\)  and \(0.67\)  as the best results for FMA-NCI, FMA-SNOMED and SNOMED-NCI, respectively), thus, making the obtained results even more valuable.

Size ratio.
The results in terms of the size (i.e., search space) of
the selected divisions \({\mathcal {M}} ^n\)  are
presented in Figure REF .
The search space is improved with respect to the original \(\mathcal {M}\)  for all the cases, getting as low as \(5\%\)  of the original matching task size for the FMA-NCI and FMA-SNOMED cases.
The gain in the reduction of the search space gets relatively stable after a
given division size; this result is expected since the context provided by
locality modules ensures modules with the necessary semantically related entities.
The scatter plot in Figure REF  visualise the size of the source
modules against the size of the target modules for the FMA-NCI matching subtasks with divisions of size \(n \in \lbrace 5, 20, 50, 100\rbrace \) . For
instance, the (blue) circles represent points \(\big (\vert Sig(\mathcal {O} _1^{i})\vert , \vert Sig(\mathcal {O} _2^{i}) \vert \big )\)  being
\(\mathcal {O} _1^{i}\)  and \(\mathcal {O} _2^{i}\)  the source and target modules (with \(i\) =1,...,5)
in the matching subtasks of \({\mathcal {M}} ^5\) . It can be noted that, on average, the size of source and target modules decreases as the size of the division increases. For example, the largest task in  \({\mathcal {M}} ^{20}\)  is represented in point \((6754, 9168)\) , while the largest task in  \({\mathcal {M}} ^{100}\)  is represented in point \((2657, 11842)\) .
<TABLE>Computation times. The time to compute the divisions of the matching task is
tied to the number of locality modules to extract, which can be
computed in polynomial time relative to the size of
the input ontology [4]}.
The creation of LexI does not add an important overhead, while the training of
the neural embedding model ranges from \(21s\)  in AMA-NCI to \(224s\)  in SNOMED-NCI.
Overall, for example, the required time to compute the division with 100 matching subtasks
ranges from \(23s\)  (AMA-NCIA) to approx. \(600s\)  (SNOMED-NCI).
Evaluation of OAEI systems
In this section we show that the division of the alignment task enables systems that, given
some computational constraints, were unable to complete an OAEI task.
We have selected the following five systems
from the latest OAEI campaigns, which include novel alignment techniques but failed to scale to very large matching tasks:
MAMBA (v.2015) [5]}, FCA-Map (v.2016) [6]}, SANOM (v.2017) [7]}, ALOD2vec (v.2018) [8]} and
POMap++ (v.2018) [9]}.
MAMBA failed to complete the anatomy track, while FCA-Map, SANOM, ALOD2vec and
POMap++ could not complete the largest tasks in the largebio track.
MAMBA and SANOM threw an out-of-memory exception with \(25Gb\) , whereas FCA-Map,
ALOD2vec and POMap++ did not complete the tasks within a 6 hours time-frame.
We have used the SEALS infrastructure to conduct the evaluation
[10]}, [11]}.
Table REF  shows the obtained results
in terms of precision, recall, f-measure, and
computation times (time for the easiest and the hardest task, and total time for all tasks)
over different divisions \({\mathcal {M}} ^n\)  computed using our strategy.
For example, FCA-Map was run over divisions
with 20 and 50 matching subtasks (i.e., \(n \in \lbrace 20, 50\rbrace \) ) in the FMA-NCI case.
Note that for each matching subtask a system generates a partial alignment \(\mathcal {M}^{S} _i\) , the final alignment for the (original)
matching task is computed as the union of all partial alignments
(\(\mathcal {M}^{S} =\bigcup _{i=1}^{n} \mathcal {M}^{S} _i\) ).
The results are encouraging and can be summarised as follows:

We enabled several systems to produce results even for the largest OAEI
test case (e.g., FCA-Map with SNOMED-NCI).

The computation times are also very good falling under the 6 hours time frame, specially given that the (independent) matching subtasks have been run sequentially without
parallelization.

The size of the divisions, with the exception of FCA-Map, is beneficial in terms of total computation time.

The increase of number of matching subtasks is positive or neutral for MAMBA, POMap++ and ALOD2vec in terms of f-measure, while it is slightly reduced for FCA-Map and SANOM.

Global f-measure results are lower than top OAEI systems;
nevertheless, since the above systems could not be evaluated without the
divisions, these results are obtained without any
fine-tuning of their parameters.

The computation times of the hardest tasks, as \(n\)  increases, is also reduced. This has a positive impact in the monitoring of alignment systems as the hardest task is completed in a reasonable time.


Related work
Partitioning and blocking.
Partitioning and modularization
techniques have been extensively used within the Semantic Web to improve the efficiency when solving the task at hand
(e.g., visualization [12]}, [13]},
reuse [14]}, debugging
[15]}, classification
[16]}).
Partitioning or blocking has also been widely used to reduce the complexity of the
ontology alignment task [17]}.
In the literature there are two major categories of partitioning
techniques, namely: independent and dependent. Independent
techniques typically use only the structure of the ontologies and are not concerned about
the ontology alignment task when performing the partitioning. Whereas
dependent partitioning methods rely on both the structure of the ontology and
the ontology alignment task at hand.
Although our approach does not compute (non-overlapping) partitions of the
ontologies, it can be considered a dependent technique.
Prominent examples of ontology alignment systems including partitioning
techniques are Falcon-AO [2]}, GOMMA [19]}, COMA++ [20]} and TaxoMap
[3]}.
Falcon-AO, GOMMA and COMA++ perform independent partitioning where the clusters of the source and target ontologies are independently
extracted. Then pairs of similar clusters (i.e., matching subtasks) are aligned using standard techniques. TaxoMap [3]}
implements a dependent technique where the partitioning is combined with the matching process.
TaxoMap proposes two methods, namely: PAP (partition, anchor, partition) and APP (anchor, partition, partition).
The main difference of these methods is the order of extraction of (preliminary) anchors to discover pairs of
partitions to be matched (i.e., matching subtasks).
SeeCOnt
[23]} presents a seeding-based clustering technique to
discover
independent clusters in the input ontologies.
Their approach has been evaluated
with the Falcon-AO system by replacing its native PBM (Partition-based Block Matching) module [24]}.
Laadhar et al. [9]}
have recently integrated within the
system POMap++ a hierarchical agglomerative clustering
algorithm to divide an ontology into a set of partitions.
The above approaches, although presented interesting ideas,
did not provide guarantees about the size and coverage
of the discovered partitions or divisions.
Furthermore, they have not been successfully evaluated on very large ontologies.
On the one hand, as reported by Pereira et al. [1]}
the results in terms of coverage of the PBM method of Falcon-OA, and the PAP and APP methods of TaxoMap are very low for the OAEI largebio track.
On the other hand, as discussed in Section , POMap++ fails to scale with the largest largebio tasks.
Note that the recent work in [27]} has borrowed from our workshop paper [28]} the quality measures presented in Section REF . They obtain competitive coverage results for medium size ontologies; however, their approach, as in POMap++, does not scale for large ontologies.
Blocking techniques are also extensively used in Entity Resolution (see [29]} for a survey).
Although related, the problem of blocking in ontologies is different as the logically related axioms for a seed signature play an important role when computing the blocks.
Our dependent approach, unlike traditional partitioning and blocking methods, computes overlapping self-contained modules (i.e., locality modules [4]}).
Locality modules guarantee the extraction of all semantically related entities
for a given signature.
This capability enhances the coverage results and enables the inclusion of the
(semantically) relevant information required by an alignment system.
It is worth mentioning that
the need of self-contained and covering modules, although not thoroughly
studied, was also highlighted in a preliminary work by
Paulheim [31]}.
Embedding and clustering.
Recently, machine learning techniques such as semantic embedding [32]} have been investigated for ontology alignment.
They often first learn vector representations of the entities and then predict the alignment [33]}, [34]}, [35]}.
However, most of them focus on alignment of ontology individuals (i.e., ABox) without considering the ontology concepts and axioms at the terminological level (i.e., TBox).
Nkisi-Orji et al. [36]} predicts the alignment between ontology concepts with Random Forest, but incorporates the embeddings of words alone, without any other semantic components like in our work.
Furthermore, these approaches focus on predicting the alignment,
while our work aims at boosting an existing alignment system. Our framework could potentially be adopted in systems like in [36]} if facing scalability problems for large ontologies.
Another piece of related work is the clustering of semantic components,
using the canopy clustering algorithm [38]}
where objects are grouped into canopies and each object can be a member of multiple canopies.
For example, Wu et al. [39]} first extracted canopies (i.e., mentions) from a knowledge base,
and then grouped the entities accordingly so as to finding out the entities with the same semantics (i.e., canonicalization).
As we focus on a totally different task – ontology alignment,
the context that can be used, such as the embeddings for the words and
ontology entities in LexI, is different from these works, which leads to a different clustering method.

Conclusions and future work
We have developed a novel framework to split the ontology alignment
task into several matching subtasks based on a semantic inverted index,
locality modules, and a neural embedding model.
We have performed a comprehensive evaluation which suggests that
the obtained divisions are suitable in practice in terms of both coverage and size.
The division of the matching task allowed us to obtain results for
five systems which failed to complete these tasks in the past.
We have focused on systems failing to complete a task, but a suitable adoption and integration of the presented framework within the pipeline of any ontology alignment system has the potential to improve the results in terms of
computation times.
Opportunities.
Reducing the ontology matching task into smaller and more manageable tasks may
also bring opportunities to enhance
[(i)]
user interaction [40]},

reasoning and repair [41]},

benchmarking and monitoring [10]}, [11]}, and

parallelization.

The computed independent matching subtasks can potentially be run
in parallel in evaluation platforms like the HOBBIT [44]}. The current evaluation was conducted sequentially as [(i)]

the SEALS instance only allows running one task at a time, and

the evaluated systems were not designed to run several tasks in parallel; for instance, we managed to run MAMBA outside SEALS, but it relies on a MySQL database and raised a concurrent access exception.

Impact on the f-measure.
As shown in Section REF , the impact of the number of divisions on the f-measure depends on the evaluated systems. In the near future we aim at conducting an extensive evaluation of our framework over OAEI systems able to deal with the largest tasks in order to obtain more insights about the impact on the f-measure. In [45]} we reported a preliminary evaluation where YAM-Bio [46]} and AML [47]} kept similar f-measure values, while LogMap [48]} had a reduction in f-measure, as the number of divisions increased.
Number of subdivisions.
Currently our strategy requires the size of the
number of matching subtasks or divisions as input. The (required) matching subtasks may be known before
hand if, for example, the matching tasks are to be run in parallel in a number
of available CPUs. For the cases where the resources are limited or where a
matching system is known to cope with small ontologies, we plan to design an
algorithm to estimate the number of divisions so that
the size of the matching subtasks in the computed divisions is appropriate to the system and resource constraints.
Dealing with a limited or large lexicon.
The construction of LexI shares a limitation with state-of-the-art systems when the input ontologies are lexically disparate or in different languages.
In such cases, LexI can be enriched with general-purpose lexicons (e.g., WordNet), more specialised background knowledge (e.g., UMLS Metathesaurus) or with translated labels using online services (e.g., Google).
On the other hand, a large lexicon may also have an important impact in the computation times. Our conducted evaluation shows, however, that we can cope with very large ontologies with a rich lexicon (e.g., NCI Thesaurus).
Notion of context.
Locality-based modules are typically much smaller than the whole ontology and they have led to very good results in terms of size and coverage. We plan, however,
to study different notions of context
of an alignment (e.g., the tailored modules proposed in
[49]}) to further improve the results in terms of size while keeping the same level of coverage.
This work was supported by the SIRIUS Centre for Scalable Data Access (Norges forskningsråd), the AIDA project (Alan Turing Institute), Samsung Research UK, Siemens AG, and the EPSRC projects AnaLOG, OASIS and UK FIRES. We would also like to thank the anonymous reviewers that helped us improve this work.
