Building data structures that are smaller than an array and faster (in C)

I use wavelet tree heavily in my job. They are very useful for compact representations of order preserving collections of strings which supports fast lookups.

Update: Sux4j has some interesting implementations of fast select/rank:

http://sux.dsi.unimi.it/

http://sux4j.dsi.unimi.it/docs/it/unimi/dsi/sux4j/bits/Selec...

For example this: "Use less memory than an array in all circumstances" is just plain impossible if your data distribution is uniform. You just cannot store 1000 32 bit random intergers (preserving their order) in a smaller place than 1000*32 bits; (it comes from from simple combinatorics considerations.)

    int32_t big_array[2^32] = {0};
    
    /* returns the key */
    int64_t write(int_32 value)
    {
        big_array[value]++;
        return big_array[value] << 32 & value;
    }
    
    /* returns the value */
    int32_t read(int64_t key)
    {
        return (int32_t) key;
    }

    /* all indexes between 1 and the return value are valid higher half values 
    for the key. The lower half is the value itself. */
    int32_t seek(int32_t value)
    {
        return big_array[value];
    }

access: O(1)

seek: O(1)

Problem solved!

:)

edit: I'm missing the "Use less memory than an array in all circumstances" requirement, but hey, you talk about "billion of records" in your post.

The author rewrites the initial values as:

1 0 2 0 2 3

He defines the keys array as:

2 3 4 6

Using the method defined in the article to find the values of each of the elements of the rewritten array, wouldn't the values be:

3 2 4 2 4 6

which does not equal the original values of:

3 2 4 6 2 6

General intro: http://crd-legacy.lbl.gov/~kewu/ps/LBNL-2164E.pdf

"Word Aligned Hybrid" compression: http://crd-legacy.lbl.gov/~kewu/ps/LBNL-49627.pdf

Bit maps as alternative to inverted index: http://crd-legacy.lbl.gov/~kewu/ps/LBNL-61768.pdf

Bit maps for range queries: http://crd-legacy.lbl.gov/~kewu/ps/LBNL-60891.pdf

The intuition is that you don't need granular memory addressing for storing large chunks. You only need to have addressability at the min(sizeof(doc)) level. So you can usually store the key in a 32bit int or less.

More detail can be found here: https://gist.github.com/1947190

https://gist.github.com/1947371

How often are you updating? What is reading from this data structure? What's the query structure?

If you're adding lots of records often, I'd go for a B+tree. There's also a trie (and a B-trie), if your keys share lots of common prefixes.

If you are making consecutive queries, then you'd do well to take advantage of what pages are in L1 and L2 cache, but if you're randomly picking things, that's less important.

)