| Dynamically Computing Approximate Frequency Counts in Sliding Window over Data Stream |
| |
| 作者姓名： | NIE Guo-liang LU Zheng-ding |
| |
| 作者单位： | School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074,Hubei, China |
| |
| 基金项目： | Supported by the National Natural Science Foun dation of China （60403027） |
| |
| 摘 要： | 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 subwindows 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.
|
| 关 键 词： | 数据流 滑动时窗 近似算法 频数 |
| 文章编号： | 1007-1202（2006）01-0283-06 |
| 收稿时间： | 2005-04-20 |
Dynamically computing approximate frequency counts in sliding window over data stream |
| |
| NIE Guo-liang LU Zheng-ding.Dynamically Computing Approximate Frequency Counts in Sliding Window over Data Stream[J].Wuhan University Journal of Natural Sciences,2006,11(1):283-288. |
| |
| Authors: | Nie Guo-liang Lu Zheng-ding |
| |
| Institution: | (1) School of Computer Science and Technology, Huazhong University of Science and Technology, 430074 Wuhan Hubei, China |
| |
| Abstract: | 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 recentN elements. The second algorithm adapts multiple levels method to deal with data stream. Once the sketch of the most recentN elements has been constructed, the second algorithm can provides the answers to the frequency queries over the most recentn(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.
Foundation item: Supported by the National Natural Science Foundation of China (60403027)
Biography: NIE Guo-liang(1975-), male, Ph. D. candidate, research direction: distributed computing, the theory of data stream. |
| |
| Keywords: | data stream sliding window approximation algorithms frequency counts |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
