An efficient and scalable algorithm for segmented alignment of ontologies of arbitrary size

摘要: It has been a formidable task to achieve efficiency and scalability for the alignment between two massive, conceptually similar ontologies. Here we assume, an ontology is typically given in RDF (Resource Description Framework) or OWL (Web Ontology Language) can be represented by directed graph. A straightforward approach of ontologies entails O(N^2) computation comparing every combination pairs nodes from ontologies, where N denotes average number each ontology. Our proposed algorithm called Anchor-Flood algorithm, boasting O([email protected]?(N)) on average, starts off with anchor, pair ''look-alike'' concepts ontology, gradually exploring collecting neighboring concepts, thereby taking advantage locality reference graph data structure. outputs set alignments properties within semantically connected subsets entire graphs, which call segments. When similarity comparison made determine whether are aligned not, repeat nodes, neighborhood surrounding anchor iteratively until meets that ''either all collected explored, no new found''. In this way, significantly reduce computational time alignment. Moreover, since only focus segment-to-segment comparison, regardless size our not achieves high performance, but also resolves problem aligning reduces seemingly-aligned actually misaligned pairs. Through several examples large will demonstrate features Anchor-Food algorithm.