{"action":"created","issue":{"url":"https://api.github.com/repos/twitter/algebird/issues/393","labels_url":"https://api.github.com/repos/twitter/algebird/issues/393/labels{/name}","comments_url":"https://api.github.com/repos/twitter/algebird/issues/393/comments","events_url":"https://api.github.com/repos/twitter/algebird/issues/393/events","html_url":"https://github.com/twitter/algebird/issues/393","id":53667214,"number":393,"title":"CMS: Do we support negative counts and/or is computing inner products broken?","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":"open","locked":false,"assignee":null,"milestone":null,"comments":5,"created_at":"2015-01-07T18:53:51Z","updated_at":"2015-01-07T22:52:46Z","closed_at":null,"body":"## Background\r\n\r\nI came across this question while debugging a failing test (computing the inner product) for CMS with the proposed new hashing code for `BigInt` discussed at #392.  The failing test in question is [\"estimate inner products\"](https://github.com/twitter/algebird/blob/develop/algebird-test/src/test/scala/com/twitter/algebird/CountMinSketchTest.scala#L198).\r\n\r\nI noticed that with the old/legacy CMS hashing for BigInt's -- and because they hash in the same way this means the issue I am talking about is also relevant for `CMS[Long]`, `CMS[Int]`, etc. -- that computing inner products (as part of the test above) returned `Approximate` instances with a negative minimum value:\r\n\r\n```scala\r\ncase class Approximate[N](min: N, estimate: N, max: N, probWithinBounds: Double)(implicit val numeric: Numeric[N]) { ...}\r\n```\r\n\r\nExample using current code and current BigInt hashing:\r\n\r\n```\r\nApproximate(-2544,24850,24850,0.9999999999)  // <<< note the negative minimum of `-2544`\r\n```\r\n\r\nThis also meant that the test ended up computing weird (?) error bounds because \"minus a negative value\" is effectively addition.  But the test passed, and has done so for I think many months.\r\n\r\n```\r\napproxA.min:  -2544\r\napprox:       24850  (approx = approxA.estimate)\r\nexact:         1192\r\nestimError:   23658  (estimationError = approx - exact)\r\nmaxError:     27394  (maxError = approx - approxA.min)  // <<< IMHO maxError should rather be smaller than approx, not larger!\r\n```\r\n\r\n> Btw, the same negative value for `Approximate.min` happens for `CMS[Long]`, for instance.\r\n\r\nWhen testing the proposed Murmur3-based hashing for `CMS[BigInt]`, the same tests fails, because here Approximate.min happened to be a positive value.\r\n\r\n> Note: I am not claiming (yet?) that the values are negative all the time etc. -- I can only confirm that they happened to be negative in my limited testing.  Same thing for the \"positive\" values for the minimums returned with the new hashing code.\r\n\r\n```\r\nApproximate(6270,33664,33664,0.9999999999) // <<< min is positive, `6270`\r\n\r\napproxA.min: 6270\r\napprox:       33664  (approxA.estimate)\r\nexact:         1305\r\nestimError:   32359  (approx - exact)\r\nmaxError:     27394  (approx - approxA.min) // <<< this makes more sense, but now the test fails!\r\n```\r\n\r\nAt this point I got confused.\r\n\r\nI checked the [inner product definition](https://github.com/twitter/algebird/blob/develop/algebird-core/src/main/scala/com/twitter/algebird/CountMinSketch.scala#L484) of CMSInstance[K]:\r\n\r\n```scala\r\n  def innerProduct(other: CMS[K]): Approximate[Long] = {\r\n    other match {\r\n      case other: CMSInstance[_] =>\r\n        require((other.depth, other.width) == (depth, width), \"Tables must have the same dimensions.\")\r\n\r\n        def innerProductAtDepth(d: Int) = (0 to (width - 1)).iterator.map { w =>\r\n          countsTable.getCount(d, w) * other.countsTable.getCount(d, w)\r\n        }.sum\r\n\r\n        val est = (0 to (depth - 1)).iterator.map { innerProductAtDepth }.min\r\n        Approximate(est - (eps * totalCount * other.totalCount).toLong, est, est, 1 - delta)\r\n      case _ => other.innerProduct(this)\r\n    }\r\n  }\r\n```\r\n\r\nThe relevant line is:\r\n\r\n```scala\r\n        Approximate(est - (eps * totalCount * other.totalCount).toLong, est, est, 1 - delta)\r\n```\r\n\r\nHere, `est - (eps * totalCount * other.totalCount).toLong` computes the minimum, and this computation can result in negative values.\r\n\r\n**Hence my question: Do we actually support negative values in CMS?**\r\n\r\nI don't think we do, even though the original CMS paper does allow for CMS that support positive counts only as well as CMS that support positive and negative counts.  (Off the hip one reason why I think we do not support negative counts is that this might break the algebraic properties we need for CMS in Algebird?) If we actually *do* support negative counts, then for instance @avibryant's proposed code in #390 needs further adjustment as his List-based optimization only supports adding items but not removing any, nor does it support negative counts in general.\r\n\r\n## A fix?\r\n\r\nAt this point I wondered whether my new hashing code (using Murmur3) is wrong, or whether we have a legitimate bug in the way we compute inner products in CMS, or even both issues together.\r\n\r\nOut of curiosity I went ahead and tested a modification of `innerProduct()` where I set the minimum value to 0 if the normal computation produces a negative value:\r\n\r\n```scala\r\n        val minimum = Math.min(est - (eps * totalCount * other.totalCount).toLong, 0)\r\n        Approximate(minimum, est, est, 1 - delta)\r\n```\r\n\r\nAnd surprise:  Now _all_ tests in Algebird passed again, and they have been passing consistently (I re-ran the full test suite a couple of times).  And when I say \"all\" tests passed then this included a) my proposed hashing changes for CMS[BigInt] in #392 -- where the failing test described above caused me to doubt my code changes -- as well as b) the fickle CMS params round-trip test that @johnynek flagged as buggy in #388.  Uh?\r\n\r\n## TL;DR\r\n\r\nI'd appreciate any feedback in this matter.  Are we supposed to support negative counts?  Is the current implementation of inner products correct or buggy?  And even though the next question is harder to answer at the moment: How could a change of the CMS hashing algo for `BigInt` trigger a bug in the inner product computation but only there, and not e.g. in \"normal\" frequency estimation aka point queries?\r\n\r\nAnother reason for me to ask this question is that @avibryant is apparently very much interested in leveraging and tuning the CMS code because he works on clustering based on inner products of CMS, so any bug we might have here should be ironed out.\r\n\r\nPS:  I also begin to get the feeling the CMS code needs more testing to ensure it works as expected, given the recent issues with it..."},"comment":{"url":"https://api.github.com/repos/twitter/algebird/issues/comments/69107391","html_url":"https://github.com/twitter/algebird/issues/393#issuecomment-69107391","issue_url":"https://api.github.com/repos/twitter/algebird/issues/393","id":69107391,"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},"created_at":"2015-01-07T22:52:46Z","updated_at":"2015-01-07T22:52:46Z","body":"And another surprise:  It looks as if the inner product test passes for the current CMS code only by sheer luck. :-)\r\n\r\nWhen I _lower_ the `totalCount` value to, say, `2000`, then the inner product test begins to fail indiscriminately for all CMS variants (i.e. Long, Int, Short, BigInt).\r\n\r\n```scala\r\n\"estimate inner products\" in {\r\n      val totalCount = 2000 // instead of currently: 5234\r\n```\r\n\r\nresults in (here: `CMS[Int]` test spec):\r\n\r\n```\r\n4767 was greater than or equal to 0, but 4767 was not less than or equal to 4000\r\n```\r\n\r\nWhen using `totalCount = 3190`, for example, the test may pass or may fail.  Yes, we do generate random input but nonetheless the mathematical properties of CMS should not be violated.\r\n\r\nSimilarly, if I _increase_ `totalCount` to, say, `>= 20,000` the test will also pass occasionally for the modified `CMS[BigInt]` code.\r\n\r\nIn other words: The likelihood of test success seems to increase and decrease with the size of `totalCount`."}}