Count-Min sketch with conservative update (CM-CU): The QUERY procedure for CM-CU (Cormode, 2009;Goyal and Daumé III, 2011a) is identical to Count-Min.
to UPDATE an item "x" with frequency c, we first compute the frequencyĉ(x) of this item from the existing data structure ( ) and the counts are updated according to: The intuition is that, since the point query returns the minimum of all the d values, we update a counter only if it is necessary as indicated by ( * ).