Ученые создали новый эффективный способ подсчета уникальных объектов

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

Представьте, что вас отправили в тропический лес для проведения учета дикой природы. Каждый раз, когда вы видите животное, делаете фото. Ваша камера отслеживает общее количество снимков, но вас интересует только количество уникальных животных, которых еще не было в кадре. Как лучше всего получить это число? Очевидное решение требует запоминания каждого животного и сравнения каждого нового с уже имеющимися в списке, отметил Ланс Фортнау, компьютерный ученый из Технологического института Иллинойса. Однако при тысячах записей такой подход становится сложным.

Ситуация усложняется, если, например, Facebook захочет подсчитать количество уникальных пользователей, заходящих на сайт каждый день, даже если они заходят с нескольких устройств и в разное время. Здесь уже речь идет о списке, который может достигать миллиардов записей.

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

Алгоритм CVM, названный в честь его создателей - Сурава Чакраборти из Индийского статистического института, Винодчандрана Вариама из Университета Небраски в Линкольне и Кулдипа Мила из Университета Торонто, представляет значительный шаг к решению проблемы уникальных элементов, с которой ученые бьются более 40 лет. Эта проблема заключается в поиске способа эффективно отслеживать поток элементов и оценивать количество уникальных из них.

"Новый алгоритм удивительно прост и легок в реализации," сказал Эндрю МакГрегор из Университета Массачусетса в Амхерсте. "Не удивлюсь, если это станет стандартным подходом к решению проблемы уникальных элементов на практике."

Для иллюстрации проблемы и решения алгоритма CVM представьте, что вы слушаете аудиокнигу "Гамлет". В пьесе 30,557 слов. Сколько из них уникальны? Чтобы узнать, можно прослушать пьесу, записывая каждое слово в алфавитном порядке в блокнот и пропуская уже записанные. Этот подход требует объема памяти, примерно равного количеству уникальных слов.

В типичных ситуациях потоковой обработки данных может быть миллионы элементов. "Вам может не захотеться хранить все," сказал Вариам. Здесь и приходит на помощь алгоритм CVM. Основной трюк заключается в использовании случайности.

Вернемся к "Гамлету", но теперь ваша рабочая память — доска для записей — вмещает всего 100 слов. Начав прослушивание, записываете первые 100 услышанных слов, пропуская повторяющиеся. Когда память заполнена, делаете паузу и подбрасываете монету для каждого слова. Орел - слово остается, решка - удаляется. После этого у вас останется около 50 уникальных слов.

Далее следует первый раунд. Продолжаете слушать "Гамлет", добавляя новые слова по мере их появления. Если слово уже в списке, снова подбрасываете монету. Решка - слово удаляется, орел - остается. Продолжаете до тех пор, пока на доске не окажется 100 слов, затем случайно удаляете половину.

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

В третьем раунде для сохранения слова нужно три орла подряд, в четвертом - четыре и так далее.

В конце последнего раунда, по завершении "Гамлета", каждый отобранный случайным образом элемент имеет одинаковую вероятность быть в списке: 1/2^k. Если, например, в конце у вас 61 слово после шести раундов, можно разделить 61 на вероятность 1/2^6, чтобы оценить количество уникальных слов — получится 3,904.

Чакраборти, Вариам и Мил математически доказали, что точность этой методики масштабируется с размером памяти. В "Гамлете" точно 3,967 уникальных слов. В экспериментах с памятью в 100 слов средняя оценка после пяти попыток составила 3,955 слов. С памятью в 1,000 слов средняя оценка улучшилась до 3,964. "Конечно," сказал Вариам, "если память настолько велика, что вмещает все слова, мы получаем 100%-ную точность."

"Это отличный пример того, как даже для очень базовых и хорошо изученных проблем иногда могут быть найдены очень простые, но не очевидные решения," сказал Уильям Кузмаул из Гарвардского университета.