The oracle of Woody Allen

Do you know about the "Six degrees of separation" theory? It states that "everyone is at most six steps away from any other person on Earth". Do you know about "The Oracle of Bacon" website?

Why actors are so important!? People behind the scenes is as important, or even more, as the actors. This project is dedicated to all of them, specially to one of the best filmmakers: Woody Allen.

This project started as a college work and it has only educational purposes.

How does it work?

Currently, you have available three different requests:

Link two persons: Find the shortest path between two persons.
People at a given number of hops: This computes which persons are at a given number of hops for a given person.
Average number of hops: Computes the average number of hops between one person and any other.

The oracle works with IMDB.com data which is available at no cost for non-comercial purposes. There are 1,925,775 movies, 2,633,235 persons and 21,782,584 links between them stored in the oracle (August 2011).

Try the oracle at joapuipe.dyndns.org/allen!

How does it work internally?

Take a look at the different wiki pages available. This are the most important ones, the ones that you will need to be able to understand how the oracle works:

The graph, this page explains how the relationship among different persons are expressed as a bipartite graph.
Shortest path, the algorithms used in the oracle to determine the shortest path between two persons are explained in this wiki page.
Radix tree, this page explains how the names of the people are maintained in the oracle to allow fast approximate lookups (approximate string matching).
Approximate string matching, this page explains how the approximate string matching is performed using the structure of a trie and the Damerau-Levenshtein distance.

Comments & questions

Please, use the different tools available in Google Code to post your questions, issue reports, comments, etc. Or just write an email to me! I swear to answer!