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

Detecting Cycles in a Network Graph With MapReduce

We’ll maintain two types of graph data:

  1. A set of link files where each line represent an edge in the graph. This file will be static.
  2. A set of path files where each line represent a path from one node to another node. This file will be updated in each round of map/reduce.

The general idea is to grow the path file until either the path cannot grow further, or the path contain a cycle, we’ll use two global flags to keep track of that: “change” flag to keep track of whether new path is discovered, and “cycle” flag to keep track whether a cycle is detected.

Isn’t this approach very inneficient (by not being able to account or reuse already processed paths)?

Original title and link: Detecting Cycles in a Network Graph With MapReduce (NoSQL database©myNoSQL)

via: http://horicky.blogspot.com/2013/01/mapreduce-detecting-cycles-in-network.html