1. A method implemented at least partially by a processor, the method comprising: constructing a bipartite graph by extracting queries from mobile search logs and identifying users that sent the queries, times at which the users sent the queries, and locations from which the users sent the queries; calculating a similarity between the users from the bipartite graph based at least in part on similarities between the queries, the times at which the users submitted the queries, and the locations from which the users submitted the queries; receiving, from a mobile computing device of a particular user, a query input associated with a current time and with a current location of the mobile computing device; and at least partly in response to the receiving of the query input: identifying, from the bipartite graph, one or more queries previously submitted by users that have previously submitted the query input, the one or more other queries comprising candidate queries; and computing a relatedness of each of the candidate queries to the received query input based at least in part on: (1) a calculated similarity between a respective user that submitted the candidate query and the particular user, (2) a difference between the current time associated with the received query input and a time when the candidate query was submitted, and (3) a distance between the current location associated with the received query input and a location where the candidate query was submitted.