Finding frequent items in data streams using hierarchical information

Finding frequent items or top-k items in data streams is a basic mining task with a wide range of applications. There are lots of algorithms proposed to enhance the performance of these algorithms, whereas not much effort has been made to make use of hierarchical information held by items in data stream. In this paper, we try to improve the accuracy of finding frequent items using hierarchical information in taxonomy. To do that, we propose a method called Merge. According to the strategy, we design and implement an algorithm, named FISH_Merge. In order to evaluate the performance of the algorithm, we propose three new measures for testing, and develop a hierarchical stream data generator. After conducting a comprehensive experimental study, we conclude that accuracy of FISH_Merge is better than algorithms without using hierarchical information under same amount of memory. In the meantime, our algorithm can also provide some information of higher level items.