Algorithm for the Accelerated Calculation of Conceptual Distances in Massive Graphs

Conceptual distance refers to the degree of proximity between two concepts within a conceptualization. It is closely linked with semantic similarity and relationship, but its computation relies entirely on the context of the given concepts. The DIS-C algorithm, which requires using search algorithms such as Breadth First Search, represents an advance in computing the semantic similarity/relation regardless of the type of knowledge structure and semantic relationships. The shortest path algorithm facilitates the determination of the semantic closeness between two indirectly connected concepts in an ontology by propagating local distances. This process is implemented for each concept pair to establish the most effective and efficient paths to connect these concepts. The algorithm identifies the shortest path between the concepts, allowing for the inference of the most relevant relationships between them. This approach contributes to developing a comprehensive understanding of the ontology and enhances the accuracy and precision of the semantic representation of the concepts. However, one of the critical issues is associated with the computational complexity due to the nature of the algorithm, which is errorn3. This paper studies alternatives to accelerate the DIS-C based on approximation and optimized algorithms, focusing on Dijkstra, pruned Dijkstra, and Sketched-based algorithms to compute conceptual distance. Based on the experiments, we discovered that the bottleneck can be avoided using the proposed 2-hop coverages, bringing DIS-C almost linearity.