Type-ahead search optimization

• US 8,965,909 B2
• Filed: 12/24/2012
• Issued: 02/24/2015
• Est. Priority Date: 12/24/2012
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Herron, Jon
• Primary Examiner(s): LE, HUNG D
• Application Number:
  US13/726,449
• Publication Number:
  US 20140181084A1
• Time in Patent Office: 792 Days
• Field of Search: None
• US Class Current: 707/754
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/2455 Query execution

Abstract

Techniques are provided for efficiently performing a series of searches. After an initial set of search results is determined from a data set based on a search query, one or more additional characters are added to the search query. In response, another search is performed, using the updated search query, but the new search is limited to searching the initial set of search results. Thus, the original data set is not accessed or searched again. This is possible due to the nature of the data. Each subsequent search is based on one or more characters that were added to a previous search query. Thus, each subsequent search is constrained to the search results that were identified in a previous search.

Claims

1. A method comprising:

in response to receiving a first search query, determining search results from a data set, wherein the search results is a strict subset of the data set;

after determining the search results and in response to receiving a second search query that comprises the first search query and one or more additional characters, searching only the search results based on the second search query;

as a result of searching only the search results based on the second search query, identifying a first strict subset of the search results;

wherein each search result in the first strict subset satisfies the second search query;

in response to identifying the first strict subset, storing a first set of references, wherein each reference in the first set of references refers to a different search result in the first strict subset of the search results;

wherein the number of references in the first set of references is the same as the number of search results in the first strict subset;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, further comprising:

after storing the first set of references and in response to receiving a third search query, searching only the first strict subset based on the third search query;

wherein searching only the first strict subset comprises, for each reference in the first set of references;

using said each reference to identify a search result in the first strict subset,

determining whether the search result satisfies the third search query;

as a result of searching only the first strict subset, identifying a strict subset of the first strict subset;

in response to identifying the strict subset of the first strict subset, storing a second set of references, wherein each reference in the second set of references refers to a different search result in the first strict subset;

wherein the number of references in the second set of references is the same as the number of search results in the strict subset of the first strict subset.

3. The method of claim 1, further comprising:

in response to determining the search results, causing a least a portion of the search results to be displayed;

in response to identifying the first strict subset, causing a least a portion of the first strict subset of the search results to be displayed.

4. A method comprising:

in response to receiving a first search query, determining search results from a data set, wherein the search results is a strict subset of the data set;

in response to determining the search results, storing a first set of references, wherein each reference in the first set of references refers to a different search result in the search results;

wherein the number of references in the first set of references is the same as the number of the search results;

after determining the search results and in response to receiving a second search query that comprises the first search query and one or more additional characters, searching only the search results based on the second search query;

as a result of searching only the search results based on the second search query, identifying a first strict subset of the search results;

wherein each search result in the first strict subset satisfies the second search query;

wherein the method is performed by one or more computing devices.

5. The method of claim 4, further comprising, in response to receiving the second search query:

for each reference in the first set of references;

using said each reference to identify a search result in the search results, and

determining whether the search result satisfies the second search query.

6. A method comprising:

in response to receiving a first search query, determining search results from a data set, wherein the search results is a strict subset of the data set;

after determining the search results and in response to receiving a second search query that comprises the first search query and one or more additional characters, searching only the search results based on the second search query;

as a result of searching only the search results based on the second search query, identifying a first strict subset of the search results;

wherein each search result in the first strict subset satisfies the second search query;

response to identifying the first strict subset, creating and storing a copy of each search result in the first strict subset;

in response to receiving a third search query, searching only the copy of each search result in the first strict subset based on the third search query;

as a result of searching only of the first stridt subset basec of the third search query, identifying a strict subset of the first strict subset;

wherein each search result in the strict subset of the first strict subset satisfies the third search query;

wherein the method is performed by one or more computing device.

7. A method comprising:

in response to receiving a first search query, determining search results from a data set, wherein the search results is a strict subset of the data set;

after determining the search results and in response to receiving a second search query, searching only the search results based on the second search query;

as a result of searching only the search results based on the second search query, identifying a first strict subset of the search results;

wherein each search result in the first strict subset satisfies the second search query;

in response to identifying the first strict subset;

creating and storing first result data that identifies the first strict subset;

inserting the first result data onto a stack;

after identifying the first strict subset and in response to receiving a third search query, searching only the first strict subset based on the third search query;

as a result of searching only the first strict subset based on the third search query, identifying a strict subset of the first strict subset;

wherein each search result in the strict subset of the first strict subset satisfies the third search query;

in response to identifying the strict subset of the first strict subset;

creating and storing second result data that identifies the strict subset of the first strict subset;

inserting the second result data onto the stack;

