Как эффективно подсчитывать кардинальность очень больших наборов данных в Python?

я был играю на работе с очень-очень большими наборами данных, как правило, с несколькими миллиардами элементов, которые все хранятся в memcached облаке и периодически выгружаются в файлы, и для одной из моих задач я пытаюсь подсчитать мощность этого множества.

Для некоторого контекста каждый элемент содержит IP-адрес и некоторые другие атрибуты, идентифицирующие человека, и закодирован в base64, размер элемента составляет 20 байт. Уменьшить размер элемента, удалив некоторые поля, невозможно.

Вот что-то, что эмулирует мой набор данных как -версию в памяти (благодаря этому сообщению для генерации строк):

import base64, os

dataset_size = 10000000000 # that's 10 billion, be careful if you run it !
big_dataset = [base64.b64encode(os.urandom(10)) for i in range(dataset_size)]

Мой первый подход состоял в том, чтобы использовать такой хэш-набор:

uniques = set(big_dataset)
print "Cardinality: %d" % len(uniques)

Хотя в теории это прекрасно работает на небольшом наборе данных, как вы можете догадаться, здесь есть заминка :

• : я не могу делать никаких предположений об уникальности своих данных. Я мог бы иметь 50% своего набора данных, которые были бы уникальными, или я мог бы иметь 100% точно так же. Он генерируется динамически через регулярные промежутки времени и зависит от множества факторов, (времени суток, например,)
• размер набора данных в 10 миллиардов. Каждый элемент, закодированный в базе 64, составляет 20 байтов, умноженные на 10 миллиардов, это в среднем несколько сотен гигабайт. К сожалению, у меня нет доступа к машине с таким объемом оперативной памяти!

Я сделал свою домашнюю работу и нашел в лучшем случае несколько научных работ или какие-то малоизвестные библиотеки, но отчасти цель этого состоит в том, чтобы понять, какой подход работает и почему.

Итак, я обращаюсь к вам, пользователи Python, знаете ли вы какой-нибудь алгоритм, который помог бы мне эффективно оценивать количество элементов? Под сложностью я подразумеваю, что меня не очень волнует сложность времени выполнения, но я больше сосредоточен на пространственной сложности.Я не возражаю против того, чтобы немного пожертвовать точностью, если это значительно повысит производительность (, поэтому мне не обязательно знать точное количество уникальных элементов, даже если это было бы идеальным, но, вероятно, нежизнеспособным подходом). Я бы сказал, что до 5% было бы приемлемо. Я ищу что-то конкретно в Python для этого проекта.

Спасибо за любую помощь!

Как отметили некоторые люди, я мог бы использовать Hadoop/MR, но для этого конкретного проекта мы не хотим идти по пути MR и хотели бы изучить алгоритмы, позволяющие эффективно делать это на одной машине, поскольку это может быть применяется к нескольким другим проектам.