Extract Operator

• US 20140181091A1
• Filed: 12/21/2012
• Published: 06/26/2014
• Est. Priority Date: 12/21/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Sandhya Kunnatur
• Inventors: Lassen, Soren Bogh, Curtiss, Michael, Kunnatur, Sandhya
• Granted Patent: US 8,935,271 B2
• Time in Patent Office: Days
• US Class Current: 707/723
• 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, the search query comprising an inner query requesting one or more second search results of a second object type;

by one or more computing devices, accessing an inverted index of a data store corresponding to the second object type;

by one or more computing devices, retrieving the second search results requested by the inner query using the inverted index of the data store corresponding to the second object type;

by one or more computing devices, accessing a forward index of the data store corresponding to the second object type; and

by one or more computing devices, 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.

2. The method of claim 1, wherein an object type is user, 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.

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.

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

7. The method of claim 1, wherein a 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, the search query comprising an inner query requesting one or more second search results of a second object type;

access an inverted index of a data store corresponding to the second object type;

retrieve the second search results requested by the inner query using the inverted index of the data store corresponding to the second object type;

access a forward index of the data store corresponding to the second object type; and

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

9. The media of claim 8, wherein an object type is user, 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.

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.

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

14. The media of claim 8, wherein a 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, the search query comprising an inner query requesting one or more second search results of a second object type;

access an inverted index of a data store corresponding to the second object type;

retrieve the second search results requested by the inner query using the inverted index of the data store corresponding to the second object type;

access a forward index of the data store corresponding to the second object type; and

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

16. The system of claim 15, wherein an object type is user, 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.

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.

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