DYNAMIC SOCIAL NETWORK RELATIONSHIP DETERMINATION METHOD AND APPARATUS

1 - 20 . (canceled)

21 . A method for dynamically determining social relationships within a social network using memory efficient bit vectors within a social networking system including a database system, a graphing system, and a server system, the method comprising:

receiving, on the graphing system from the server system, a request for relationship data for a first user within the social network;

computing, within the graphing in response to the request, a bit vector representation of relationship data for the first user based at least in part on a plurality of social network relationships for a plurality of users maintained in the database system;

storing, within computer memory within the graphing system, the bit vector representation of the relationship data for the first user; and

transmitting, from the graphing system to the server system, the bit vector representation of the relationship data for the first user.

22 . The method of claim 21 , wherein storing the bit vector representation of the relationship data includes determining whether to store the bit vector with a sparse or dense representation.

23 . The method of claim 22 , wherein determining whether to store the bit vector with a sparse or dense representation includes determining whether the number of ON bits in the bit vector exceed a pre-defined threshold.

24 . The method of claim 21 , wherein computing the bit vector includes representing all users of the plurality of users that are within a specified social distance of the first user.

25 . The method of claim 21 , wherein computing the bit vector representation includes computing a collection of bit vectors, wherein each bit vector in the collection of bit vectors represents a different degree of social separation of a plurality of users from the first user.

26 . The method of claim 25 , further comprising:

receiving, at the graphing system, a social distance request requesting a subset of the relationship data for the first user based on relationships satisfying the social distance request; and

returning, from the graphing system in response to the social distance request, a first bit vector of the collection of bit vectors, wherein the first bit vector corresponds to a social distance included within the social distance request.

27 . The method of claim 21 , further comprising:

receiving, on the graphing system, a second request for relationship data for the first user;

evaluating, in response to the second request, the bit vector stored in computer memory within the graphing system to identify dirty bits, where dirty bits are indicative of the bit vector not representing up-to-date relationship data; and

recomputing, in response to identifying a dirty bit, the bit vector prior to responding to the second request.

28 . A system comprising:

a server including a processor coupled to memory, the server configured to receive and process requests for data associated with a social network; and

a graphing system including:

a memory device storing a plurality of social network relationships including a social map including entries for a first user;

a processor coupled to the memory device, the processor configured to,

receive, from the server system, a request for relationship data for a first user within the social network;

generate, in response to the request, a bit vector representation of relationship data for the first user based at least in part on a plurality of social network relationships for a plurality of users maintained in a database system;

store, within the memory device, the bit vector representation of the relationship data for the first user; and

transmit, to the server system, the bit vector representation of the relationship data for the first user.

29 . The system of claim 28 , wherein the graphing system is further configured to determine whether to store the bit vector with a sparse or dense representation.

30 . The system of claim 29 , wherein the graphing system is further configured to store the bit vector with a dense representation when the number of ON bits in the bit vector exceeds a pre-defined threshold.

31 . The system of claim 28 , wherein the graphing system is further configured to generate the bit vector to represent all users of the plurality of users that are within a specified social distance of the first user.

32 . The system of claim 28 , wherein the graphing system is further configured to generate a collection of bit vectors, wherein each bit vector in the collection of bit vectors represents a different degree of social separation of a plurality of users from the first user.

33 . The system of claim 32 , wherein the graphing system is further configured to:

receive a social distance request requesting a subset of the relationship data for the first user based on relationships satisfying the social distance request; and

return, in response to the social distance request, a first bit vector of the collection of bit vectors, wherein the first bit vector corresponds to a social distance included within the social distance request.

34 . The system of claim 28 , wherein the graphing system is further configured to:

receive a second request for relationship data for the first user;

evaluate, in response to the second request, the bit vector stored in computer memory within the graphing system to identify dirty bits, where dirty bits are indicative of the bit vector not representing up-to-date relationship data; and

regenerate, in response to identifying a dirty bit, the bit vector prior to responding to the second request.

35 . A non-transitory computer-readable storage medium comprising instructions that, when executed within a social networking system including a database system, a graphing system, and a server system, cause the social network system to perform operations comprising:

receive, on the graphing system from the server system, a request for relationship data for a first user within the social network;

determine, within the graphing in response to the request, a bit vector representation of relationship data for the first user based at least in part on a plurality of social network relationships for a plurality of users maintained in the database system;

store, within computer memory within the graphing system, the bit vector representation of the relationship data for the first user; and

transmit, from the graphing system to the server system, the bit vector representation of the relationship data for the first user.

36 . The non-transitory computer-readable storage medium of claim 35 , wherein the instructions that cause the system to store the bit vector representation of the relationship data include instructions to determine whether to store the bit vector with a sparse or dense representation.

37 . The non-transitory computer-readable storage medium of claim 36 , wherein the instructions that cause the system to determine whether to store the bit vector with a sparse or dense representation include instructions to determine whether the number of ON bits in the bit vector exceed a pre-defined threshold.

38 . The non-transitory computer-readable storage medium of claim 35 , wherein the instructions that cause the system to determine the bit vector include instructions to represent all users of the plurality of users that are within a specified social distance of the first user.

39 . The non-transitory computer-readable storage medium of claim 35 , wherein the instructions that cause the system to determine the bit vector representation include instructions to compute a collection of bit vectors, wherein each bit vector in the collection of bit vectors represents a different degree of social separation of a plurality of users from the first user.

40 . The non-transitory computer-readable storage medium of claim 39 , further comprising instructions to:

receive, at the graphing system, a social distance request requesting a subset of the relationship data for the first user based on relationships satisfying the social distance request; and

return, from the graphing system in response to the social distance request, a first bit vector of the collection of bit vectors, wherein the first bit vector corresponds to a social distance included within the social distance request.

41 . The non-transitory computer-readable storage medium of claim 35 , further comprising instructions to:

receive, on the graphing system, a second request for relationship data for the first user;

determine, in response to the second request, the bit vector stored in computer memory within the graphing system to identify dirty bits, where dirty bits are indicative of the bit vector not representing up-to-date relationship data; and

re-compute, in response to identifying a dirty bit, the bit vector prior to responding to the second request.