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

Brian,

Can you do a sql query to find the degrees of separation with your design of table?

"Brian Peasland" <dba_at_nospam.peasland.net> wrote in message news:46b1d997$0$16340$88260bb3_at_free.teranews.com...
> 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
>
Received on Fri Aug 03 2007 - 15:33:29 CDT