Composite term index for graph data

• US 9,223,899 B2
• Filed: 09/03/2013
• Issued: 12/29/2015
• 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: Singh, Sanjeev, Taylor, Bret Steven, Buchheit, Paul, Norris, James, Bosman, Tudor, Darnell, Benjamin
• Primary Examiner(s): LE, DEBBIE M
• Application Number:
  US14/017,153
• Publication Number:
  US 20140006412A1
• Time in Patent Office: 847 Days
• Field of Search: 707/711, 707/739, 707/741, 707/707, 707/802, 707/E17.083, 707/999.102
• 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

An indexing system for graph data. In particular implementations, the indexing system provides for denormalization and replica index functionality to improve query performance.

Claims

1. A method comprising:

by one or more computing systems, in response to a creation of an object, generating a document identifier comprising an object identifier component and a time stamp;

by the computing systems, selecting one or more term producer modules from a plurality of term producer modules, the selection based at least in part on a type of the respective object;

by one or more of the selected term producer modules, generating one or more terms associated with the data object, each term based at least in part on one or more attributes of the data object;

by the computing systems, outputting one or more pairs to one or more indexes, each of the pairs comprising one of the document identifiers and one of the terms; and

by the computing systems, storing the one or more indexes on one or more index servers.

2. The method of claim 1, wherein the type of the object comprises:

a node type;

or

an edge type, wherein the edge type comprises;

one or more of the generated terms is associated with a source object attribute; and

one or more of the generated terms is associated with a destination object attribute.

3. The method of claim 1, further comprising:

by the computing systems, receiving a search comprising an indication of one or more search data objects and one or more search attributes; and

by the computing systems, based on the search, retrieving the data object.

4. The method of claim 1, further comprising:

by the computing systems, updating one or more of the term producer modules.

5. The method of claim 4, wherein updating the term producer modules comprises one or more of:

adding one or more terms generated by the term producer module;

or

altering one or more terms generated by the term producer module.

6. The method of claim 4, wherein the term producer modules are updated before the creation of the object.

7. The method of claim 1, wherein outputting one or more pairs to one or more indexes comprises outputting one or more of the pairs to an existing index entry comprising the respective term.

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

in response to a creation of an object, generate a document identifier comprising an object identifier component and a time stamp;

select one or more term producer modules from a plurality of term producer modules, the selection based at least in part on a type of the respective object;

generate one or more terms associated with the data object, each term based at least in part on one or more attributes of the data object;

output one or more pairs to one or more indexes, each of the pairs comprising one of the document identifiers and one of the terms; and

store the one or more indexes on one or more index servers.

9. The media of claim 8, wherein the type of the object comprises:

a node type;

or

an edge type, wherein the edge type comprises;

one or more of the generated terms is associated with a source object attribute; and

one or more of the generated terms is associated with a destination object attribute.

10. The media of claim 8, wherein the software is further operable when executed to:

receive a search comprising an indication of one or more search data objects and one or more search attributes; and

based on the search, retrieve the data object.

11. The media of claim 8, wherein the software is further operable when executed to:

update one or more of the term producer modules.

12. The media of claim 11, wherein updating the term producer modules comprises one or more of:

adding one or more terms generated by the term producer module;

or

altering one or more terms generated by the term producer module.

13. The media of claim 11, wherein the term producer modules are updated before the creation of the object.

14. The media of claim 8, wherein outputting one or more pairs to one or more indexes comprises outputting one or more of the pairs to an existing index entry comprising the respective term.

15. A system comprising:

one or more processors; and

a memory coupled to the processors comprising instructions executable by the processors, the processors being operable when executing the instructions to;

in response to a creation of an object, generate a document identifier comprising an object identifier component and a time stamp;

select one or more term producer modules from a plurality of term producer modules, the selection based at least in part on a type of the respective object;

generate one or more terms associated with the data object, each term based at least in part on one or more attributes of the data object;

output one or more pairs to one or more indexes, each of the pairs comprising one of the document identifiers and one of the terms; and

store the one or more indexes in one or more index servers.

16. The system of claim 15, wherein the type of the object comprises:

a node type;

or

an edge type, wherein the edge type comprises;

one or more of the generated terms is associated with a source object attribute; and

one or more of the generated terms is associated with a destination object attribute.

17. The system of claim 15, wherein the software is further operable when executed to:

receive a search comprising an indication of one or more search data objects and one or more search attributes; and

based on the search, retrieve the data object.

18. The system of claim 15, wherein the software is further operable when executed to:

update one or more of the term producer modules.

19. The system of claim 18, wherein updating the term producer modules comprises one or more of:

adding one or more terms generated by the term producer module;

or

altering one or more terms generated by the term producer module.

20. The system of claim 18, wherein the term producer modules are updated before the creation of the object.