QUERY PATTERN MATCHING

• US 20200133967A1
• Filed: 10/31/2018
• Published: 04/30/2020
• Est. Priority Date: 10/31/2018
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Laserlike, Inc. (Apple Inc.)
• Inventors: Shukla, Anand, Natchu, Vishnu Priya
• Granted Patent: US 11,023,506 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/374 Thesaurus
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

A set of documents associated with a query comprising one or more query terms is determined. A subset of the documents is sampled to identify a corresponding query constraint pattern associated with each document included in the subset of the documents. An entry of an inverted index is generated based on the corresponding query constraint pattern associated with each document included in the subset of document.

Claims

1. A system, comprising:

a processor configured to;

determine a set of documents associated with a query comprising one or more tokens;

sample a subset of the documents to identify a corresponding query constraint pattern associated with each document included in the subset of the documents;

generate an entry of an inverted index based on the corresponding query constraint pattern associated with each document included in the subset of document; and

a memory coupled to the processor and configured to provide the processor with instructions.

2. The system of claim 1, wherein each document included in the set of documents includes at least one of the one or more tokens.

3. The system of claim 1, wherein the processor is further configured to generate a query is tree comprising the one or more tokens.

4. The system of claim 3, wherein the query tree includes a corresponding branch for the one or more tokens.

5. The system of claim 4, wherein the corresponding branches are associated with one or more corresponding leaf nodes.

6. The system of claim 5, wherein a leaf node of the one or more corresponding leaf nodes corresponds to at least one of the one or more tokens, a singular version of one of the one or more tokens, a plural version of one of the one or more tokens, a synonym associated with one of the one or more tokens, a singular version of the synonym associated with one of the one or more tokens, a plural version of the synonym associated with the one or more tokens, an abbreviation of one of the one or more tokens, or a related token associated with one of the one or more tokens.

7. The system of claim 5, wherein the corresponding query constraint pattern is based on the one or more corresponding leaf nodes.

8. The system of claim 7, wherein the corresponding query constraint pattern indicates the document satisfies the query.

9. The system of claim 7, wherein the corresponding query constraint pattern indicates that the document fails to satisfy the query.

10. The system of claim 1, wherein the processor is further configured to:

receive a subsequent web document; and

determine a query constraint pattern associated with the subsequent web document.

11. The system of claim 10, wherein the processor is further configured to determine whether the query constraint pattern associated with the subsequent web document matches at least one of one or more query constraint patterns that fail to satisfy the query.

12. The system of claim 11, wherein the processor is further configured to update the inverted index in the event the query constraint pattern associated with the subsequent web document does not match the at least one of the one or more query constraint patterns that fail to satisfy the query.

13. The system of claim 10, wherein the processor is further configured to determine whether the query constraint pattern associated with the subsequent web document matches at least one of one or more query constraint patterns that satisfy the query.

15. The system of claim 1, wherein the inverted index is used to identify one or more documents matching the query.

14. The system of claim 14, wherein the processor is further configured to update the inverted index in the event the query constraint pattern associated with the subsequent web document matches at least one of the one or more query constraint patterns that satisfy the query.

16. The system of claim 16, wherein the one or more identified documents are provided to an orchestrator, wherein the orchestrator is configured to provide the one or more identified documents in a content feed based on a corresponding ranking associated with the one or more identified documents.

17. A method, comprising:

determining a set of documents associated with a query comprising one or more query terms;

sampling a subset of the documents to identify a corresponding query constraint pattern associated with each document included in the subset of the documents;

generating an entry of an inverted index based on the corresponding query constraint pattern associated with each document included in the subset of document.

18. The method of claim 17, using the inverted index to identify one or more documents matching the query.

19. The method of claim 18, providing the one or more identified documents to an orchestrator, wherein the orchestrator is configured to provide the one or more identified documents in a content feed based on a corresponding ranking associated with the one or more identified documents.

20. A computer program product, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

determining a set of documents associated with a query comprising one or more query terms;

sampling a subset of the documents to identify a corresponding query constraint pattern associated with each document included in the subset of the documents; and

generating an entry of an inverted index based on the corresponding query constraint pattern associated with each document included in the subset of document.