| Autor: |
Guo-liang, Nie, Zheng-ding, Lu |
| Zdroj: |
Wuhan University Journal of Natural Sciences; Jan2006, Vol. 11 Issue 1, p283-288, 6p |
| Abstrakt: |
This paper presents two one-pass algorithms for dynamically computing frequency counts in sliding window over a data stream-computing frequency counts exceeding user-specified threshold ɛ. The first algorithm constructs sub-windows and deletes expired sub-windows periodically in sliding window, and each sub-window maintains a summary data structure. The first algorithm outputs at most 1/ɛ + 1 elements for frequency queries over the most recent N elements. The second algorithm adapts multiple levels method to deal with data stream. Once the sketch of the most recent N elements has been constructed, the second algorithm can provides the answers to the frequency queries over the most recent n(n≤N) elements. The second algorithm outputs at most 1/ɛ + 2 elements. The analytical and experimental results show that our algorithms are accurate and effective. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
Full text from SpringerLink