3 ms·
How would I use this data-structure in an application? Is it basically a replacement for a byte array with improved space characteristics?
by javajosh 12y ago
How would I use this data-structure in an application? Is it basically a replacement for a byte array with improved space characteristics?
- twic 12y agoSemantically, it's a boolean array. Or, to look at it another way, a set of integers, where a[n] is true if n is in the set. This representation, and the various others the paper compares it to, are useful when the array is fairly sparse - the introduction suggests the range 1/10000 to 1/64 of the bits being set. They're a lot more compact, but still support key operations - ORing, ANDing, testing a particular bit, enumerating all set bits - fairly efficiently. The major motivating use of structures like this is for bitmap indexes in databases. Bitmap indexes store a single bit of data per record - it could be "is this person a current employee?", "has this user ever bought anything?", etc. If you can encode these compactly, you can use them to very quickly winnow vast amounts of data down to a small number of interesting records, which you can then retrieve one by one.