Methods and systems for using distributed memory and set operations to process social networks

Systems and methods for managing and evaluating a social network. The social network is represented as a graph structure and stored in distributed memory. A viable path from one node that is not directly connected to another node in the graph structure may be determined by traversing the graph in stages, moving outward from each node in stages until common midpoint nodes are found providing a connection between the nodes. When midpoint nodes are found, the paths connecting the one node to the other node may be reconstructed.

COPYRIGHT NOTICE

A portion of this disclosure document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the disclosure document, as it appears in the records of the U.S. Patent & Trademark Office, but otherwise reserves all rights.

TECHNICAL FIELD

One or more implementations relate generally to management and operation of a social network using distributed memory and set operations.

BACKGROUND

Graph-oriented databases are designed for storage of graphical structures to represent information. A typical graph structure in a graph-oriented database represents the significant objects or entities of interest as a set of nodes, connected by edges, the edges describing the relationship between nodes. Further, the nodes and edges may also have properties.

There are several graph-oriented database products available and/or presently in use. For example, Pregel is Google's graph engine, designed to mine relationships from graphs, but it is not capable of delivering real time search results as it is a batch process. Neo4J is an open-source NOSQL graph database, providing an object-oriented, flexible structure with transactional capability, but is not horizontally scalable. HyperGraphDB is a general purpose distributed storage mechanism using a standard key/value store nomenclature to handle graph nodes and edges.

It remains an objective of database designers, architects and researchers to find improved methods of storing and accessing data for use in data operations.

BRIEF SUMMARY

Systems and methods are described for representing a social network and for drawing inferences from it. A social network is defined as having a large number of entities, such as contacts, connected by a plurality of relationships. The social network may be represented as a graph by having nodes represent the entities and edges represent the relationships between the entities, and the graph stored in a graph-oriented database. Typically, a social network models undirected relationships. However, a directed social network may also be modeled.

In one embodiment, the graph of the social network is stored in a distributed memory apparatus using a key/value schema, wherein each of the nodes in the social network is stored as a key in the key/value schema, and for each key, a corresponding value is stored. Advantageously, the stored value is one or more sets of neighbor nodes. A neighbor node is defined as one that is connected to the node of interest by an edge.

According to a described method for finding a viable path from a first node to a second node, the graph of the social network is traversed in stages, outward from the first node and outward from the second node, looking for common neighbors located between them. At each stage, a set of neighbor nodes for the first node is compared with a set of neighbor nodes for the second node. For example, in the first iteration, the neighbor nodes are located at a distance of d=1 from the first node and d=0 from the second node (i.e., the second node itself), respectively. In one embodiment, the comparison step is done by performing an intersection operation on the sets in the distributed memory.

If the comparison finds common nodes, the common nodes represent midpoint nodes in multiple paths connecting the first node to the second node. Those paths are reconstructed and delivered as results to a user.

If the comparison operation does not find common nodes, then a next set of neighbor nodes is obtained for one of the nodes at a time, in alternating stages, and the comparing step is performed again with the new set of neighbor nodes replacing the prior set. The next set of neighbor nodes is located one edge further away from the node of interest than those in the prior set.

In order to obtain the next set of neighbor nodes, the sets of neighbor nodes at distance d=1 for the prior set, which are already in distributed memory, are combined using a union operation. This results in a new intermediate set. Difference operations are then used to subtract the prior neighbor sets from this intermediate set, thus yielding the next set.

DETAILED DESCRIPTION

Systems and methods are described for representing a social network as a graph and storing the graph in a distributed memory system, and for operating on the graphs to infer relationships and other information over the social network.

A distributed memory system may be implemented using open-source memcached storage technology, which provides a horizontally scalable resource that allows for fast and efficient data processing, including concurrent processing, enabling greatly improved speeds for data access and query operations. Techniques for using a distributed memory system to store and operate on sets of data are described in co-pending U.S. patent application Ser. No. 13/104,193, entitled Methods and Systems for Latency-Free Database Queries, and in co-pending U.S. patent application Ser. No. 13/104,226, entitled Methods and Systems for Latency-Free Contacts Search, the disclosures of which are incorporated herein by reference. These techniques include basic set operations, such as union and/or intersection of sets, and represent the preferred methods for carrying out the set operations described herein.

Graph-oriented databases are generally known, wherein the database is organized to store graphical representations of data, for example, nodes (representing entities) connected by edges (representing relationships between entities). The representation of a social network as a graph is a natural application for a graph-oriented-database, since a social network can readily be modeled as a plurality of nodes representing the entities, usually individuals or business contacts, and a plurality of edges connecting the various nodes and representing the relationships between the connected entities.

Advantageously, the systems and methods described herein use the same general graphical model of nodes and edges, but store and use the graphs in a different manner, using a key/value schema with a distributed memory system. Each node of the graph is stored as a key, and for each key/node, a set of “neighbor nodes” is stored as the value corresponding to the key. The sets of neighbor nodes stored in the distributed memory system can be used in fast and efficient set operations in the manner described in the co-pending applications identified above, which are incorporated into simple methods as described herein in order to evaluate a graph to draw inferences in support of any legitimate query over the social network database.

