Abstract: To mine XML stream in an online way,a data structure named exponential histogram of cluster feature for XML is proposed.The structure is based on the temporal cluster feature and can be maintained according to the exponential histogram rule.The experiment results for a real data set and a synthetic data set show that the structure is of higher quality than the method offline.