[Haskell-cafe] Big Arrays

Hemanth Kapila saihemanth at gmail.com
Wed Oct 6 00:46:22 EDT 2010

Thanks Ketil.
On Wed, Oct 6, 2010 at 1:36 AM, Ketil Malde <ketil at malde.org> wrote:

> > Just out of curiosity, may I know a use case of such huge arrays?
> Bloom filters?
> Am probably dense - I still did not get an idea of where would one use such
a big array.

Let us say, we are using a bit-array of size 2^43 (that is, a byte array of
size 2^40) to store a bloom filter. And let us further assume that we are
interested in a false-positive probability of 0.01

That means, I will be able to use this array to represent  a set of
cardinality 9.18e11 ~ 10^12

I was curious to know what sort of programs would be dealing with sets of
10^12 elements.
Am mainly curious about how one would decide that bloom filters are the best
algorithm when dealing with this amount of data.What factors do we consider
when deciding the algorithm or the data structure?  The impact on GC would
be taken into account, for example (am guessing there would be at least one
copy from a younger generation to a permanent generation)?

/Hemanth K
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20101005/5d6fd8a8/attachment.html

More information about the Haskell-Cafe mailing list