In the context of the overall algorithm, wouldn't you cluster the movie ratings first anyway (O(n)), so most of the algorithm would do computations on those clusters which would have less data than single movies to begin with? I'd worry about minimizing the size of the clusters instead.
You'll also probably want some kind of hierarchical data structure to use the cache efficiently. This doesn't help with that.
If the movie ratings are sorted, a lot of the data becomes redundant and can be left out entirely.
Those values should be all 0-based too, since it saves you some bits (3 bits for 1-5 vs 2 bits for 0-4). With that "optimization" alone you save more bits than with the early bit packing attempt.
The solution with primes also doesn't scale well. The bigger the primes get, the more empty space you create.
The actual rating is a tiny part of the data per movie, so there's not much saving there. And clustering would have to be done instead of indexing by movie / user, so it would probably make performance worse overall.
Indexing by movie / user is done exactly for the reason of using the cache efficiently. Unfortunately, you have to iterate through both movies and users, so you either store the sparse matrix twice (once movie-indexed, once user-indexed) OR you deal with lots of cache misses half the time.
And, yes, all the values are stored 0-based for exactly that reason :) It's an even bigger saving for storing timestamps.
Not sure what you mean about the prime solution not scaling well - 3 primes of ~2^20 can be stored in ~2^60 (i.e. within 8 bytes) as opposed to within 3 4-byte integers.
When it really sucks is when you're storing lots of small integers, e.g. 20 things in [0,1,2,3] - that gets very inefficient fast, and it'd be much more efficient to use normal bitfields.
Comments
In the context of the overall algorithm, wouldn't you cluster the movie ratings first anyway (O(n)), so most of the algorithm would do computations on those clusters which would have less data than single movies to begin with? I'd worry about minimizing the size of the clusters instead. You'll also probably want some kind of hierarchical data structure to use the cache efficiently. This doesn't help with that. If the movie ratings are sorted, a lot of the data becomes redundant and can be left out entirely. Those values should be all 0-based too, since it saves you some bits (3 bits for 1-5 vs 2 bits for 0-4). With that "optimization" alone you save more bits than with the early bit packing attempt. The solution with primes also doesn't scale well. The bigger the primes get, the more empty space you create.
The actual rating is a tiny part of the data per movie, so there's not much saving there. And clustering would have to be done instead of indexing by movie / user, so it would probably make performance worse overall.
Indexing by movie / user is done exactly for the reason of using the cache efficiently. Unfortunately, you have to iterate through both movies and users, so you either store the sparse matrix twice (once movie-indexed, once user-indexed) OR you deal with lots of cache misses half the time.
And, yes, all the values are stored 0-based for exactly that reason :) It's an even bigger saving for storing timestamps.
Not sure what you mean about the prime solution not scaling well - 3 primes of ~2^20 can be stored in ~2^60 (i.e. within 8 bytes) as opposed to within 3 4-byte integers.
When it really sucks is when you're storing lots of small integers, e.g. 20 things in [0,1,2,3] - that gets very inefficient fast, and it'd be much more efficient to use normal bitfields.