Web search results clustering are navigator for users to search results. Therefore the correct cluster label is important which has been index the set of web document. Suffix Tree Clustering (STC) is fast automatically clustering and labeling. However, STC is inadequate since they generate interrupted cluster label due to using n-gram technique. In this paper, we propose an approach for web search results clustering and labeling based on a new suffix tree data structure, a new base cluster combining algorithm with a new partial phase join operation. The algorithm for constructing the data structure is an incremental and a linear time algorithm. Thus, the proposed approach is suitable for on-the-fly the web search results clustering and labeling cluster. The proposed approach provides more readable and true common phrase of web document cluster than conventional web search result clustering. Experimental results also show that the proposed approach has better performance than that of conventional web search result clustering.