Intelligent data caching for typeahead search

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;

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;

receiving a second search query from the user;

determining whether the second search query is a refined query of the first search query, wherein the determining comprises:

generating one or more prefix queries based on the second search query;

calculating prefix hashes for the prefix queries based on symbolic expressions for the prefix queries and a hash of the first search query based on a symbolic expression for the first search query; and

determining whether one of the prefix hashes matches the hash of the first search query; and

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

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

3. The computer-implemented method of claim 1 , 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.

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

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

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

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

8. 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;

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;

determining whether to process the second search query by searching the first search results from the cache storage, wherein the determining comprises:

generating one or more prefix queries based on the second search query;

calculating prefix hashes for the prefix queries based on symbolic expressions for the prefix queries and a hash of the first search query based on a symbolic expression for the first search query; and

determining whether one of the prefix hashes matches the hash of the first search query; and

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

9. The method of claim 8 , further comprising:

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

10. The method of claim 8 , 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.

11. 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;

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;

determining processing the second search query by searching the first search results from the cache storage, wherein the determining comprise:

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 based on symbolic expressions for the prefix queries and a hash of the first search query based on a symbolic expression for the first search query; and

determining whether one of the prefix hashes matches a hash of the first search query stored in the index server; and

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

12. The computer server of claim 11 , wherein the first search results include social networking objects within a social network of a user.

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