A XOR-Based Hierarchical Sketch for Identifying and Estimating Hierarchical Frequent Items Online

Many sketch data structures have been implemented. But due to our knowledge, the current sketching approach to summarizing the hierarchical structure in data was oracles-based, which "stack" logn sketches. By designing and using a XOR-based pair-wise independent family of hash functions on the hierarchical domain U*, a hierarchical sketch data structure was implemented to summarize the hierarchical structure in data stream, which mapped the data stream items to a three dimensional counter array of size LtimesDtimesW, of which, L was the number of layers in the hierarchical domain, D was the number of the hash functions chosen uniformly at random, and W was the range of the hash functions. The sketch used the breadth-first search strategy to identify and estimate the hierarchical frequent items online with user-specified probability. The experiments demonstrate substantial improvement in the update time and evaluating accuracy over the straightforward oracles-based sketch approach.