after inserting the second result data onto the stack and in response to receiving a fourth search query;

removing the second result data from the stack;

identifying the first result data in the stack;

using the first result data to identify the first strict subset;

wherein the method is performed by one or more computing devices.

8. The method of claim 7, wherein the third search query is a subset of the fourth search query and is shorter than the fourth search query.

9. One or more non-transitory storage media carrying instructions which, when executed by one or more processors, cause:

in response to receiving a first search query, determining search results from a data set, wherein the search results is a strict subset of the data set;

after determining the search results and in response to receiving a second search query that comprises the first query and one or more additional characters, searching only the search results based on the second search query;

as a result of searching only the search results based on the second search query, identifying a first strict subset of the search results;

wherein each search result in the first strict subset satisfies the second search query;

in response to identifying the first strict subset, storing a first set of references, wherein each reference in the first set of references refers to a different search result in the first strict subset of the search results;

wherein the number of references in the first set of references is the same as the number of search results in the first strict subset.

10. The one or more storage media of claim 9, wherein the instructions, when executed by the one or more processors, further cause:

after storing the first set of references and in response to receiving a third search query, searching only the first strict subset based on the third search query;

wherein searching only the first strict subset comprises, for each reference in the first set of references;

using said each reference to identify a search result in the first strict subset,

determining whether the search result satisfies the third search query;

as a result of searching only the first strict subset, identifying a strict subset of the first strict subset;

in response to identifying the strict subset of the first strict subset, storing a second set of references, wherein each reference in the second set of references refers to a different search result in the first strict subset;

wherein the number of references in the second set of references is the same as the number of search results in the strict subset of the first strict subset.

11. The one or more storage media of claim 9, wherein the instructions, when executed by the one or more processors, further cause:

in response to determining the search results, causing a least a portion of the search results to be displayed;

in response to identifying the first strict subset, causing a least a portion of the first strict subset of the search results to be displayed.

12. One or more non-transitory storage media storing instructions which, when executed by one or more processors, cause:

in response to receiving a first search query, determining search results from a data set, wherein the search results is a strict subset of the data set;

in response to determining the search results, storing a first set of references, wherein each reference in the first set of references refers to a different search result in the search results;

wherein the number of references in the first set of references is the same as the number of the search results;

after determining the search results and in response to receiving a second search query that comprises the first search query and one or more additional characters, searching only the search results based on the second search query;

as a result of searching only the search results based on the second search query, identifying a first strict subset of the search results;

wherein each search result in the first strict subset satisfies the second search query.

13. The one or more storage media of claim 12, wherein the instructions, when executed by the one or more processors, further cause, in response to receiving the second search query:

for each reference in the first set of references;

using said each reference to identify a search result in the search results, and

determining whether the search result satisfies the second search query.

14. One or more non-transitory storage media storing instructions which, when executed by one or more processors, cause:

in response to receiving a first search query, determining search results from a data set, wherein the search results is a strict subset of the data set;

after determining the search results and in response to receiving a second search query that comprises the first query and one or more additional characters, searching only the search results based on the second search query;

as a result of searching only the search results based on the second search query, identifying a first strict subset of the search results;

in response to identifying the first strict subset, creating and storing a copy of each search result in the first strict subset;

in response to receiving a third search query, searching only the copy of each search result in the first strict subset based on the third search query;

as a result of searching only the first strict subset based on the third search query, identifying a strict subset of the first strict subset;

wherein each search result in the strict subset of the first strict subset satisfies the third search query.

15. One or more non-transitory storage media storing instructions which, when executed by one or more processors, cause:

in response to receiving a first search query, determining search results from a data set, wherein the search results is a strict subset of the data set;

after determining the search results and in response to receiving a second search query, searching only the search results based on the second search query;

as a result of searching only the search results based on the second search query, identifying a first strict subset of the search results;

wherein each search result in the first strict subset satisfies the second search query;

in response to identifying the first strict subset;

creating and storing first result data that identifies the first strict subset;

inserting the first result data onto a stack;

after identifying the first strict subset and in response to receiving a third search query, searching only the first strict subset based on the third search query;

as a result of searching only the first strict subset based on the third search query, identifying a strict subset of the first strict subset;

wherein each search result in the strict subset of the first strict subset satisfies the third search query;

in response to identifying the strict subset of the first strict subset;

creating and storing second result data that identifies the strict subset of the first strict subset;

inserting the second result data onto the stack;

after inserting the second result data onto the stack and in response to receiving a fourth search query;

removing the second result data from the stack;

identifying the first result data in the stack;

using the first result data to identify the first strict subset.

16. The one or more storage media of claim 15, wherein the third search query is a subset of the fourth search query and is shorter than the fourth search query.