Efficient search query clustering using tripartite graphs may enable a search engine developer to model information needs of users while expending less computing resources. The efficient clustering of search queries may involve multiple computing devices receiving a subgraph of a multi-partite graph that encompasses search queries, as well as receiving a global center vector table that includes cluster center entries for query clusters. At each computing device, the received global center vector table may be filtered to eliminate one or more cluster center entries that are irrelevant to the search queries. Subsequently, the search queries may be clustered into the query clusters by at least using the filtered global center vector table at each of the computing devices. In some instances, one or more comparisons between search queries and the cluster center entries in the global center vector table during the clustering may be eliminated.