Composite term index for graph data

• US 9,576,060 B2
• Filed: 10/28/2015
• Issued: 02/21/2017
• Est. Priority Date: 12/30/2010
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Norris, James, Singh, Sanjeev, Taylor, Bret Steven, Buchheit, Paul, Bosman, Tudor, Darnell, Benjamin
• Primary Examiner(s): Le, Debbie
• Application Number:
  US14/925,803
• Publication Number:
  US 20160048600A1
• Time in Patent Office: 482 Days
• Field of Search: 707/722, 707/798, 707/769, 707/767, 707/741, 707/E17.014, 707/739
• US Class Current: 1/1
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

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.

Claims

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 first edge-type term and a first object identifier;

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;

one or more node objects; and

one or more edge objects;

identifying a first set of edge objects having an edge type specified by the first edge-type term and having a destination node corresponding to the first object identifier of the search query;

identifying a second set of node objects that are source nodes of the first set of edge objects; and

sending, to the client server, object identifiers of one or more node objects of the second set.

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

3. The method of claim 2, 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.

4. The method of claim 3, 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.

5. The method of claim 3, 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.

6. The method of claim 1, wherein the first edge-type term defines a type of association between a source node object and a destination node object of the one or more data objects.

7. The method of claim 6, 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.

8. The method of claim 1, wherein each node object has a node object identifier and a node object type.

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

10. The method of claim 9, wherein identifying the second set of node objects that are the source nodes of the first set of edge 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 set of edge objects.

11. The method of claim 1, wherein the search query comprises a first combination of the first edge-type term and the first object identifier in association with a second combination of a second edge-type term and a second object identifier.

12. The method of claim 11, further comprising:

identifying a third set of edge objects having an edge type specified by the second edge-type term and having a destination node corresponding to the second object identifier of the search query;

identifying a fourth set of node objects that are source nodes of the third set of edge objects;

identifying a fifth set of node objects that includes source nodes that are in both the second set of node objects and the fourth set of node objects; and

sending, to the client server, object identifiers of one or more node objects of the fifth set.

13. The method of claim 1, wherein the search query comprises a combination of the first edge-type term and the first object identifier as a function of a second edge-type term.

14. The method of claim 13, further comprising:

identifying a third set of edge objects having an edge type specified by the second edge-type term and having a destination node corresponding to one or more of the object identifiers of the node objects of the second set;

identifying a fourth set of node objects that are source nodes of the third set of edge objects; and

sending, to the client server, object identifiers of the one or more node objects of the fourth set.

15. 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.

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

17. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

receive, from a client server of an online social network, a search query comprising an edge-type term and an object identifier, and the online social network comprising one or more index servers;

access, 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;

one or more node objects; and

one or more edge objects;

identify a first set of edge objects having an edge type specified by the edge-type term and having a destination node corresponding to the object identifier of the search query;

identify a second set of node objects that are source nodes of the first set of edge objects; and

send, to the client server, object identifiers of one or more node objects of the second set.

18. 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 an online social network, a search query comprising an edge-type term and an object identifier, and the online social network comprising one or more index servers;

access, 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;

one or more node objects; and

one or more edge objects;

identify a first set of edge objects having an edge type specified by the edge-type term and having a destination node corresponding to the object identifier of the search query;

identify a second set of node objects that are source nodes of the first set of edge objects; and

send, to the client server, object identifiers of one or more node objects of the second set.