data structure for RLE-style compression

Question

lets say i have numbers from 1-10Million (customer ids). each single number is associated with 1 of 3 possible values - A,B,C.

i know that very large adjacent regions of about 1000 elements are in the same category.

what is a data structure that allows me to save the link between number range and category in a memory-efficient way?

also, is there a java implementation of an interval-tree, which was suggested in an answer.

Answer 1

You can try LinkedListMultimap from Google Collections with some tricky logic.

What is tricky logic: each odd value represent begin of the interval and each even value represent end of the interval.

For example, you have 1001-1100 ids in A, 1101-1300 in B and 1301-1400 again in A

multimap.put (A, 1001); 
multimap.put (A, 1100);

multimap.put (B, 1101);
multimap.put (B, 1300);

multimap.put (A, 1301);
multimap.put (A, 1400);

Answer 2

Create 3 interval trees, or sorted map of (begin, end) pairs, each representing the categories A, B and C.

Answer 3

Start by transposing your data structure, t.i. instead of storing a customer -> category (A/B/C) mapping, store a category -> customers mapping. I've found transposition to be a common and cool method for designing very efficient datastructures.

Now, use 3 bitmaps (bitmasks, bitsets like java.util.BitSet) for each of the 3 A,B,C tables. The i-th bit in A table will tell whether customer number 'i' is in category A.

Each of these tables will take up only N/8 bytes of memory, which is just 3.75mb given your 10mln customers.

(note that this will work only if your customer id's are sequential integers)