Investigative knowledge graph exploration & targeted problem solving with metaphactory’s pathfinding interface
Written by Johannes Trame on . Posted in Search

Finding paths in a graph is a well defined space in mathematics and computer science. The Seven Bridges of Königsberg problem from 1736 - which asked to devise a roundtrip through the city of Königsberg in Prussia while crossing each bridge in the city only once - is one of the most famous real world problems and resulted in the foundations of today's graph theory.
While the term pathfinding might often be associated with finding the shortest path (for example, in a geographical context or in computer networks), the seven bridges problem is a good example showing that the shortest path is not necessarily the optimal or desired path for a given problem or information need.
Although they are graph databases, semantic graph databases lacked native support for pathfinding algorithms for a time (with a few exceptions). This was initially mainly due to the slightly different focus on data integration and a very expressive and standardized query language, SPARQL. SPARQL itself is a graph pattern matching language, which may naturally come with some trade-offs (e.g., in terms of index design, query optimization and computing cost) when applied to other use cases such as pathfinding.
With matured technology, evolution of standards and increased availability of computing resources, nowadays, most RDF databases natively support pathfinding algorithms. Most recently, our partner Ontotext released GraphDB 9.9 featuring sophisticated pathfinding algorithms which are fully compliant with and accessible through standard SPARQL 1.1 service extensions. See [1] and [2].
Following our mission, we have taken up the challenge to enable business users and domain experts to utilize this functionality without having knowledge about SPARQL or the particulars of pathfinding algorithms. When designing metaphactory's new visual pathfinding interface - released just last week with metaphactory 4.3, we focused on two primary usage scenarios: