PerseforeComplete

Если вам допустима потеря точности - посмотрите на hyperloglog. Можно во много раз уменьшить потребление памяти.

Такая структура реализована, например, в redis. Там она займёт 12 Кбайт при погрешности в 0,81%.