Re: Any body here knows the design model of The Oracle of Bacon at Virginia?

John Ruan wrote:
> Acturally what I am interested in is its algorithms.

Well that's a completely different question. The database design and the algorithms to generate the results are totally different things.

> If you input a name of an actor, it will give you the bacon number , or the
> degree of separation from Kevin Bacon.
>
>
> What is the basic algorithms behind this?

The How It Works section discusses this. Their app uses shortest-path algorithms. This is a study called Network Flows. One of the most popular shortest patch algorithms is Djikstra's Algorithm. Do a Google search on this and you will find plenty, including:

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

> How do you come out with this number?

They are simply computing the number of traverses from one node to the next in the network diagram for the path determined to be the "shortest path".

> Perhaps they have a series of tables, with each holding a bunch of actors
> who appreared in one movie.
>
> Say, actors A,B,C appear in one movie table TB1 and A only apprears in this
> movie.
>
> Actor C,D,E appear in another movie table TB2.
>
> If we want to find the degree of separation from A to D, we may JOIN TB1
> with TB2 and we connect A and D through C. In this case, the bacon number is
> 2 from A to C.
>

You don't need multiple tables. One will do. Each row can contain a record (movie title, actor name). From that, the network graph is computed.

If you read their web site, you can see that they also do some precomputations to help speed up their searches.

HTH,
Brian

-- 
===================================================================

Brian Peasland
dba_at_nospam.peasland.net
http://www.peasland.net

Remove the "nospam." from the email address to email me.


"I can give it to you cheap, quick, and good.
Now pick two out of the three" - Unknown

-- 
Posted via a free Usenet account from http://www.teranews.com