As used herein, a set of neighbor nodes Ndis defined as those nodes that are located at a specific distance d from the node of interest. For example, the set of neighbor nodes at a distance of 1 from the node of interest is designated N1, and consists of those nodes that are connected along a single edge to the node of interest, and therefore have a direct relationship with the node of interest. The set of neighbor nodes N2are located at a distance of 2 from the node of interest and do not have a direct relationship with the node of interest, but are connected only indirectly through another node. This indirect relationship also has a path length of 2, i.e., the nodes are connected by two edges, but may be useful to the node of interest, for example, in order to gain an introduction through the common node. Likewise, longer path lengths may yield indirect connections, but the value or utility of the connection generally diminishes with length or distance from the node of interest.

Initially, only the set of neighbor nodes having a direct relationship with the key/node of interest is stored in the key/value store. However, if there is available capacity and suitable demand, additional sets of neighbor nodes may also be routinely stored, i.e., sets of nodes at larger distances. It makes sense to do so in order to avoid duplicative operations, for example, involving popular nodes. Therefore, at a minimum, an implementation strategy may also store sets of neighbor nodes for popular nodes that are frequently used in query operations.

The nodes and/or edges can also have properties associated with them that may be used in weighting or filtering of the graphs, or possibly, the results provided to a user. The properties may also be used to provide strength to inferences drawn from evaluating the social graph.

The methods described herein are useful for finding a short path between a first node (origin) and a second node (destination). This is done by traversing the graph in stages, and comparing sets of neighbor nodes for the origin and destination (using a set intersection operation) until one or more common nodes are found. The common nodes represent midpoints in multiple paths connecting the nodes of interest, and the full path(s) may be obtained by reconstructing each half of the path from the midpoint back to the origin in one direction and to the destination in the other direction.

In the first stage, neighbor nodes located at a distance of 1 from the origin are compared (intersected) with neighbor nodes located at a distance of 0 from the destination (that is, the destination node itself). If the intersection yields a null set (no common nodes), then the technique retrieves a new set of neighbors for the destination and perform an intersection again; then retrieves new origin neighbors-intersect again-then new destination neighbors-intersect again-etc., until a solution is found or the process simply ends as yielding a path too long.

When new neighbor sets are needed, they may be obtained by retrieving all the values stored with nodes of the prior neighbor set, and performing a union of all those nodes, then subtracting duplicates.

A database is a well known component of computer-based systems providing structured storage for electronic data records. Although the present disclosure is focused on graph-oriented databases, the physical requirements and demands for such a system do not differ greatly from that of a standard relational database—only the management and allocation of resources differ. The database is accessed by users through computer-implemented devices in a computing environment. The database is configured to allow storing, indexing, searching and retrieving of a large number of data records, as well as security and backup for the system. The database is typically hosted on a single server, and management of the database is handled by a software utility called something like DBMS, which runs on the database server and is programmed in accord with application needs. Although it is typical for multiple databases to be hosted on a single server, database resources are typically limited by physical server capacity, and additional server capacity may sometimes be required for operations involving large data sets.

In one embodiment, illustrated inFIG. 1, an on-demand, multi-tenant database system (“MTS”)16is operating within a computing environment10, wherein user devices or systems12a-12naccess and communicate with MTS16through network14in a known manner. As used herein, the term multi-tenant database system refers to those systems in which various elements of hardware and software of the database system may be shared by one or more customers. For example, a given application server may simultaneously process requests for a large number of customers, and a given database table may store rows upon rows of data for an even larger number of customers. As used herein, the term query refers to a set of steps used to access information in a database system. More detailed MTS embodiments are shown inFIG. 5andFIG. 6, described below.

User devices12a-12nmay be any computing device, such as a desktop computer or a digital cellular telephone, and network14may be any type of computing network, such as the Internet, as described in more detail below.

The operation of MTS16is controlled by a computer-implemented processor system17resident on server16a, and network interface15manages inbound and outbound communications with the network14from the MTS. One or more applications19are managed and operated by the MTS16through application platform18. For example, a database management application as described herein runs on application platform18.

MTS16provides the users of user systems12a-12nwith managed access to many features and applications, including tenant data storage22, which is configured through the MTS to maintain tenant data for multiple users/tenants. Tenant data storage22may be physically incorporated within MTS16, or may alternatively be configured as remote storage, or alternatively, or in addition to, may be serviced by a distributed memory system28.

The distributed memory system28is coupled to the MTS server16a. The distributed memory28is comprised of a plurality of memcached storage30a. . .30n, and corresponding memcached storage servers29a. . .29n. The distributed memory28is used to store indexed graph structures in a key/value schema, and such storage may be permanent and/or temporary. Also, the distributed memory28may be used for performing database operations as directed by the database manager program.

