{"action":"closed","issue":{"url":"https://api.github.com/repos/twitter/algebird/issues/353","labels_url":"https://api.github.com/repos/twitter/algebird/issues/353/labels{/name}","comments_url":"https://api.github.com/repos/twitter/algebird/issues/353/comments","events_url":"https://api.github.com/repos/twitter/algebird/issues/353/events","html_url":"https://github.com/twitter/algebird/issues/353","id":45847909,"number":353,"title":"CMS computes heavy hitters incorrectly when combining CMS instances with ++","user":{"login":"miguno","id":294849,"avatar_url":"https://avatars.githubusercontent.com/u/294849?v=3","gravatar_id":"","url":"https://api.github.com/users/miguno","html_url":"https://github.com/miguno","followers_url":"https://api.github.com/users/miguno/followers","following_url":"https://api.github.com/users/miguno/following{/other_user}","gists_url":"https://api.github.com/users/miguno/gists{/gist_id}","starred_url":"https://api.github.com/users/miguno/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/miguno/subscriptions","organizations_url":"https://api.github.com/users/miguno/orgs","repos_url":"https://api.github.com/users/miguno/repos","events_url":"https://api.github.com/users/miguno/events{/privacy}","received_events_url":"https://api.github.com/users/miguno/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":7,"created_at":"2014-10-15T09:46:56Z","updated_at":"2015-01-14T08:21:58Z","closed_at":"2015-01-14T08:21:58Z","body":"_This is a follow-up on a conversation I had with @johnynek and @avibryant on Twitter.  Many thanks to both of you for your help on narrowing this down.  And please do let me know if I'm mistaken with what I'm writing here._\r\n\r\nFrom what I understand today, I think I was partly right and partly wrong in my Twitter comments from yesterday:\r\n\r\n* I was right right in the sense there currently _is_ a bug in the Algebird's CMS that miscomputes heavy hitters under certain (data) conditions.  I describe these conditions in detail below and also propose a fix, and this fix is exactly what @avibryant and I briefly talked about on Twitter.\r\n* I was (partly) wrong though when I said this is related to the merging of heavy hitters not being associative -- here I over-generalized.  In fact, the merging of heavy hitters (once fixed) _is_ associative for top-% CMS variants (the current, pre GH-345 implementation of CMS is such a variant) but it is not associative for top-N CMS variants.  On the positive side, this means once this fix is included, the current CMS variant works correctly.  On the negative side, it means that a top-N CMS variant may still (and always?) have a problem when merging heavy hitters, and SketchMap might be similarly affected (and if SketchMap is not, which would be great, then we may have just learned we can't simply replace SketchMap with a top-N CMS variant).\r\n\r\nIn summary:\r\n\r\n* We seem to have a legitimate bug in the current (top-% based) CMS implementation that miscomputes heavy hitters under certain conditions.  There's a fix for that, see below.\r\n* We seem to have a general limitation to correctly compute heavy hitters for any top-N based CMS.\r\n\r\n## Background\r\n\r\nAs part of my refactoring work in GH-345 I decoupled the counting/querying functionality of CMS from the heavy hitters functionality (as per @jnievelt's suggestion), and once I reached that point I could easily provide both top-% and top-N CMS variants (here, having a top-N CMS variant brings us one step closer to eventually retire SketchMap).  And while testing the top-N variant I first discovered the heavy hitters issue I describe here.\r\n\r\n\r\n## Problem statement\r\n\r\n_In the discussion below I assume the two CMS instances we want to merge are called `left` and `right`, respectively._\r\n\r\nThe computation to combine two sets of heavy hitters is not correct right now when you use `CMSInstance#++(other: CMS): CMS` for combing two CMS instances.  The problem itself is two-fold, though both aspects are related and can be fixed in one swing.\r\n\r\nFirst, currently the way to combine the \"left\" and \"right\" heavy hitters is a simple call to `++` of the `HeavyHitters` case class (same `++` name, but different class; [see code](https://github.com/twitter/algebird/blob/develop/algebird-core/src/main/scala/com/twitter/algebird/CountMinSketch.scala#L454)) -- or, alternatively speaking, that we don't post-process the combined heavy hitters to merge entries for the same item.\r\n\r\nHere, heavy hitters elements for the same item are not summed/merged.  The effect is that items that are elements of the _intersection_ of left's and right's heavy hitters are not represented correctly.\r\n\r\nExample REPL output:\r\n\r\n```scala\r\n    scala> import com.twitter.algebird._\r\n    scala> import scala.collection.SortedSet\r\n    scala> val s1 = SortedSet[HeavyHitter]()(HeavyHitter.ordering) + HeavyHitter(10L, 1) + HeavyHitter(20L, 2)\r\n    s1: scala.collection.immutable.SortedSet[com.twitter.algebird.HeavyHitter] = TreeSet(HeavyHitter(10,1), HeavyHitter(20,2))\r\n\r\n    scala> val s2 = SortedSet[HeavyHitter]()(HeavyHitter.ordering) + HeavyHitter(20L, 1)\r\n    s2: scala.collection.immutable.SortedSet[com.twitter.algebird.HeavyHitter] = TreeSet(HeavyHitter(20,1))\r\n\r\n    scala> val combinedHhs = s1 ++ s2\r\n    combinedHhs: scala.collection.immutable.SortedSet[com.twitter.algebird.HeavyHitter] = TreeSet(HeavyHitter(10,1), HeavyHitter(20,1), HeavyHitter(20,2))\r\n```\r\n\r\nAs you can see in this example the item `20L` is actually represented twice in the combined heavy hitters `combinedHhs` -- `HeavyHitter(20L, 1)` and `HeavyHitter(20L, 2)` -- though it should be represented only once as a single `HeavyHitter(20L, 3)`.\r\n\r\nI think in summary the first problem means a) items that are in the left+right HH intersection will have lower effective counts than they should (`max(individual counts)` instead of `sum(individual counts)`), which means they are less likely to stay in the post-merge set of heavy hitters -- which is the opposite behavior of what one would intuitively expect for such intersection items -- and b) the cardinality of heavy hitters is `>=` the cardinality of the items in the heavy hitters -- because we have duplicate HH entries for some items -- which means the memory footprint is larger than it needs to be (at least until one or more subsequent \"purging/dropping\" operations are run on the heavy hitters), though this additional memory footprint may be of little concern in practice at the moment.  In case we would have a truly parameterized `CMS[K, V]` at some point in the future, e.g. with `V=HyperLogLog` [like Avi suggested](https://github.com/twitter/algebird/issues/345#issuecomment-58373165), the additional memory footprint might become an issue.\r\n\r\nThis first problem could be fixed by properly merging the left and right sets (think: `groupBy(._item)`).  But fixing only this two-set-merge is not sufficient, because there's a second issue:\r\n\r\nSecond, items that are elements of heavy hitters of _either_ left _or_ right (\"left.heavyHitters and not right.heavyHitters\", \"right.heavyHitters and not left.heavyHitters\") may not be represented correctly.  For example, it may happen that item `A` is in left's heavy hitters and not in right's BUT it was seen by right and thus counted (`A` simply didn't make it into the heavy hitters).  Here, in order to represent `A` correctly when combining left and right, we do not want to forget right's count of `A` when doing the merge.\r\n\r\n## Unit test that demonstrates the problem\r\n\r\nYou can see that problem by adding the following unit test to [CountMinSketchTest.scala](https://github.com/twitter/algebird/blob/develop/algebird-test/src/test/scala/com/twitter/algebird/CountMinSketchTest.scala):\r\n\r\n```scala\r\n\"should compute heavy hitters correctly (regression test of GH-353)\" in {\r\n      val monoid = new CountMinSketchMonoid(EPS, DELTA, SEED, 0.1)\r\n\r\n      val data1 = Seq(1L, 1L, 1L, 2L, 2L, 3L)\r\n      val data2 = Seq(3L, 4L, 4L, 4L, 5L, 5L)\r\n      val data3 = Seq(3L, 6L, 6L, 6L, 7L, 7L)\r\n      val data4 = Seq(3L, 8L, 8L, 8L, 9L, 9L)\r\n      val singleData = data1 ++ data2 ++ data3 ++ data4\r\n\r\n      /*\r\n        Data sets from above shown in tabular view\r\n\r\n        Item     1   2   3   4   total (= singleData)\r\n        ----------------------------------------\r\n        A (1L)   3   -   -   -   3\r\n        B (2L)   2   -   -   -   2\r\n        C (3L)   1   1   1   1   4  <<< C, with count 4, is the global top 1 heavy hitter\r\n        D (4L)   -   3   -   -   3\r\n        E (5L)   -   2   -   -   2\r\n        F (6L)   -   -   3   -   3\r\n        G (7L)   -   -   2   -   2\r\n        H (8L)   -   -   -   3   3\r\n        I (9L)   -   -   -   2   2\r\n\r\n       */\r\n\r\n      val cms1 = monoid.create(data1)\r\n      val cms2 = monoid.create(data2)\r\n      val cms3 = monoid.create(data3)\r\n      val cms4 = monoid.create(data4)\r\n      val aggregated = cms1 ++ cms2 ++ cms3 ++ cms4\r\n\r\n      val single = monoid.create(singleData)\r\n      aggregated.heavyHitters should be(single.heavyHitters)\r\n      aggregated.heavyHitters contains(3L) // C=3L is global top 1 heavy hitter\r\n    }\r\n```\r\n\r\nHere, we would expect that the final heavy hitters in the \"merged\" `aggregated` CMS are identical to the heavy hitters in the `single` CMS.  However, in the current CMS implementation they are not.\r\n\r\n## How to fix\r\n\r\nThe basic algorithm to correctly combine two sets of heavy hitters is as follows.  We assume the two corresponding CMSs are called `left` and `right`, respectively.\r\n\r\n1. Create the union of the items in left's heavy hitters and right's heavy hitters.  This union is the set of candidates that may become the final, combined heavy hitters.\r\n2. Combine the counting tables of left and right.\r\n    * In the GH-345 code, you can conveniently do this via `left.cms ++ right.cms`, where the `cms` field is a CMS that can only count and query.\r\n3. For each item in the union from step 1, estimate the \"combined\" frequency from\r\n   the combined counting table from step 2.\r\n4. Drop all items whose count is below the minimum threshold.  The remaining items are the correct heavy hitters.\r\n\r\nProof of concept fix for the current CMS implementation:\r\n\r\n```diff\r\ndiff --git a/algebird-core/src/main/scala/com/twitter/algebird/CountMinSketch.scala b/algebird-core/src/main/scala/com/twitter/algebird/CountMinSketch.scala\r\nindex b87058e..c11560c 100644\r\n--- a/algebird-core/src/main/scala/com/twitter/algebird/CountMinSketch.scala\r\n+++ b/algebird-core/src/main/scala/com/twitter/algebird/CountMinSketch.scala\r\n@@ -258,9 +258,98 @@ case class CMSInstance(countsTable: CMSCountsTable, totalCount: Long,\r\n       case other: CMSZero => this\r\n       case other: CMSItem => this + other.item\r\n       case other: CMSInstance => {\r\n         val newTotalCount = totalCount + other.totalCount\r\n-        val newHhs = (hhs ++ other.hhs).dropCountsBelow(params.heavyHittersPct * newTotalCount)\r\n-        CMSInstance(countsTable ++ other.countsTable, newTotalCount, newHhs, params)\r\n+        val allItems = hhs.items ++ other.hhs.items\r\n+        val combinedCounts = countsTable ++ other.countsTable\r\n+        val newHhs = {\r\n+          def freq(table: CMSCountsTable, x: Long): Approximate[Long] = {\r\n+            val estimates = table.counts.zipWithIndex.map {\r\n+              case (row, i) =>\r\n+                row(params.hashes(i)(x))\r\n+            }\r\n+            makeApprox(estimates.min)\r\n+          }\r\n+          val hitters: Set[HeavyHitter] = allItems.map { case i => HeavyHitter(i, freq(combinedCounts, i).estimate) }\r\n+          val hhs = HeavyHitters(hitters.foldLeft(SortedSet[HeavyHitter]()(HeavyHitter.ordering))(_ + _))\r\n+          hhs.dropCountsBelow(params.heavyHittersPct * newTotalCount)\r\n+        }\r\n+        CMSInstance(combinedCounts, newTotalCount, newHhs, params)\r\n       }\r\n     }\r\n   }\r\n```\r\n\r\nPlease note that the purpose of the patch above is to let me demonstrate the idea of the fix in a simple, short diff.  A proper, cleaner variant of the fix would touch multiple places in the CMS code.  (For instance, such a clean fix is already part of the GH-345 code.)\r\n\r\n\r\n## Limitation of this fix\r\n\r\nThe fix approach above does address the heavy hitters problem for **top-% CMS variants**, i.e. a CMS that computes heavy hitters based on the rule `count >= heavyHittersPct * totalCount`.  The current (pre GH-345) CMS code in Algebird is such a top-% CMS variant, and can thus be fixed with the approach above.\r\n\r\nHowever, the fix does not address the heavy hitters problem for **top-N CMS variants**, i.e. a CMS that computes heavy hitters by sorting items by count, and keeping only the top N items.  In a nutshell, the reason is that there may be items that should be promoted to the \"global\" heavy hitters list (aka post-merge) but which will not.  What are the characteristics of these items?  They happen to never make it into the heavy hitters of _any_ of the CMS instances being merged (think: `cms1 ++ cms2 ++ ...`), and thus never make it into the union-based set of HH candidates (cf. step 1 in the \"How to fix\" section above).  Alternatively speaking this limitation is caused by the operation of merging \"top-N\" sets not being associative.  (The latter may or may not be what @johnynek was eluding to [in his Twitter comment](https://twitter.com/posco/status/522076690671869952) that \"SketchMap's approach is not strictly associative [...]\".)\r\n\r\nFor the current top-% CMS implementation in comparison, every item that should make it into the global, post-merge set of heavy hitters _will_ at some point become an element of the left+right heavy hitter union set aka the list of HH candidates, thanks to the `count >= heavyHittersPct * totalCount` rule.\r\n\r\n## Next steps?\r\n\r\n_What I say below assume you agree there actually is an issue with the current CMS code.  Please let me know if I'm mistaken, which may well be. :-)_\r\n\r\nMy work in GH-345 already includes this fix in a \"clean\" way, and I should get open source approval by the end of this week.  So depending on how pressing / important this issue is for you, we could opt to just wait until GH-345 is in.\r\n\r\nAlternatively, we could patch the current CMS implementation -- either with the PoC fix in this issue, or with a cleaner variant (the PoC fix is intentionally not clean to better demonstrate the fix approach)."}}