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

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

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

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

import base64, os

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

Мой первый подход состоял в том, чтобы использовать hashset следующим образом:

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

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

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

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

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

Спасибо за любую помощь, которую вы можете предоставить!

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

Ответы

Ответ 1

Я бы рекомендовал использовать эскизы Hash, а именно (Super) Log Log sketches или Hyper Log Sketches.

Вы можете проверить и, возможно, использовать и улучшить простую реализацию python, которую я сделал: https://github.com/goncalvesnelson/Log-Log-Sketch

Ответ 2

Я бы посоветовал вам попробовать фильтр цветения. Даже при таком количестве данных вы можете добиться чрезвычайно низких коэффициентов ошибок со скромными системными требованиями. Учитывая, что вы будете использовать (грубо) оптимальный k = ln (2) * (размер фильтра цветения в битах)/(10 миллиардов), вы можете рассчитать свой размер фильтра цветения в битах как - ((10 миллиардов) * ln (желаемое ложное срабатывание скорость))/п (2) ^ 2.

Например, с менее чем 2 гигабайтами памяти вы можете получить коэффициент ошибок 0,1%. Очень быстрая и чрезвычайно простая реализация всего этого http://mike.axiak.net/python-bloom-filter/docs/html/