Using Ontological Information to Accelerate Path-Finding in Large Semantic Graphs: A Probabilistic Approach
Tina Eliassi‐Rad, Edmond Chow · 2005
Many real-world graphs contain semantics. That is, they represent meaningful entities and relationships as vertices and directed edges, respectively. Moreover, such graphs (called semantic graphs) have meaningful types associated with their vertices and edges. These types produce an ontology graph, which specifies the types of vertices that may be connected via a given edge type. Path-finding in large real-world semantic graphs can be a non-trivial task since such graphs typically exhibit small-world properties. In this paper, we use ontological information, probability theory, and heuristic search algorithms to reduce and prioritize the search space between a source vertex and a destination vertex. Specifically, we introduce two probabilistic heuristics that utilize a semantic graph’s ontological information. We embed our heuristics into A * and compare their performances to breadth-first search and A * with a simple non-probabilistic heuristic. We test our heuristics on both unidirectional and bidirectional search algorithms. Our experimental results on two realworld semantic graphs illustrate the merits of our approach.