Finding Hierarchical Frequent Items in Data Streams
Wenfeng Feng, Qiao Guo, Zhibin Zhang · 2006
A Hierarchical Sketch was implemented to summarize the hierarchical structure in stream data. The sketch used a XOR-based pair-wise independent family of hash functions on the hierarchical domain to map stream data items to a three dimensional array of counters of size L×D×W. Of the counter array, L was the layers in hierarchy, D was the number of uniformly and randomly chosen hash functions, and W was the range of hash functions. Based on the sketch, an algorithm that identified and evaluated the hierarchical frequent items over data streams approximately was implemented. This algorithm has sub-linear time and space costs and is almost exact in statistic meaning.