Composite term index for graph data

Patent metadata

Field	Value
Publication number	US-9934329-B2
Application number	US-201715429031-A
Country	US
Kind code	B2
Filing date	Feb 9, 2017
Priority date	Dec 30, 2010
Publication date	Apr 3, 2018
Grant date	Apr 3, 2018

Abstract

This application is directed to an indexing system for graph data. In particular implementations, the indexing system uses a database index infrastructure that provides for flexible search capability to data objects and associations between data objects. Particular embodiments relate to an indexing system for storing and serving information modeled as a graph that includes nodes and edges that define associations or relationships between nodes that the edges connect in the graph.

First claim

What is claimed is:

1. A method comprising, by one or more index servers of an online social network:
receiving, from a client server of the online social network, a search query comprising an inner query and an outer query, the inner query comprising a first edge-type term and a first object identifier, and the outer query comprising a second edge-type term and a second object identifier;
executing the inner query by identifying a first set of node objects, each node object in the first set being a source node of one or more first edge objects of an edge type specified by the first edge-type term, each of the one or more edge objects having a destination node corresponding to the first object identifier;
executing the outer query by identifying a second set of nodes objects, each node in the second set being a source node of one or more second edge objects of an edge type specified by the second edge-type term, each of the one or more edge object having a destination node corresponding to one of the node objects in the first set; and
sending, to the client server, second object identifiers of one or more node objects in the second set.

2. The method of claim 1 , wherein the executing of the inner query comprises:
identifying the one or more first edge objects associated with the inner query having the edge type specified by the first edge-type term and having the destination node corresponding to the first object identifier; and
identifying the first set of node objects that are the source nodes of the one or more first edge objects.

3. The method of claim 2 , wherein the executing of the outer query comprises:
identifying the one or more second edge objects associated with the outer query having the edge type specified by the second edge-type term and having the destination node corresponding to one of the node objects in the first set;
identifying the second set of node objects that are source nodes of the one or more second edge objects; and
identifying the second object identifiers of the one or more node objects in the second set.

4. The method of claim 1 , wherein the inner query further comprises a node attribute.

5. The method of claim 4 , wherein the executing of the inner query further comprises:
filtering the first set of node objects by the node attribute to identify a third set of node objects comprising one or more nodes associated with the node attribute.

6. The method of claim 5 , wherein the executing of the outer query further comprises:
identifying the second set of nodes objects in which each node in the second set is a source node of the one or more second edge objects of the edge type specified by the second edge-type term and each of the one or more edge object has a destination node corresponding to one of the node objects in the third set of node objects.

7. The method of claim 1 , further comprising, prior to executing the inner query:
accessing, at the one or more index servers, one or more indexes associated with the online social network, each index comprising one or more data objects, the data objects comprising the one or more node objects and the one or more edge objects.

8. The method of claim 7 , wherein the second object identifiers of the one or more node objects in the second set comprise a time stamp and a data object identifier associated with the one or more node objects.

9. The method of claim 8 , wherein the time stamp comprises to one or more of:
a time when the node object was first created; and
a time when the node object was last modified.

10. The method of claim 9 , wherein the one or more nodes objects of the second set are ordered by reverse chronological order based on the time when the node object was created.

11. The method of claim 9 , wherein the one or more nodes objects of the second set are ordered by reverse chronological order based on the time when the node object was last modified.

12. The method of claim 1 , wherein the first edge-type term and the second edge type term each defines a type of association between a source node object and a destination node object.

13. The method of claim 12 , wherein the type of association between the source node object and the destination node object is determined based on a social graph of the online social network, the social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the nodes comprising a plurality of user nodes and a plurality of concept nodes; and
wherein each of the plurality of nodes corresponds to one or more node objects, and each of the plurality of edges corresponds to one or more edge objects.

14. The method of claim 13 , wherein each node object has a node object identifier and a node object type.

15. The method of claim 14 , wherein each edge object has an edge-object identifier, an edge-object type, an edge-object source identifier, and an edge-object destination identifier.

16. The method of claim 15 , wherein identifying the second set of node objects comprises determining one or more node objects that each have a node-object identifier that matches an edge-object source identifier of an edge object of the first edge objects.

17. The method of claim 1 , wherein the client server uses the object identifiers of the node objects of the second set to access corresponding data objects stored in a data store of the online social network.

18. The method of claim 17 , wherein the corresponding data objects are inputted to a term producer module to generate one or more terms associated with the data object.

19. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:
receive, from a client server of the online social network, a search query comprising an inner query and an outer query, the inner query comprising a first edge-type term and a first object identifier, and the outer query comprising a second edge-type term and a second object identifier;
execute the inner query by identifying a first set of node objects, each node object in the first set being a source node of one or more edge objects of an edge type specified by the first edge-type term, each of the one or more edge objects having a destination node corresponding to the first object identifier;
execute the outer query by identifying a second set of nodes objects, each node in the second set being a source node of one or more edge objects of an edge type specified by the second edge-type term, each of the one or more edge object having a destination node corresponding to one of the node objects in the first set; and
send, to the client server, object identifiers of one or more node objects in the second set.

20. A system comprising: one or more processors; and a non-transitory memory coupled to the processors comprising instructions executable by the processors, the processors operable when executing the instructions to:
receive, from a client server of the online social network, a search query comprising an inner query and an outer query, the inner query comprising a first edge-type term and a first object identifier, and the outer query comprising a second edge-type term and a second object identifier;
execute the inner query by identifying a first set of node objects, each node object in the first set being a source node of one or more edge objects of an edge type specified by the first edge-type term, each of the one or more edge

Assignees

• Facebook Inc

Inventors

• Singh Sanjeev
• Taylor Bret Steven
• Buchheit Paul
• Norris James
• Bosman Tudor
• Darnell Benjamin

Classifications

• G06F17/30619

  Physics · mapped topic

• G06F17/30424

  Physics · mapped topic

• G06F17/30554

  Physics · mapped topic

• G06F17/30528

  Physics · mapped topic

• G06F17/30477

  Physics · mapped topic