Mailing-List: contact user-help@cassandra.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@cassandra.apache.org
Received-SPF: pass (nike.apache.org: domain of chris.burroughs@gmail.com
 designates 209.85.213.172 as permitted sender)
Message-ID: <4FEDAD4D.9070309@gmail.com>
Date: Fri, 29 Jun 2012 09:27:41 -0400
From: Chris Burroughs <chris.burroughs@gmail.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
 rv:12.0) Gecko/20120430 Thunderbird/12.0.1
MIME-Version: 1.0
To: user@cassandra.apache.org
CC: Yuki Morishita <mor.yuki@gmail.com>
Subject: Re: Distinct Counter Proposal for Cassandra
References: 
 <CAKsb8n4JDLHN_aKwAYxJPFbYRdkOREXuZTVD4w_pt9gj0Y3CTQ@mail.gmail.com>
 <62C288C441C240D9998F0F6066F9A487@gmail.com>
In-Reply-To: <62C288C441C240D9998F0F6066F9A487@gmail.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit

On 06/13/2012 01:00 PM, Yuki Morishita wrote:
> The above implementation and most of the other ones (including stream-lib) implement the optimized version of the algorithm which counts up to 10^9, so may need some work.
> 
> Other alternative is self-learning bitmap (http://ect.bell-labs.com/who/aychen/sbitmap4p.pdf) which, in my understanding, is more memory efficient when counting small values.

The closest we could get to a one-size fits all would probably be an
adaptive counting scheme that uses linear counting (or self-learning
bitmap, didn't know about that one!) for small expected cardinalities
and a LogLog variant for higher ones.  It's more choices to make, but
choosing between "not too big" and "really really big" doesn't seem like
an unreasonable burden to me.