ALL COVERED TOPICS

NoSQL Benchmarks NoSQL use cases NoSQL Videos NoSQL Hybrid Solutions NoSQL Presentations Big Data Hadoop MapReduce Pig Hive Flume Oozie Sqoop HDFS ZooKeeper Cascading Cascalog BigTable Cassandra HBase Hypertable Couchbase CouchDB MongoDB OrientDB RavenDB Jackrabbit Terrastore Amazon DynamoDB Redis Riak Project Voldemort Tokyo Cabinet Kyoto Cabinet memcached Amazon SimpleDB Datomic MemcacheDB M/DB GT.M Amazon Dynamo Dynomite Mnesia Yahoo! PNUTS/Sherpa Neo4j InfoGrid Sones GraphDB InfiniteGraph AllegroGraph MarkLogic Clustrix CouchDB Case Studies MongoDB Case Studies NoSQL at Adobe NoSQL at Facebook NoSQL at Twitter

NAVIGATE MAIN CATEGORIES

Close

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.


  1. Marko A.Rodriguez: @twarko  

Original title and link: Global and Local Graph Ranking (NoSQL databases © myNoSQL)

via: http://markorodriguez.com/2011/03/30/global-vs-local-graph-ranking/