Abstract: Data mining based on data stream has become a very hot research field in recent years. In this paper a novel discovering and maintenance algorithm of subspace clustering over high dimensional data streams is presented, which is based on Hoeffding bound and named SHStream. SHStream partitions data streams (the length of each segment is computed by Hoeffding bound), makes subspace clusters on the segments and discovers clusters step-by-step. Meanwhile, focusing on dynamic of data stream, SHStream adjusts and maintains the cluster results. SHStream can deal with high dimensional clustering problem effectively and discover clusters with arbitrary shape through the technology based on grids and density. The experimental results on real datasets and synthetic datasets demonstrate promising availabilities of the approach.