Memcached storage is a general purpose distributed memory caching system that is an open source tool, and is horizontally scalable to rather arbitrary lengths. In short, a number of memcached server instances listen on user-defined ports to access spare memory on one or more machines. All the pieces of spare memory thus form a giant hash table that may be distributed across multiple machines. See Fitzpatrick,Distributed Caching with Memcached,124 Linux Journal, August 2004 (http://www.linuxjoumal.com/article/7451). The latest memcached storage software release v.1.4.6 is available on the Internet at http://memcached.org/.

Memcached storage provides an attractive alternative to traditional client/server architectures by providing a relatively arbitrary allocation of memory resources to applications, and managing those memory resources in a manner that is invisible to the client. The memory resources available to a memcached storage system may be spread across multiple servers.

Prior co-pending U.S. application Ser. Nos. 13/104,193 and 13/104,226, filed May 10, 2011, incorporated by reference, describe the use of a distributed memory apparatus to perform fast set operations, such as intersection and union. It is preferred that the same techniques be used on the data sets described below to quickly and efficiently perform set operations, but in this disclosure we will only refer to the use of the intersection and union operations generically, and the reader should refer to the co-pending applications for details of the specific data operations.

4. Representation and Storage of Graphs

A graph-oriented database uses graph structures to represent and store information. For example, one graph structure is commonly described as a set of nodes n0. . . nmand a set of edges {ni, nj}, the edges connecting various nodes in accord with some relationship schema. Both the nodes and the edges may have properties associated with and stored with them Typically, the nodes represent a large number of entities or objects of interest, and the edges represent connections or relationships between the various objects. For example, in a social network built on business contacts, the nodes represent individual contacts and generally have properties associated with the contacts, such as company, title, email address, telephone number, etc., while the edges represent connections between individuals that know each other and the associated properties describe the relationship, such as boss, friend, family, etc.

In some social networks, the edges are undirected and symmetrical, and these type of networks are described first. That is, the nodes represent two friends who simply know each other socially, and the relationship goes both ways equally, without a superior or inferior status associated with one or the other. In some relationships, however, the edges may be directed; that is, the relationship is not symmetrical but instead points only in one direction. We also describe the small changes to the methods that are required for the directed case. For example, the nodes representing a boss and his employee would be connected by a directed edge, indicating the superior position of the boss. Other criteria could be used to assign a weight, or a preference, or a ranking of some sort, to a particular edge, or to provide an indication that the edge is specifically known to be directed or non-directed.

Further, rather than describe and store graphs strictly in terms of “nodes” and “edges” as is conventional, the methods described herein define and store each node along with one or more sets of “neighbor nodes” rather than edges. In particular, a graph is stored into distributed memory using a key/value storage schema, wherein the key is the identity of the node and the value is the set of neighbor nodes. This allows for fast and efficient data operations to be performed on these sets using the set operations described in co-pending applications identified above.

For example,FIG. 2Aillustrates an undirected graph51ahaving nodes labeled A through I and edges labeled52athrough61aconnecting various of the nodes. In this example, graph51arepresents a portion of a social graph wherein the nodes represent contacts, and the edges represent relationships between the contacts. Thus, from graph51a, person A knows person B and they are connected through an undirected relationship shown by edge52a; person A knows person C and they are connected through an undirected relationship edge53a; person B knows persons A, D and E through undirected edges52a,55aand54a, respectively; and so on.

It is evident from looking at graph51aofFIG. 2Athat the immediate neighbors of node A are nodes B and C; that is, nodes B and C are located at a distance of 1 from node A. Thus, we can get from A to B in one hop along edge52a. Likewise, we can get from A to C in one hop along edge53a. A typical query from person A is: “which of my friends knows person D?” We can see fromFIG. 2Athat node D is connected by one hop to nodes B and C, which are the immediate neighbors of node A. By performing an intersection operation using the immediate neighbors of node A with the immediate neighbors of node D yields the result which is apparent fromFIG. 2A, i.e., that nodes B and C define that intersection set; that is, friends B and C both know persons A and D, and according to our simple information, either one would be a good path for an introduction from A to D. If there were other information that made the path through either B or C easier or preferable, then such information could be taken into account in weighting the different paths, preferably to filter or rank the results before passing to the user.

FIG. 2Billustrates a graph51b, which is similar to that ofFIG. 2Aand has the same nodes, except that each of the edges now has an arrow head pointing in one direction, i.e., the edges connecting the nodes are directed in the manner indicated by the arrow end of the edge. Thus, from graph51b, person A likes person B and they are connected through a directed relationship shown by edge52b; person A likes person C and they are connected through directed relationship edge53b; person B likes persons D and E and they are connected through directed edges54band55b, respectively, and so on. We can use this graph to answer the query from person A: “which of my friends likes person D?”

Since edge52bis directed from node A to node B, we can get from A to B in one hop along edge52b. Likewise, edge53bis directed from node A to node C, so we can get from A to C in one hop along edge53b. In a directed graph, we define the “out-neighbors” as those nodes that can be reached in one forward hop, and nodes B and C are thus considered out-neighbors of node A. We can see fromFIG. 2Bthat node D is connected by one hop backwards (i.e. against the direction of edges55b,56b) to nodes B and C, which we know from above are also the out-neighbors of node A. We thus define the “in-neighbors” as those nodes that can be reached in one backward hop, and nodes B and C are thus considered in-neighbors of node D. A quick intersection of the out-neighbors of node A with the in-neighbors of node D yields the expected result that nodes B and C define that intersection set.

5. Determining Short Paths

A simple method300to determine viable short paths for person A to be introduced to person D is illustrated inFIG. 3. The process300is initiated when a user (e.g., person A) enters a query into a search interface for the database, such as “which of my friends knows person D?” This query is received by the database in step301. The database processes the query in step302to identify relevant information for determining a short path. Since the source of the query is person A, the origin or starting node in this case is identified as node A, and the destination or ending nodeis clearly identified in the query as person D=node D. A distance counter d is initialized and set equal to 0 in step303.

In step304, the first sets of values to be operated on are retrieved and loaded into temporary storage in the distributed memory. In this first pass, the set of values stored for neighbor nodes located at distance d+1 from the origin node A, namely N1(A), is retrieved and stored in a temporary buffer A. Also, the set of values stored for neighbor nodes at distance d from the destination node D, namely N0(D), is retrieved and stored in a temporary buffer B. Initially, the neighbor sets having a direct connection to the origin N1(A) and the destination node itself N0(B) are indicated in the first iteration. These sets of values are already stored in distributed memory as the values associated with immediate neighbors of key/node A and the values associated with key/node D, and are quickly retrieved for temporary processing.

In step305, an intersection operation is performed on the sets of values stored in temporary buffers A and B. In step306, if the result of the intersection operation is not a null set, then the result set is stored in step307. The result set identifies midpoint nodes of multiple paths that connect the origin node and the destination node.

In step308, the paths back to the origin and the destination are reconstructed from the midpoint points. This step is described in more detail below. In step309, the results are filtered or sorted if necessary, then delivered to the user in step310.

If the result of the intersection operation in step306is the null set, then the distance counter d is incremented in step311. In step312, the distance counter d is compared to a preset maximum value, such as 5. If the distance counter d is larger than the maximum value, then any possible path from node A to node D is becoming quite long, that is, through too many intermediaries, and therefore may not even be a viable path. Therefore, the process delivers a message to the user in step313that the search returned no results, then ends.

If the distance counter d does not exceed the maximum value in step312, then in step314, the first sets of neighbor nodes N1(D) for the destination are obtained, i.e., those nodes at a distance of d=1 from the destination. These first sets of neighbor nodes for the destination are also typically stored in distributed memory, thus they can be quickly retrieved and placed into temporary buffer D for another intersection operation. However, if the sets of neighbor nodes are not already stored in distributed memory, then they must be calculated. This calculation is described below with reference toFIG. 4.

When the next sets of neighbor nodes for the destination N1(B) have been placed in temporary buffer D, an intersection operation is performed again in step315between temporary buffers A and D. The question of whether a null set results from the operation is considered in step316. If not, then the process jumps to step307to store the results. If so, then the next set of neighbor nodes for the origin node N2(A) are obtained (from storage, or calculated) and stored in buffer A in step317, and an intersection operation is again performed in step318. The null set question is again considered in step319, and if there is a result from the intersection operation, the process jumps to step307to store the results. If a null set results, then the process returns to step311to increment the distance counter d and try again. The process continues for additional iterations, retrieving and using sets of neighbor nodes located further away from the nodes of interest, until either a result is obtained or the distance counter d reaches its maximum preset value.

One embodiment for calculating next sets of neighbor nodes, for example, when needed in step314or317, is process350shown inFIG. 4. In step351, each neighbor node in the prior sets of neighbor nodes for the node of interest is identified and is already stored in distributed memory. In step352, the neighbor nodes located at distance d=1 from each neighbor node in the prior sets stored are retrieved from distributed memory. In step353, a union operation is performed to add together all the new neighbor nodes identified in step352. The intermediate result set in step354thus includes sets of neighbor nodes for each neighbor node in the prior iteration, including possible duplicate entries. In step355, any duplicate entries are removed using a set subtraction operation. Specifically, the prior sets are subtracted from the result set obtained in step354. The result set in step356now contains the next set of neighbor nodes for one of the origin or destination nodes, and these results are stored in the appropriate buffer in step314or317. A recursive formulation for computing Nd(v), that is, a set of neighbor nodes for node v, is shown in Equation 0 below:
Nd+1(v)=UwεNd(v)N1(w)−Nd(v)−Nd−1(v),d≧1  (0)

In sum, the method described essentially traverses the graph outward from the origin and outward from the destination, looking at successive pairs of neighbor sets until an intersection of those sets yields a result set indicating nodes in common. When a result set is obtained, the nodes in the result set are considered midpoint nodes on multiple paths that connect the origin and destination. Each of the paths is then reconstructed, from the origin node to the midpoint node, and from the midpoint node to the destination node, and the results, namely a list of viable paths from origin to destination, are delivered to the user—all substantially in real time.

In general, the set N of neighbors of a node n can be written as:
N(n)=m|{n,m}εE.

That is, the set N of neighbors of node n is the set of all nodes m for which {n,m} is an element of the set of edges E. The graph is then stored in distributed memory as n→N(n); that is, the node n is stored as the key and the set of neighbors N(n) is stored as the value corresponding to the key using a two level tree structure in distributed memory as described in co-pending U.S. patent application Ser. No. 13/104,193 and co-pending U.S. patent application Ser. No. 13/104,226. As a result, advantageously, all of the edges containing node n are immediately available in a single fetch operation.

FromFIGS. 2A and 2B, we saw that the set of immediate neighbors (A) or N1(A) N(A) was the set of nodes at a distance of 1 to node A. node A More generally, Nd(n) is the set of nodes at distance dd to nn. Computation of Nd(n) Nd(n) was discussed previously. InFIG. 2A, the set of neighbors at a distance of 1 to node A are nodes B and C, and this relationship can be written as N1(A)={B,C}; the set of neighbors at a distance of 2 to node A are nodes D, E and F, and this relationship can be written as N2(A)={D,E,F}; and so on. Because of the directionality of the edges in the example ofFIG. 2B, the set of in-neighbors of node D, that is, nodes B and C, are located against the direction of edges105and106, and the direction is backward, so the distance d=−1d=−1, and this relationship can be written as N−1(D)={B,C}.

Upon initialization of the graph database, only the set of immediate neighbors are stored with a node. However, depending on need and available capacity, more distant neighbor sets may also be stored with a node, either on a temporary or permanent basis. For example, it may be possible that neighbor sets that are 2 or 3 hops away may become useful because of the popularity of a particular node, and thus keeping these sets in ready storage will facilitate faster and more economical processing of the large number of queries involving the popular nodes by avoiding having to recalculate the same sets over and over.

A path is defined as a sequence of edges linking two nodes. The length of a path is the number of edges in it. Two nodes are said to be connected if there is a path connecting them. The distance between two connected nodes is the length of the shortest path connecting them. However, a short path, and not the shortest path, may be adequate and/or desirable as a solution for a variety of reasons. Thus, the task at hand for the database is to find multiple short paths, if there are any, between two given nodes. The methods described herein leverage the graph in distributed memory, and can also leverage efficient implementations of various set operations in distributed memory, as described for example in the co-pending applications identified above.

While the model is based on a general distributed graph, a social graph is an interesting application of the model where the following is true: (i) the graph is quite large (millions of nodes); (ii) a single node (the user) is seeking to connect with one other node or a small set of other nodes; and (iii) the utility or viability of a path dissipates with distance—a friend of a friend of a friend of a friend is still a stranger. Therefore, in realistic terms, only a small part of the whole graph should need to be traversed for any one query.

Consider the case of two connected nodes (a, b) (a, b) and let m mdenote a positive integer. A useful matrix Im(a,b) is defined in Equation (1) below:
Im(a,b)=N[m/2](a)∩N[m/2](b) form>1m≧1  (1)

It is noted that I1(a,b)=∅ is a special case for m=1. Since N0(v) N0(v) is the set of nodes at distance of 0 from node v, namely {v} itself, then as a consequence, N0(a)∩N0(b) is the empty set because a and b are different nodes.

Initially, we consider only the shortest paths. For example, let the function S(m,n,d) denote all shortest paths between two connected nodes (m,n) at a distance d>1:

Equation 2 first finds the product of ordered sets representing neighbors at different distances from the nodes of interest, then identifies paths to those sets, one side of the arguments delivering paths from m→w and the other side delivering paths from w→n.
λxId(a,b)a×b[m]×shortestpathsm,n,d

Note that to compute shortest paths between two nodes m and n, the distance between them must be computed. This is simply the smallest d for which the matrix Id(m, n) is not empty. Further, although Equation 2 is a recursive function, it can just as easily be performed iteratively starting from shorter to longer paths. This would allow a server to return shorter paths while still in the process of generating longer ones. By storing intermediary results in distributed memory, it is not necessary for the request for additional results to be performed by the same server as the initial request.

Once this distance d is known, the matrix Id(m,n) is computed. Id(m, n) Next, for every node w in the matrix, the following are recursively computed: (i) the shortest paths from m to w; and wId(m, n) (ii) the shortest paths from w to n. ww Next, every path computed in step (ii) is appended to every path computed in step in step (i). The result is a list of all the shortest paths from m to n. The intermediate results are stored in distributed memory so that they can be used in other shortest path computations.

Ideally, for a certain maximum distance k, k which is usually no larger than 5 for modeling social networks, the entire Ik(a,b) Ik(a, b) matrix of neighbors, i.e., over all pairs of nodes a,b, is stored in distributed memory. If so, then queries of the form S (m,n,k′) shortestpaths (m, n, k′) for any k′≦k can be performed exceptionally fast. Set operations as in Equation 1 are then not needed; just an iterative enumeration of the paths as defined by Equation 2.

The methods described provide ample opportunity for parallelization in an actual implementation. The expansion of the neighbor sets, the calculation of the intersections, and the recursive calls to paths each allows for concurrency. This concurrency may be exploited locally in a particular server and globally among a set of servers attached to distributed memory, thus making the system horizontally scalable, by having multiple levels of cache, both in distributed memory and in a local cache from which data is aged out.

In order to effectively use distributed memory, a naming scheme is needed for intermediate results. The basic graph is composed of three kinds of sets representing edge sets in the graph:

“id(n)” represents the identity edge on n and is composed of n's N0neighbor—itself;

“id(n)|edgeType” contains all the N1neighbors of n along edges of type edgeType;

“id(n)|edgeType[d]” contains all the Ndneighbors of n along edges of type edgeType; and

“edgeType|id(n)” contains all the nodes for whom n is a N1neighbor along edges of type edgeType.

The intersection sets and the paths also need to be specified:

“midpoint:n$m|edgeType[d]” identifies the intersection nodes at distance d; and

The methods described above efficiently find all shortest paths. However, as was also noted above, in some applications only a short path need be found, not necessarily the shortest path.

Acyclic paths of length d+1 are computed as follows. To describe it we need some additional notation. Let S(m,n) and S+1(m,n)S(m, n) S+1(m, n) denote the sets of paths from mm to nn of lengths dd and d+1 respectively. There are two cases.
UwεId+1(m,n)S(m,w)×S(w,n)  case 1:
UwεId(m,n)S+1(m,w)×S(w,n)∪S(m,w)×S+1(w,n)  case 2:

The first case yields paths of length d+1 from nodes mm to nn whose mid-point is in the matrix Id+1(m,n). Id+1(m,n) The second case yields paths of length d+1 from nodes m to n mn whose mid-point are not in the matrix Id+1(m,n) Id+1(m, n) but which do have a vertex in Id+1(m,n). Id(m, n)

Lemma 1: The union of the above two expressions yields all paths of length d+1 from m to nmn.

Proof: Let PmnPmndenote any path of length d+1 d+1 from nodes mnm to n. It suffices to show either (i) that there are nodes w in the path PmnwPmnsuch that wεId+1(m,n) or (ii) that there exists nodes w in the path Pmnsuch that wεId(m, n). Let x denote the midpoint of path Pmn, i.e.,

Pmx=⌈d+12⌉.
Assume that x is not in the matrix Id+1(m, n). Then exactly one of the following holds: (1) there is a path Qmxfrom m to x of length

⌈d+12⌉-1;
or (2) there is a path Rxnfrom x to n of length

In the first case, let u be the left-neighbor of x on the path Qmx. In the second case, let u be the left-neighbor of x on the path Pmx. In either case, uεId(m, n).

Paths from m to n of length d+1 cannot contain a cycle because d is the distance between m and n.

To compute paths of length d+2, let S+2(m, n) denote the set of acyclic paths of length d+2 from m to n. The set:
UwεId+2(m,n)S(m,w)×S(w,n)
is the set of paths of length d+2 from m to n whose mid-point is in the matrix Id+2(m, n). Since S(m, w) and S(w, n) are sets of shortest paths between the end points, a path in S(w, n) appended to a path in S(m, w) intersects only at w. Consequently, the concatenated path is acyclic.

The set:
UwεId+1(m,n)S(m,w)×S+1(w,n)∪S+1(m,w)×S(w,n)
is the set of all paths of length d+2 from m to n which contain a vertex in the matrix Id+1(m, n). Every path in S(m, w), S+1(w, n), S+1(m,w), and S(w, n) is acyclic. Moreover, it is easy to prove that any path in S+1(w, n) appended to any path in S(m, w) intersects only at w. Similarly, any path in S(w, n) appended to any path in S+1(m, w) intersects only at w. Thus every path in the result set is acyclic.

The set:
UwεId(m,n)S+1(m,w)×S+1(w,n)∪S+2(m,w)×S(w,n)∪S(m,w)×S+2(w,n)  (3)
is the set of paths of length d+2 from m to n which contain a vertex in the matrix Id(m, n). These paths can have cycles, however their structure is very limited, as the following Lemma 2 shows.

Lemma 2: Let Pmn=Pmw·Pwndenote a path of length d+2 from m to n where node wεId(m, n). Then, if Pmwand Pwnintersect at some node in addition to w, then Pmn=m−vwv−n.

Proof: Suppose Pmwand Pwnintersect at some vertex v≠w and Pmn≠m−vwv−n. Then Pmn=mavbwcvdn, where a, b, c and d are (possibly empty) sequences of vertices and b and c are not both empty. Consider the path mavdn. Since the distance between m and n is d, |mavdn|≧d. Since b and c are not both empty, vbwcv has a path of length≧3. Thus |mavbwcvdn|≧d+3 which contradicts |Pmn|=d+2.

From Lemma 2 above, by removing from the result set the paths found by Equation (3) in which the neighbors of w are identical, all paths with cycles in them are eliminated. We concentrate on these cases because they match the base use case. If m is not directly linked to n, then a path of length d+2 already has at least 3 intermediate nodes and likely contains all the paths of interest. For paths of length greater than d+2, checking for cycles becomes more onerous and devolves to checking each pair of path segments as they are placed together.

I[m/2]⁡(b)⁢I⌊m2⌋⁡(b)
is the set of nodes v where b is reachable from v via a directed path of length [m/2] and not by a shorter path. Equation (2) is unchanged, but Equation (0) becomes:
Od+1(v)=UwεOd(v)O1(w)−Od(v)−Od−1(v),d≧1Od+1(v)=UwεOd(v)O1(w)−Od(v)−Od−1(v),d≧1
Id+1(v)=UwεId(v)I1(w)−Id(v)−Id−1(v),d≧1

For weighted graphs, or more generally, where there is some data structure attached to the edges and/or the nodes, the values are preferably kept in a separate data structure that shadows the graph structure. Thus, for every neighbor set s there is a value set w:s containing the values and a function w:s(m) to retrieve the value of m. Values for node n are in w:id(n) and values for its neighbors are in w:id(n)/edgeType. The value may be a record or just a single value. Regardless, the value is simply referred to as the “weight.”

To use these values as part of a method to determine short paths, such as those described above, a composition function “*” is defined, over weights, so that if path a→b has weight i and path b→c has weight j, then path a→b→c has weight i*j.

Note that path a→d→c may have a different weight, so that determining a specific weight for path a→c would require applying a function over the sets, like min or max, but the function could be used to sort the order in which results are extended, rather than to adjust the methods described

To keep things simple, we can assume that the composition function * is associative. Then, a weight is assigned to each path as follows:

1) for paths (n,m,1), which in fact consists of the single path [m] if there is an edge from n to m, the weight is: id(n)/edgeType(m);

