What is the distribution of elements on the big universe? If it isn’t uniform, then perhaps splitting into ‘heavy hitters’ and rare elements is useful.
On the whole, it appears a Bloom filter will be a good data structure, combined with a vector of elements (filters don’t allow easy iteration).