20 августа 2018 г.

Оценки квантилей распределений потока данных

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