this is perhaps worth watching: http://www.youtube.com/watch?v=BT-piFBP4fE&feature=channel
it deals with finding the shortest path in a graph using MR. here at work i don't have audio working so i'm not 100% sure that this is the best way to do it, but it is a start. Miles 2009/1/29 Mark Kerzner <[email protected]>: > Oh, hail to the creator of Luke!Mark > > On Thu, Jan 29, 2009 at 11:20 AM, Andrzej Bialecki <[email protected]> wrote: > >> Hi, >> >> I'm looking for an advice. I need to process a directed graph encoded as a >> list of <from, to> pairs. The goal is to compute a list of longest paths in >> the graph. There is no guarantee that the graph is acyclic, so there should >> be some mechanism to detect cycles. >> >> Currently I'm using a simple approach consisting of the following: I encode >> the graph as <vertex, <neighbor, direction, distance>>, and extending the >> paths by one degree at a time. This means that in order to find the longest >> path of degree N it takes N + 1 map-reduce jobs. >> >> Are you perhaps aware of a smarter way to do it? I would appreciate any >> pointers. >> >> -- >> Best regards, >> Andrzej Bialecki <>< >> ___. ___ ___ ___ _ _ __________________________________ >> [__ || __|__/|__||\/| Information Retrieval, Semantic Web >> ___|||__|| \| || | Embedded Unix, System Integration >> http://www.sigram.com Contact: info at sigram dot com >> >> > -- The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336.
