Top-k Frequent Items and Item Frequency Tracking over Sliding Windows of Any Sizes
Chunyao Song, Xuanming Liu, Tingjian Ge · 2017
Many big data applications today require querying highly dynamic and large-scale data streams for top-k frequent items in the most recent window of any specified size at any time. This is a challenging problem. We show that our novel solution is not only accurate, but it also one to two orders of magnitude faster than previous approaches. Moreover, its memory footprint grows only logarithmically with the window size, rather than linearly as in previous work. Our comprehensive experiments over real-world datasets show that our solution is very effective and scalable. In addition, we devise a concise and efficient solution to a related problem of tracking the frequency of selected items, improving upon previous work by twenty to thirty times in model conciseness while providing the same accuracy and efficiency.