6. 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 first node representing the query prefix in a query graph, wherein: the query graph is a directed graph that comprises a plurality of nodes, each node representing a query, a query prefix, or both, wherein each node representing a query prefix has a directed edge that directs to one or more child nodes; and each node has one or more user category specific frequency measures, each user category specific frequency measure being based on a number of times that the query that is represented by the node was received from users that belong to the associated user category; locating descendant nodes of the first node, each descendent node being a node that represents a query; ranking the queries represented by the located nodes based on the user category specific frequency measure associated with the identified user category; and sending the ranked queries to the user device.
8. The method of claim 6 , further comprising only sending queries represented by located nodes that have an associated user category frequency measure greater than a threshold frequency.