Применение HyperLogLog к выборке населения
Алгоритм HyperLogLog от Flajolet и др. Описывает умный способ оценки мощности множества, используя только небольшой объем памяти. Тем не менее, он учитывает все N элементов исходного набора в расчете. Что если бы у нас был доступ только к небольшой случайной выборке (скажем, 10%) от исходного N? Было ли какое-либо исследование о том, как HyperLogLog или подобные алгоритмы могут быть адаптированы к этой ситуации?
Мне известно, что это, по сути, проблема, описанная как отдельная оценка стоимости, для которой существует множество исследований (см., Например, эту статью для обзора). Тем не менее, в исследовании оценки отдельных значений, о котором я знаю, используется ряд специальных оценок, очень отличающихся от подхода, используемого HyperLogLog. Поэтому мне интересно, задумывался ли кто-нибудь об адаптации HyperLogLog для отдельной задачи оценки стоимости.
2 ответа
Тем не менее, в исследовании оценки отдельных значений, о котором я знаю, используется ряд специальных оценок, очень отличающихся от подхода, используемого HyperLogLog.
Да, потому что они решают совершенно другую проблему.
Предположим, вы только что конфисковали тайник с 1000 000 поддельных долларовых купюр и хотите узнать количество различных серийных номеров.
Отобрав 100 000 из них (используя HyperLogLog, поскольку у вашей старинной паровой счетной машины всего 1 Кб памяти) вы насчитываете 5000 различных серийных номеров, каждый из которых встречается где-то около 20 раз. Тогда вы можете быть почти уверены, что весь тайник будет содержать только немногим более 5000 различных серийных номеров.
Теперь предположим, что 1 серийный номер встречается 95,001 раз, а 4999 серийных номеров встречаются только один раз. Очевидно, некоторые добросовестные банкноты попали в ваш тайник. Теперь вы можете быть уверены, что в тайнике содержится около 5% честных банкнот, так что весь тайник содержит около 50 000 различных серийных номеров.
Обратите внимание, что распределение частот в вашем образце используется, чтобы сделать вывод о распределении во всем тайнике. На самом деле это упоминается как один из методов ad hoc (ваши слова) во второй цитируемой вами статье ("Оценка числа различных значений (..) на основе выборки"):
Идея параметрической оценки состоит в том, чтобы подогнать распределение вероятностей к наблюдаемым относительным частотам различных значений атрибута.
Также обратите внимание, что результаты HyperLogLog и аналогичных методов абсолютно нечувствительны к распределению выборок по их значениям. Но ваша окончательная оценка, очевидно, во многом зависит от этого!
Мой совет: используйте метод по вашему выбору (например, HyperLogLog), чтобы подсчитать количество различных значений в вашей выборке, а затем используйте один из методов в "Оценке на основе выборки", чтобы оценить количество значений во всем мультимножестве, или используйте ваши предыдущие знания о распределении мультимножества для расчета оценки (возможно, вы видели печатную машину фальшивомонетчика, и вы знаете, что она может печатать только один серийный номер)
Поиск цитаты - замечательная вещь. Я не очень знаком с этими двумя проблемами, так что эта статья может быть не совсем то, что вы имели в виду. По крайней мере, они, безусловно, говорят о HyperLogLog и его связи с проблемой, так что, возможно, это насытит ваше любопытство.