A search engine tracks search queries from a user received at the search engine to generate a search query history. A prediction engine compares the search query history from the user with search query histories from other users on the search engine. A predicted search query for the user that the user is predicted to use to perform a next search in relation to other possible searches is generated in view of the comparison. Search query histories of the other users with greater similarities to the search query history of the user have a greater computation weight in generating the predicted search query than the search query histories of the other users with fewer similarities to the search query history of the user.