Name
Abstract | ||
|---|---|---|
Computing shortest paths between two given nodes is a fundamental operation over graphs, but known to be nontrivial over large disk-resident instances of graph data. While a number of techniques exist for answering reachability queries and approximating node distances efficiently, determining actual shortest paths (i.e. the sequence of nodes involved) is often neglected. However, in applications arising in massive online social networks, biological networks, and knowledge graphs it is often essential to find out many, if not all, shortest paths between two given nodes. In this paper, we address this problem and present a scalable sketch-based index structure that not only supports estimation of node distances, but also computes corresponding shortest paths themselves. Generating the actual path information allows for further improvements to the estimation accuracy of distances (and paths), leading to near-exact shortest-path approximations in real world graphs. We evaluate our techniques - implemented within a fully functional RDF graph database system - over large real-world social and biological networks of sizes ranging from tens of thousand to millions of nodes and edges. Experiments on several datasets show that we can achieve query response times providing several orders of magnitude speedup over traditional path computations while keeping the estimation errors between 0% and 1% on average. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1871437.1871503 | CIKM |
Keywords | Field | DocType |
computing shortest path,estimation accuracy,functional rdf graph database,biological network,shortest path,actual shortest path,actual path information,accurate estimation,estimation error,computes corresponding shortest path,large graph,approximating node distance,social networks,database system,graph databases,social network | Average path length,Computer science,Distance,Constrained Shortest Path First,Theoretical computer science,Floyd–Warshall algorithm,Shortest Path Faster Algorithm,Longest path problem,Euclidean shortest path,K shortest path routing | Conference |
Citations | PageRank | References |
77 | 2.17 | 25 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrey Gubichev | 1 | 263 | 11.88 |
| Srikanta Bedathur | 2 | 607 | 43.23 |
| Stephan Seufert | 3 | 279 | 10.69 |
| Gerhard Weikum | 4 | 12710 | 2146.01 |