Define new cluster centers with a different selection probability when handling the subgraph incident to high-degree vertices 
(these will exist alongside the clusters of the original algorithm). O(n^{3/4}) is the result of a particular tradeoff between the number of edges in the spanner
(i.e. number of new centers * number of redundant edges between a vertex and a new center's cluster) and the number of neighbors you're allowed to query.