Global and Local Graph Ranking
Marko A.Rodriguez[1]:
Graph ranking algorithms are all about mapping a complex graphical structure to a numeric vector. […] Most of the discussion on graph ranking is focused on global rank metrics. However, in many situations, local metrics are both more useful and more efficient. They are more useful in situations such as recommendation. They are more efficient in that they do not require a full traversal of the graph and are usually completed in a only a few hops out from the root set.
I’m wondering if combining these two graph ranking approaches would not give a solution for scaling graph databases.
Here is what I’m imagining:
- an application with a set of predefined traversal patterns could precompute and continuously update global and local graph rankings
- both local and global rankings would include the cost of disk access
- global rankings would also include the cost of network access
- background tasks could redistribute/reshard the graph according to the rankings and the set of traversal algorithms defined by the application
- a smart router will be aware of where a specific subgraph corresponding to an algorithm lives on the cluster
To make this possible a graph database should provide:
- notifications about graph changes
- the background graph relocation/sharding algorithms
- ways to plug in custom ranking algorithms
I don’t know if and how well this would work in real life, but the whole approach still sounds very application specific.
Original title and link: Global and Local Graph Ranking (NoSQL databases © myNoSQL)
via: http://markorodriguez.com/2011/03/30/global-vs-local-graph-ranking/
