Efficient top-k shortest path query processing in sparse graph databases
Hasan M. Jamil · 2017
While internet graphs are usually dense as a whole, localized sub-graphs are often sparse. In particular, in social networks, the graphs corresponding to users' friends, connections and interactions with others are almost always sparse relative to the entire social graph of which they are a part. In such sparse graphs, reachability queries may suffer unnecessary performance losses if generalized reachability algorithms are used. Classical shortest path queries are among those that incur such losses.