I read this article [1] and found an interesting algorithm Space Saving (SS) for finding Top-K and frequent items or heavy hitters. The authors described a data structure called Stream summary. The SS algorithm is very simple but the stream summary data structure is a little bit difficult to implement. I am wondering is it possible to design SS algorithm without stream summary data structure. Can some one guide me?
[1] Metwally, Ahmed, Divyakant Agrawal, and Amr El Abbadi. "Efficient computation of frequent and top-k elements in data streams." Database Theory-ICDT 2005. Springer Berlin Heidelberg, 2005. 398-412.
http://link.springer.com/chapter/10.1007/978-3-540-30570-5_27#page-1
.
the data structure proposed by the authors just improves the efficiency of the algorithm (constant time retrieval etc)
if you have no such high speed stream problems, you can just code the algorithm as described in Fig1 of your reference : you will see that a naive implementation will in some cases lead you to many sorting operations on the counters which could be avoided with a more sophisticated data structure
but once again, if your stream is not very fast (or if you do not care about a real application), a naive implementation is ok
.
.
by the way, the Stream Summary data structure is not so complicated ; in order to understand it, you just have to remember the following facts
therefore it makes sense
... which is the basic structure of the Stream Summary
.
Thanks for explanation of Stream Summary data structure. I understood it but the problem I want to solve, require technique which can handle deletion as well. For example, a stream with elements having negative and positive frequencies. So is it possible to handle such case using stream summary? will there be any problem in performance? Finally I am looking for similar counter based methods that can handle deletion.
- Badges
- Science topic
- Similar topics
- Computer Science
- Data Mining