2) since the composition function * is associative, if path a has weight a_w and path b has weight b_w, then the concatenation of a and b has weight a_w*b_w.

As it turns out, the problem of finding acyclic weighted paths may be efficiently solved by a variant of the previous methods. The previous methods specifically enumerate acyclic paths in order of non-decreasing path length. Here, however, we need to enumerate paths in order of non-decreasing weight rather than length. That these two problems are indeed different may be noted by observing the following: in edge-weighted graphs, lighter paths can in fact contain more edges than heavier ones.

The variant method uses a different definition of a neighborhood of a node. In the previous method, the neighbor set Nd(n) was defined as the set of nodes at distance d from node n. In the variant method, a new neighbor set Nl(n) is defined Nl(n) to denote the set of nodes having a path of length l to n. The variant method uses the following variant of Equation (2).

If node bεNl(a), then the weight of the composite edge from node a to node b is Nl(a,b), Nl(a, b) defined as:
+{vεNn−1(a)|bεN1(v)}Nn−1(a,v)*N1(v,b).

The weight of a node c in the set Im(a,b), is defined as:
Im(a,b)(c)=N[m/2](a,c)*N[m/2](b,c)

This expression returns a weight for each node for every length path, which can be used to return paths in a weighted order. All that remains is to define the functions + and * in a manner appropriate to the application. In a simple weighted graph, * is defined as addition and + as minimum.

