Because of important applications such as denial-ofservice attack detection, finding frequent items in data streams under different models has been studied extensively. Finding frequent items in a turnstile data stream is the most challenging because both insertions and deletions of items are allowed in the stream. In this paper, we propose a deterministic algorithm that solves the problem. Furthermore, we propose a randomized algorithm for the problem. Empirical results show that our randomized algorithM provides better results than existing randomized algorithms for the problem and our algorithm uses much smaller space, and supports faster query time and similar update time.
展开▼
