First something general. Maybe you can try DBM::Deep for persistent data. And try some home-made struct made with the help C::Binary::Convert (but not pure perl obviously). At least it can give you an idea of what you can save memory-wise and how fast you can go.

Another idea (that came to me while previewing) is that maybe you could split your record into two - one for counts and one for the condition -- working out the intersection later

hth --stephan