7. Detailed System Overview

FIG. 5is a block diagram of an exemplary environment110for use of an on-demand database service. Environment110may include user systems112a-112n, network114and system116. Further, the system116can include processor system117, application platform118, network interface120, tenant data storage122, system data storage124, program code126and process space128. In other embodiments, environment110may not have all of the components listed and/or may have other elements instead of, or in addition to, those listed above.

User system112a-112nmay be any machine or system used to access a database user system. For example, any of the user systems112a-112ncould be a handheld computing device, a mobile phone, a laptop computer, a work station, and/or a network of computing devices. As illustrated inFIG. 5(and in more detail inFIG. 6), user systems112a-112nmight interact via a network114with an on-demand database service, which in this embodiment is system116.

An on-demand database service, such as system116, is a database system that is made available to outside users that are not necessarily concerned with building and/or maintaining the database system, but instead, only that the database system be available for their use when needed (e.g., on the demand of the users). Some on-demand database services may store information from one or more tenants into tables of a common database image to form a multi-tenant database system (MTS). Accordingly, the terms “on-demand database service116” and “system116” will be used interchangeably in this disclosure. A database image may include one or more database objects or entities. A database management system (DBMS) or the equivalent may execute storage and retrieval of information against the database objects or entities, whether the database is relational or graph-oriented. Application platform118may be a framework that allows the applications of system116to run, such as the hardware and/or software, e.g., the operating system. In an embodiment, on-demand database service116may include an application platform118that enables creation, managing and executing one or more applications developed by the provider of the on-demand database service, users accessing the on-demand database service via user systems112a-112n, or third party application developers accessing the on-demand database service via user systems112a-112n.

