Jim Norris

"Given a (nondecreasing) monotone sequence x0, x1,… , xn − 1 of natural numbers smaller than u, the Elias–Fano representation makes it possible to store it using at most 2 + log(u/n) bits per element, which is very close to the information-theoretical lower bound ≈ log e + log(u/n). A typical example is a list of pointer into records of a large file: instead of using, for each pointer, a number of bit sufficient to express the length of the file, the Elias–Fano representation makes it possible to use, for each pointer, a number of bits roughly equal to the logarithm of the average length of a record." - Jim Norris via Bookmarklet

Perfect for a posting list? - ⓞnor

lolwut? - Tad - the Meme Maker

Seems like the only way to construct one, which presumably uses byte arrays underneath, is to pass it an iterator to copy the longs from. So you're using twice the space, at least for a while... - DeWitt Clinton

Ah, nevermind, you can add new values in incrementally. And it is serializable, so perhaps you'd persist and depersist it as well. - DeWitt Clinton

Here's the 1974 paper at ACM: http://portal.acm.org/citation... - DeWitt Clinton