Extract operator

• US 8,935,271 B2
• Filed: 12/21/2012
• Issued: 01/13/2015
• Est. Priority Date: 12/21/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Lassen, Soren Bogh, Kunnatur, Sandhya, Curtiss, Michael
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US13/723,861
• Publication Number:
  US 20140181091A1
• Time in Patent Office: 753 Days
• Field of Search: 707/607, 707/706, 707/713, 707/758, 707/781, 707/742, 707/737, 707/767
• US Class Current: 707/758
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: H04L 67/306 User profiles

Abstract

In one embodiment, a method includes receiving a search query requesting first search results of a first object type. The search query includes an inner query requesting second search results of a second object type. The method includes accessing an inverted index of a data store corresponding to the second object type; retrieving the second search results requested by the inner query using the inverted index of the data store corresponding to the second object type; accessing a forward index of the data store corresponding to the second object type; retrieving the first search results requested by the search query using the second search results and the forward index of the data store corresponding to the second object type.

Claims

1. A method comprising:

by one or more computing devices, receiving a search query requesting one or more first search results of a first object type that corresponds to a user in a social-networking system, the search query comprising an inner query identifying a specified user and requesting one or more second search results of a second object type that corresponds to a concept in the social-networking system;

by one or more computing devices, accessing an inverted index of a data store corresponding to the second object type, wherein the inverted index maps a user node to one or more concept nodes in accordance with a second relationship;

by one or more computing devices, retrieving the one or more second search results requested by the inner query using the inverted index of the data store corresponding to the second object type, wherein the one or more second search results comprise one or more concept nodes of a social graph in the social-networking system, and the one or more concept nodes are related to the specified user by the second relationship;

by one or more computing devices, accessing a forward index of the data store corresponding to the second object type, wherein the forward index maps a concept node to one or more user nodes in accordance with a first relationship; and

by one or more computing devices, retrieving the one or more first search results requested by the search query using the second search results and the forward index of the data store corresponding to the second object type, wherein the one or more first search results comprise one or more user nodes of the social graph that are related to the one or more resulting concept nodes by the first relationship.

2. The method of claim 1, wherein the concept comprises a photo, post, web page, or application.

3. The method of claim 1, further comprising, by one or more computing devices, ranking the first search results by:

accessing a data store corresponding to the first object type;

determining respective relationships of the first search results to an element of the inner query using the data store corresponding to the first object type; and

ranking the first search results based on the respective relationships of the first search results to the element of the inner query.

4. The method of claim 1, wherein the inverted index maps a search term associated with the first object type to one or more search results of the second object type, and the search term identifies the first relationship.

5. The method of claim 1, wherein the forward index maps a search term associated with the second object type to one or more search results of the first object type, and the search term identifies the second relationship.

6. The method of claim 1, wherein the search query is directed to objects within a social network of the social-networking system.

7. The method of claim 1, wherein the social-networking system comprises the computing devices and the data store.

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

receive a search query requesting one or more first search results of a first object type that corresponds to a user in a social-networking system, the search query comprising an inner query identifying a specified user and requesting one or more second search results of a second object type that corresponds to a concept in the social-networking system;

access an inverted index of a data store corresponding to the second object type, wherein the inverted index maps a user node to one or more concept nodes in accordance with a second relationship;

retrieve the one or more second search results requested by the inner query using the inverted index of the data store corresponding to the second object type, wherein the one or more second search results comprise one or more concept nodes of a social graph in the social-networking system, and the one or more concept nodes are related to the specified user by the second relationship;

access a forward index of the data store corresponding to the second object type, wherein the forward index maps a concept node to one or more user nodes in accordance with a first relationship; and

retrieve the one or more first search results requested by the search query using the second search results and the forward index of the data store corresponding to the second object type, wherein the one or more first search results comprise one or more user nodes of the social graph that are related to the one or more resulting concept nodes by the first relationship.

9. The media of claim 8, wherein the concept comprises a photo, post, web page, or application.

10. The media of claim 8, wherein the software is further operable when executed to rank the first search results by:

accessing a data store corresponding to the first object type;

determining respective relationships of the first search results to an element of the inner query using the data store corresponding to the first object type; and

ranking the first search results based on the respective relationships of the first search results to the element of the inner query.

11. The media of claim 8, wherein the inverted index of the data store maps a search term associated with the first object type to one or more search results of the second object type, and the search term identifies the first relationship.

12. The media of claim 8, wherein the forward index maps a search term associated with the second object type to one or more search results of the first object type, and the search term identifies the second relationship.

13. The media of claim 8, wherein the search query is directed to objects within a social network of the social-networking system.

14. The media of claim 8, wherein the social-networking system comprises the computing devices and the data store.

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;

receive a search query requesting one or more first search results of a first object type that corresponds to a user in a social-networking system, the search query comprising an inner query identifying a specified user and requesting one or more second search results of a second object type that corresponds to a concept in the social-networking system;

access an inverted index of a data store corresponding to the second object type, wherein the inverted index maps a user node to one or more concept nodes in accordance with a second relationship;

retrieve the one or more second search results requested by the inner query using the inverted index of the data store corresponding to the second object type, wherein the one or more second search results comprise one or more concept nodes of a social graph in the social-networking system, and the one or more concept nodes are related to the specified user by the second relationship;

access a forward index of the data store corresponding to the second object type, wherein the forward index maps a concept node to one or more user nodes in accordance with a first relationship; and

retrieve the one or more first search results requested by the search query using the second search results and the forward index of the data store corresponding to the second object type, wherein the one or more first search results comprise one or more user nodes of the social graph that are related to the one or more resulting concept nodes by the first relationship.

16. The system of claim 15, wherein the concept comprises a photo, post, web page, or application.

17. The system of claim 15, wherein the processors are further operable when executing the instructions to rank the first search results by:

accessing a data store corresponding to the first object type;

determining respective relationships of the first search results to an element of the inner query using the data store corresponding to the first object type; and

ranking the first search results based on the respective relationships of the first search results to the element of the inner query.

18. The system of claim 15, wherein the inverted index of the data store maps a search term associated with the first object type to one or more search results of the second object type, and the search term identifies the first relationship.

19. The system of claim 15, wherein the forward index of the data store maps a search term associated with the second object type to one or more search results of the first object type, and the search term identifies the second relationship.

20. The system of claim 15, wherein the search query is directed to objects within a social network of the social-networking system.