The users of user systems112a-112nmay differ in their respective capacities, and the capacity of a particular user system112a-112nmight be entirely determined by permission levels for the current user. For example, where a salesperson is using a particular user system112a-112nto interact with system116, that user system has the capacities allotted to that salesperson. However, while an administrator is using that user system to interact with system116, that user system has the capacities allotted to that administrator. In systems with a hierarchical role model, users at one permission level may have access to applications, data, and database information accessible by a lower permission level user, but may not have access to certain applications, database information, and data accessible by a user at a higher permission level. Thus, different users will have different capabilities with regard to accessing and modifying application and database information, depending on a user's security or permission level.

User systems112a-112nmight communicate with system116using TCP/IP and, at a higher network level, use other common Internet protocols to communicate, such as HTTP, FTP, AFS, WAP, etc. In an example where HTTP is used, user system112a-112nmight include an HTTP client commonly referred to as a browser for sending and receiving HTTP messages to and from an HTTP server at system116. Such an HTTP server might be implemented as the sole network interface between system116and network114, but other techniques might be used as well or instead. In some implementations, the interface between system116and network114includes load sharing functionality, such as round-robin HTTP request distributors to balance loads and distribute incoming HTTP requests evenly over a plurality of servers. At least as for the users that are accessing that server, each of the plurality of servers has access to the data stored in the MTS; however, other alternative configurations may be used instead.

