{"action":"opened","issue":{"url":"https://api.github.com/repos/twitter/algebird/issues/404","labels_url":"https://api.github.com/repos/twitter/algebird/issues/404/labels{/name}","comments_url":"https://api.github.com/repos/twitter/algebird/issues/404/comments","events_url":"https://api.github.com/repos/twitter/algebird/issues/404/events","html_url":"https://github.com/twitter/algebird/issues/404","id":54948979,"number":404,"title":"Self Learning bitmap","user":{"login":"MansurAshraf","id":535144,"avatar_url":"https://avatars.githubusercontent.com/u/535144?v=3","gravatar_id":"","url":"https://api.github.com/users/MansurAshraf","html_url":"https://github.com/MansurAshraf","followers_url":"https://api.github.com/users/MansurAshraf/followers","following_url":"https://api.github.com/users/MansurAshraf/following{/other_user}","gists_url":"https://api.github.com/users/MansurAshraf/gists{/gist_id}","starred_url":"https://api.github.com/users/MansurAshraf/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MansurAshraf/subscriptions","organizations_url":"https://api.github.com/users/MansurAshraf/orgs","repos_url":"https://api.github.com/users/MansurAshraf/repos","events_url":"https://api.github.com/users/MansurAshraf/events{/privacy}","received_events_url":"https://api.github.com/users/MansurAshraf/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/twitter/algebird/labels/question","name":"question","color":"cc317c"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2015-01-20T22:21:33Z","updated_at":"2015-01-20T22:21:33Z","closed_at":null,"body":"I was wondering if someone has seen this paper from google. it is solving the same problem as HLL but is scale invariant and has better memory consumption. Below is the abstract.\r\n\r\nAbstract:\r\n*In this paper, we develop a novel approach, called self-learning bitmap (S-bitmap) that is scale-invariant for cardinalities in a specified range. S-bitmap uses a binary vector whose entries are updated from 0 to 1 by an adaptive sampling process for inferring the unknown cardinality, where the sampling rates are reduced sequentially as more and more entries change from 0 to 1. We prove rigorously that the S- bitmap estimate is not only unbiased but scale-invariant. We demonstrate that to achieve a small RRMSE value of ǫ or less, our approach requires significantly less memory and consumes similar or less operations than state-of-the- art methods for many common practice cardinality scales. Both simulation and experimental studies are reported.* \r\n\r\n![screen shot 2015-01-05 at 12 07 29 pm 1](https://cloud.githubusercontent.com/assets/535144/5827477/74bdeb1a-a0af-11e4-986a-058143de35e3.png)\r\n\r\nhttp://arxiv.org/pdf/1107.1697v1.pdf\r\n\r\nHere is an implementation in Java : https://github.com/travisbrady/self-learning-bitmap"}}