1. A computer-implemented method comprising: receiving query data that specify a query prefix and a user identifier for a user, the query prefix including one or more characters; determining, by one or more computers and based at least in part on the user identifier, a user category to which the user belongs; selecting, by one or more computers, one or more queries that each include the query prefix, wherein each of the one or more queries have a category-specific frequency measure indicative of a number of times that the query was received from users that belong to the user category; ranking, by one or more computers, the one or more queries based on the category-specific frequency measures for the one or more queries; and providing data that cause presentation of the one or more queries according to the ranking.