One arrangement for elements of system116is shown inFIG. 5, including a network interface120, application platform118, tenant data storage122for tenant data123, system data storage124for system data125accessible to system116and possibly multiple tenants, program code126for implementing various functions of system116, and a process space128for executing MTS system processes and tenant-specific processes, such as running applications as part of an application hosting service. Additional processes that may execute on system116include database indexing processes.

Several elements in the system shown inFIG. 5include conventional, well-known elements that are explained only briefly here. For example, each user system112a-112ncould include a desktop personal computer, workstation, laptop, PDA, cell phone, or any wireless access protocol (WAP) enabled device or any other computing device capable of interfacing directly or indirectly to the Internet or other network connection. User system112a-112ntypically runs an HTTP client, e.g., a browsing program, such as Microsoft's Internet Explorer browser, Netscape's Navigator browser, Opera's browser, or a WAP-enabled browser in the case of a cell phone, PDA or other wireless device, or the like, allowing a user (e.g., subscriber of the multi-tenant database system) of user systems112a-112nto access, process and view information, pages and applications available to it from system116over network114. Each user system112a-112nalso typically includes one or more user interface devices, such as a keyboard, a mouse, trackball, touch pad, touch screen, pen or the like, for interacting with a graphical user interface (GUI) provided by the browser on a display (e.g., a monitor screen, LCD display, etc.) in conjunction with pages, forms, applications and other information provided by system116or other systems or servers. For example, the user interface device can be used to access data and applications hosted by system116, and to perform searches on stored data, and otherwise allow a user to interact with various GUI pages that may be presented to a user. As discussed above, embodiments are suitable for use with the Internet, which refers to a specific global internetwork of networks. However, it should be understood that other networks can be used instead of the Internet, such as an intranet, an extranet, a virtual private network (VPN), a non-TCP/IP based network, any LAN or WAN or the like.

