New estimation methods of Count-Min sketch Huanliang Sun and Houkuan Huang   View Paper (PDF)   Return to Practical Applications of Data Mining 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. ©2006 Association for Computing Machinery