<div dir="ltr">On Mon, Jul 8, 2013 at 7:11 PM, Alex Arnon <span dir="ltr"><<a href="mailto:alex.arnon@gmail.com" target="_blank">alex.arnon@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi All,<div><br></div><div>I need to implement a very large set of data, with the following requirements:</div>

<div>- It will be populated EXCLUSIVELY by 64-bit integers.</div><div>- The only operations will be: </div>
<div>  - add element,</div><div>  - get number of elements, and</div><div>  - fold/foreach over the SORTED dataset.</div><div><br></div></div></blockquote><div><br></div><div style>Unless I am totally wrong here about what you want to get, why don't you use a digital representation? A 64 bit integer is a stream of bits. You can then share the common parts of the bit pattern in a tree-like structure. This in turn means that compression is "automatic" since the common bit patterns acts like the compression pattern. Add something like "everything below this node is present" and you can compress common parts of the tree.</div>

<div style><br></div><div style>In general, the solution is RADIX-trees, or something along that pattern. They have, incidentally, also been used for quick Integer-key-based maps and so on.</div><div> </div></div></div></div>