Finding Frequent Items of Data Streams Based on Hierarchical Sketch

A new hierarchical sketch data structure was implemented,which summarized the hierarchical structure in stream data and the key component of which was a pairwise independent family of hash functions based on exclusive-or operator.Applying the hierarchical sketch,an algorithm that finds hierarchical frequent items over data streams dynamically and approximately was implemented.The algorithm has sub-linear time and space costs and its accuracy is almost perfect in statistical meaning.