| Degree of Separation Calculation [message #480] |
Tue, 19 December 2006 11:11  |
Skeptical
Messages: 4
Registered: December 2006 |
Junior Member |
|
|
I'm looking to do permission calculation based on degrees of separation. This would include things like granting permissions based on if the viewing user is your friend, your friend's friend, or your friend's friend's friend.
A friend would be 1 degree away.
A friend's friend would be 2 degrees away.
A friend's friend's friend would be 3 degrees away.
In order to calculate the degree of separation user B is away from user A, the most basic logic would mean the traversal of all of A's friends, and their friends, and so on, until the shortest link is found that connects A and B.
However, this is very database consuming, as each degree of separation can result in an exponential increase in the amount of queries.
A shorter way would be to store on a cache table all second-degree level friendships for all users. Then another table for all third-degree friendships. However, this will obviously lead to a HUGE database, and I'm not sure if this is the best way to go about it. Every time a friendship is added/editted/removed, it could mean the updating of thousands+ of records in the cache table.
Is there a better way to go about doing this?
[Updated on: Tue, 19 December 2006 11:14]
|
|
|
| Re: Degree of Separation Calculation [message #481 is a reply to message #480 ] |
Tue, 19 December 2006 12:41  |
 Peter
Messages: 405
Registered: August 2006 |
Senior Member
Super Guru |
|
|
If something is not done well in the database may be you do not have to do it in the database ?
You're really dealing with graph here which databases do not really do well.
If you expect large volume I would implement separate daemon which holds all graph in memory and is able to perform graph operations as you need them
(find shortest path between two elements, find how many people do you have in your network etc)
On medium sizes singe box should be enough to give you decent response time. For huge sizes you might need more than that.
Peter Zaitsev, MySQL Performance Expert
MySQL Performance Blog - http://www.mysqlperformanceblog.com
MySQL Consulting http://www.mysqlperformanceblog.com/mysql-consulting/
|
|
|
| Re: Degree of Separation Calculation [message #488 is a reply to message #480 ] |
Tue, 19 December 2006 20:22 |
Skeptical
Messages: 4
Registered: December 2006 |
Junior Member |
|
|
So the daemon would generated all of the paths and hold them all in memory, or would it just hold all of the data in memory, and do the path calculations on the fly?
Where can I find such a daemon?
|
|
|
|
Members
Search
Help
Register
Login
Home
