INTELLIGENT DATA CACHING FOR TYPEAHEAD SEARCH

• US 20140244619A1
• Filed: 02/26/2013
• Published: 08/28/2014
• Est. Priority Date: 02/26/2013
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Doroshenko, Sergii
• Granted Patent: US 10,169,356 B2
• Time in Patent Office: Days
• US Class Current: 707/722
• CPC Class Codes: G06F 16/168 Details of user interfaces specifically adapted to file systems, e.g. browsing and visualisation, 2d or 3d GUIs query results presentation G06F16/156
• CPC Class Codes: G06F 16/185 Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof details of archiving G06F16/11
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/3331 Query processing
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

Techniques for providing low latency incremental search results are disclosed herein. According to one embodiment, a method for incremental search includes receiving a first search query from a user, obtaining a plurality of first search results in response to the first search query from an index server, determining whether the plurality of first search results are a substantially exhausted list of results for the first search query, and caching the plurality of first search results in a cache storage if the plurality of first search results are the substantially exhausted list of results for the first search query.

Claims

1. A computer-implemented method comprising:

receiving a first search query from a user;

obtaining a plurality of first search results in response to the first search query from an index server;

determining whether the plurality of first search results are a substantially exhausted list of results for the first search query; and

caching the plurality of first search results in a cache storage if the plurality of first search results are the substantially exhausted list of results for the first search query.

2. The computer-implemented method of claim 1, further comprising:

receiving a second search query from the user;

determining whether the second search query is a refined query of the first search query; and

searching the first search results in response to the first search query cached in the cache storage for at least one second search result in response to the second search query.

3. The computer-implemented method of claim 1, further comprising:

presenting at least a portion of the first search results to an incremental search interface;

wherein the first search query is generated in real time when the user types one or more characters in the incremental search interface;

4. The computer-implemented method of claim 2, further comprising:

presenting the at least one second search result to an incremental search interface;

wherein the second search query is generated in real time when the user types one or more additional characters in the incremental search interface after the first search query being generated.

5. The computer-implemented method of claim 1, wherein the step of determining whether the plurality of first search results are a substantially exhausted list of results for the first search query further includes:

determining whether a number of the first search results is less than or equal to a predetermined proportion of a number of results requested from the index server.

6. The computer-implemented method of claim 2, wherein the step of determining whether the second search query is a refined query of the first search query further includes:

generating one or more prefix queries by trimming one or more characters from an end of the second search query;

calculating prefix hashes for the prefix queries; and

determining whether one of the prefix hashes matches a hash of the first search query store in the index server.

7. The computer-implemented method of claim 6, wherein the prefix hashes are calculated based on symbolic expressions for the prefix queries, and the hash of the first search query is calculated based on a symbolic expression for the first search query.

8. The computer-implemented method of claim 1, wherein the cache storage is in the index server, and the cache storage utilizes a cache storage policy of Belady'"'"'s algorithm, least recently used, most recently used, or random replacement.

9. The computer-implemented method of claim 1, wherein the cache storage purges the plurality of first search results after a predetermined time period.

10. The computer-implemented method of claim 1, wherein presenting search results in real time as continuously receiving input characters as contents of search queries from the user.

11. A method for incremental search comprising:

receiving a plurality of initial keystrokes from a user device;

obtaining, from an index server, a plurality of first search results based on a first search query including the initial keystrokes;

caching the plurality of first search results in a cache storage;

receiving one or more additional keystrokes from the user device;

generating one or more second search results by searching the first search results in the cache storage based on a second search query including the initial keystrokes and additional keystrokes; and

transmitting the second search results to the user device in real time.

12. The method of claim 11, further comprising:

transmitting the first search results to the user device in real time.

13. The method of claim 11, wherein the user device is configured to provide an incremental search interface for a user to input the initial and additional keystrokes, and for presenting the first and second search results in real time as the user inputting the initial and additional keystrokes.

14. The method of claim 11, further comprising:

determining whether the plurality of first search results are a substantially exhausted list of result for the first search query, wherein a number of the first search results is less than or equal to a predetermined proportion of a number of results requested from the index server.

15. The method of claim 14, further comprising:

determining whether to process the second search query by searching the first search results from the cache storage.

16. The method of claim 15, wherein the step of determining whether to process the second search query by searching the first search results from the cache storage further includes:

generating one or more prefix queries by trimming one or more characters from an end of the second search query;

calculating prefix hashes for the prefix queries; and

determining whether one of the prefix hashes matches a hash of the first search query store in the index server.

17. A computer server for incremental search comprising:

a networking component configured for receiving a plurality of initial keystrokes and later one or more additional keystrokes from a user device;

the networking component being further configured for obtaining from an index server a plurality of first search results based on a first search query including the initial keystrokes;

a cache storage configured for caching the plurality of first search results;

a processor; and

a memory storing instructions which, when executed by the processor, cause the computer server to perform a process including;

generating one or more second search results by searching the first search results in the cache storage based on a second search query including the initial keystrokes and additional keystrokes;

wherein the networking component is further configured for transmitting the second search results to the user device in real time.

18. The computer server of claim 17, wherein the process further includes;

determining processing the second search query by searching the first search results from the cache storage.

19. The computer server of claim 18, wherein the step of determining processing the second search query by searching the first search results from the cache storage further includes:

generating one or more prefix queries by trimming one or more characters from an end of the second search query;

calculating prefix hashes for the prefix queries; and

determining whether one of the prefix hashes matches a hash of the first search query store in the index server.

20. The computer server of claim 17, wherein the process further includes:

determining whether the plurality of first search results are a substantially exhausted list of result for the first search query, wherein a number of the first search results is less than or equal to a predetermined proportion of a number of results requested from the index server.

21. The computer server of claim 17, wherein the first search results includes social networking objects within a social network of a user.

22. The computer server of claim 17, wherein the initial keystrokes form at least a portion of an identity of a social networking object.