3 ms·
>In the extreme case where you have many, many distinct identifiers, then make [sic] become highly compressible This seems backwards. Each random, incompressib
by dTal 5y ago
>In the extreme case where you have many, many distinct identifiers, then make [sic] become highly compressible
This seems backwards. Each random, incompressible identifier must be stored verbatim exactly once. If you have relatively few identifiers, that are mentioned many times, it doesn't matter at all what you call them. A compressor can just put them in a dictionary and use their reference.
On the other hand, if you have a large number of identifiers, the cost of that dictionary becomes non-trivial.
- 10000truths 5y agoIt makes sense. If the number of identifiers you’re storing exceeds 1/2 the cardinality of the identifier’s underlying key space, then you can simply store the complement at a reduced size. Why store (2^32 - 10) random 4-byte identifiers when I can store 10 instead, and invert the lookup query?
- nimih 5y agoThis seems like a weird argument, since any time I've encountered a UUID or some other randomized identifier in practice, I care about things beyond set containment, like "what order did I see them in" or "the database row attached to the identifier".