[thelist] [MYSQL] - The most effective algorithm for the shortest path.

VOLKAN ÖZÇELİK volkan.ozcelik at gmail.com
Sat Dec 10 04:01:11 CST 2005


Hi list,

We have a site which has several hundreds of thousands of users
(really, the number of members has grown exponentially in the recent
week)
It may possibly grow further since it is a business networking site
and for the time being it does not have any strong counterparts /
rivals around.

It will be better to state my problem with an example:

Here is a (very) condensed contacts table:

ID ContactID
1    5
5    12
5    17
12  26
12  28
12  54

So to go from 1 to 54, the shortest path is 1-5-12-54
This may be achieved by writing nested queries or joining the table
with itself etc.
However it is very resource consuming and as the complexity increases
the resource consumption increases exponentially.

Thus we have disabled the functionality that uses this mechanism
within weekdays (i.e. we only allow it for weekends because there is
considerably lesser traffic on the weekends)

Before forgetting to mention we have a PHP / MySQL setup.

BTW, I have found the following resources:

http:­/­/www­.cs­.cornell­.edu­/courses­/cs312­/2002sp­/lectures­/lec20­/lec20­.htm
http:­/­/research­.microsoft­.com­/research­/sv­/SPA­/

I had done something similar before, but it was not this much complex:
It was going only three levels deep.
Currently the depth of the path is undefined (although there will be
an upper-limit I suppose).
And we really have a high server load (2000+ users logged in within
working hours 200-300 users logged in at night and on weekends).

I thought about using temporary tables. Will it be as overkilling as
nested queries or joining the table with itself?

Have you done something similar?
Do you have any suggestions?

Thank you very much in advance.
--
Volkan Ozcelik
+>Yep! I'm blogging! : http://www.volkanozcelik.com/volkanozcelik/blog/
+> My projects/studies/trials/errors : http://www.sarmal.com/



More information about the thelist mailing list