14. A machine-readable storage medium storing instructions which, when processed by one or more processors, causes the method of: receiving, from a client over a network a portion of a query, wherein the portion of the query is not formerly issued by the user that initiated the query; before any predicted queries are provided to the client and in response to receiving the portion of the query, determining, based on the portion of the query, a set of one or more predicted queries that correspond to the portion of the query; selecting, based upon selection criteria, a particular predicted query from the one or more predicted queries; processing the particular predicted query to obtain search results; and providing both the one or more predicted queries and the search results to the client over the network, wherein determining the set of one or more predicted Queries includes: determining a plurality of potential predicted queries; for each query of the plurality of potential predicted queries: search a first database to determine a first value that indicates how often said each query was issued during a first period of time; searching a second database to determine a second value that indicates how often said each query was issued during a second period of time that occurred temporally before or after the first period of time; scaling the first value by a scale factor to generate a scaled value; generating a resulting value based on the scaled value and the second value; and associating the resulting value with said each query; and using the resulting value of each query of the plurality of potential predicted queries to determine the set of one or more queries from the plurality of potential predicted queries.
14. A machine-readable storage medium storing instructions which, when processed by one or more processors, causes the method of: receiving, from a client over a network a portion of a query, wherein the portion of the query is not formerly issued by the user that initiated the query; before any predicted queries are provided to the client and in response to receiving the portion of the query, determining, based on the portion of the query, a set of one or more predicted queries that correspond to the portion of the query; selecting, based upon selection criteria, a particular predicted query from the one or more predicted queries; processing the particular predicted query to obtain search results; and providing both the one or more predicted queries and the search results to the client over the network, wherein determining the set of one or more predicted Queries includes: determining a plurality of potential predicted queries; for each query of the plurality of potential predicted queries: search a first database to determine a first value that indicates how often said each query was issued during a first period of time; searching a second database to determine a second value that indicates how often said each query was issued during a second period of time that occurred temporally before or after the first period of time; scaling the first value by a scale factor to generate a scaled value; generating a resulting value based on the scaled value and the second value; and associating the resulting value with said each query; and using the resulting value of each query of the plurality of potential predicted queries to determine the set of one or more queries from the plurality of potential predicted queries. 23. The machine-readable storage medium of claim 14 , wherein the instructions, when processed by the one or more processors, further cause the method of: receiving an indication of a selection of another predicted query in the set of one or more predicted queries; and providing new search results based on the selection of the selected predicted query.