Есть ли алгоритм для выполнения выборки коллектора, когда точки в потоке данных связаны с весами?
Существует ли алгоритм отбора проб из взвешенного коллектора?
Ответ 1
Алгоритм Павлоса Эфраиммида и Пола Спиракиса решает именно эту проблему. Оригинальная статья с полными доказательствами опубликована с заголовком "Взвешенная случайная выборка с резервуаром" в "Обращениях обработки информации 2006", но вы можете найти простое резюме здесь.
Алгоритм работает следующим образом. Прежде всего, обратите внимание, что другой способ решить невзвешенную выборку коллектора - это присвоить каждому элементу случайный идентификатор R между 0 и 1 и поэтапно (скажем, с кучей) отслеживать верхние k идентификаторы. Теперь посмотрим на взвешенную версию, и пусть i-й элемент имеет вес w_i. Затем мы модифицируем алгоритм, выбирая id i-го элемента как R ^ (1/w_i), где R снова равномерно распределено в (0,1).
Другая статья, говорящая об этом алгоритме, - этот от людей Cloudera.
Ответ 2
Вы можете попробовать алгоритм A-ES из этой статьи S. Efraimidis. Это довольно простое кодирование и очень эффективное.
Надеюсь, что это поможет,
Benoit