FIG. 6also illustrates environment110. However, inFIG. 6elements of system116and various interconnections in an embodiment are further illustrated.FIG. 6shows that user system112amay include processor system112A, memory system112B, input system112C, and output system112D.FIG. 6shows network114and system116.FIG. 6also shows that system116may include tenant data storage122, tenant data123, system data storage124, system data125, User Interface (UI)230, Application Program Interface (API)232, PL/SOQL234, save routines236, application setup mechanism238, applications servers2001-200N, system process space202, tenant process spaces204, tenant management process space210, tenant storage area212, user storage214, and application metadata216. In other embodiments, environment110may not have the same elements as those listed above and/or may have other elements instead of, or in addition to, those listed above.

User systems112a-112n, network114, system116, tenant data storage122, and system data storage124were discussed above inFIG. 5. Regarding user system112a, processor system112A may be any combination of one or more processors. Memory system112B may be any combination of one or more memory devices, short term, and/or long term memory. Input system112C may be any combination of input devices, such as one or more keyboards, mice, trackballs, scanners, cameras, and/or interfaces to networks. Output system112D may be any combination of output devices, such as one or more monitors, printers, and/or interfaces to networks.

As shown byFIG. 6, system116may include a network interface115(ofFIG. 5) implemented as a set of HTTP application servers200, an application platform118, tenant data storage122, and system data storage124. Also shown is system process space202, including individual tenant process spaces204and a tenant management process space210. Each application server200may be configured to tenant data storage122and the tenant data123therein, and system data storage124and the system data125therein to serve requests of user systems112a-112n. The tenant data123might be divided into individual tenant storage areas212, which can be either a physical arrangement and/or a logical arrangement of data. Within each tenant storage area212, user storage214and application metadata216might be similarly allocated for each user. For example, a copy of a user's most recently used (MRU) items might be stored to user storage214. Similarly, a copy of MRU items for an entire organization that is a tenant might be stored to tenant storage area212. A UI230provides a user interface and an API232provides an application programmer interface to system116resident processes to users and/or developers at user systems112a-112n. The tenant data and the system data may be stored in various databases, such as one or more Oracle™ databases, or in distributed memory as described herein.

Application platform118includes an application setup mechanism238that supports application developers' creation and management of applications, which may be saved as metadata into tenant data storage122by save routines236for execution by subscribers as one or more tenant process spaces204managed by tenant management process210for example. Invocations to such applications may be coded using PL/SOQL234that provides a programming language style interface extension to API232. A detailed description of some PL/SOQL language embodiments is discussed in commonly owned, co-pending U.S. Provisional Patent App. No. 60/828,192, entitled Programming Language Method And System For Extending APIs To Execute In Conjunction With Database APIs, filed Oct. 4, 2006, which is incorporated in its entirety herein for all purposes. Invocations to applications may be detected by one or more system processes, which manages retrieving application metadata216for the subscriber making the invocation and executing the metadata as an application in a virtual machine.

Each application server200may be coupled for communications with database systems, e.g., having access to system data125and tenant data123, via a different network connection. For example, one application server2001might be coupled via the network114(e.g., the Internet), another application server200N−1might be coupled via a direct network link, and another application server200Nmight be coupled by yet a different network connection. Transfer Control Protocol and Internet Protocol (TCP/IP) are typical protocols for communicating between application servers200and the database system. However, it will be apparent to one skilled in the art that other transport protocols may be used to optimize the system depending on the network interconnect used.

In certain embodiments, each application server200is configured to handle requests for any user associated with any organization that is a tenant. Because it is desirable to be able to add and remove application servers from the server pool at any time for any reason, there is preferably no server affinity for a user and/or organization to a specific application server200. In one embodiment, an interface system implementing a load balancing function (e.g., an F5 Big-IP load balancer) is coupled for communication between the application servers200and the user systems112a-112nto distribute requests to the application servers200. In one embodiment, the load balancer uses a “least connections” algorithm to route user requests to the application servers200. Other examples of load balancing algorithms, such as round robin and observed response time, also can be used. For example, in certain embodiments, three consecutive requests from the same user could hit three different application servers200, and three requests from different users could hit the same application server200. In this manner, system116is multi-tenant and handles storage of, and access to, different objects, data and applications across disparate users and organizations.

In certain embodiments, user systems112a-112n(which may be client systems) communicate with application servers200to request and update system-level and tenant-level data from system116that may require sending one or more queries to tenant data storage122and/or system data storage124. System116(e.g., an application server200in system116) automatically generates one or more SQL statements (e.g., one or more SQL queries) that are designed to access the desired information. System data storage124may generate query plans to access the requested data from the database.