Title :
New estimation methods of Count-Min sketch
Author :
Li, Hongsong ; Huang, Houkuan
Author_Institution :
Sch. of Comput. & Inf. Technol., Beijing Jiaotong Univ., China
Abstract :
Count-Min sketch is an efficient approximate query tool for data stream. In this paper we address how to further improve its point query performance. Firstly, we modify the estimation method under cash register model. Our method will relieve error propagation. Secondly, we find better method under turnstile model and prove that our method is more efficient than that Count-Min sketch. These conclusions are well supported by experimental results.
Keywords :
data structures; query processing; Count-Min sketch; approximate query tool; cash register model; data stream; error propagation; point query performance; turnstile model; Computer errors; Data engineering; Data processing; IP networks; Information analysis; Monitoring; Performance analysis; Registers; Stress; Telecommunication computing;
Conference_Titel :
Research Issues in Data Engineering: Stream Data Mining and Applications, 2005. RIDE-SDMA 2005. 15th International Workshop on
Print_ISBN :
0-7695-2390-0
DOI :
10.1109/RIDE.2005.12
