On finding the k shortest paths in RDF data
Erwin Filtz, Vadim Savenkov, Jürgen Umbrich · ePubWU Institutional Repository (Wirtschaftsuniversität Wien) · 2016
Finding relationships between entities in RDF data is in the heart of many exploration tasks.General path enumeration algorithms are typically used for computing such relationships, finding top k shortest paths being of special interest.The k shortest paths problem has been thoroughly studied for the weighted graph case, the two most popular generic algorithms are due to Eppstein and to Yen.Along with the Dijkstra's shortest path algorithm upon which they build, these two algorithms are available in most libraries and graph databases.In the RDF context, however, the graph is unlabeled but can have multi-edges, and the found paths can contain cycles, so applying the mentioned algorithms is either impossible (Yen's) or suboptimal.It is a folklore knowledge that the traditional breadth first search (BFS) can be easily adapted to compute the k shortest paths.However, for dense graphs and large k, both time and memory consumption become critical.We discuss two BFS adaptations which are easy to implement and substantially boost performance when solving the k shortest paths problem.