1. A computer-implemented method comprising: receiving a query prefix from a user device; determining a user identifier based on the user device; identifying an associated user category that is associated with the user identifier; locating a node representing the query prefix in a query graph; locating descendent nodes of the located node, the descendent nodes representing queries, wherein: each descendent node has one or more user category specific frequency measures; each user category specific frequency measure for each located descendent node is associated with a user category; and each user category specific frequency measure for each located descendent node is based on a number of times that the query that is represented by the descendent node was received from users that belong to the associated user category; ranking the queries represented by the located descendent nodes based on a user category specific frequency measure associated with the identified user category; and sending the ranked queries to the user device.