Алгоритм подсчета с потерями

Алгоритм подсчета с потерями — это алгоритм идентификации элементов в потоке данных которых , частота превышает заданный пользователем порог. Алгоритм работает путем разделения потока данных на сегменты для часто встречающихся элементов, но при этом за один раз заполняется как можно больше сегментов в основной памяти. Частота, вычисленная этим алгоритмом, не всегда точна, но имеет порог ошибки, который может указать пользователь. Время выполнения и пространство, необходимые алгоритму, обратно пропорциональны указанному порогу ошибки; следовательно, чем больше ошибка, тем меньше след.

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

Алгоритм

Общий алгоритм следующий ^{[ 1 ]}

Шаг 1. Разделите входящий поток данных на сегменты по ширине. $w=1/\epsilon$ , где $\epsilon$ упоминается пользователем как граница ошибки (вместе с минимальным порогом поддержки = $\sigma$ ).
Шаг 2. Увеличьте частоту каждого элемента в соответствии с новыми значениями сегмента. После каждого сегмента уменьшайте все счетчики на 1.
Шаг 3. Повторите. Обновите счетчики и после каждого сегмента уменьшите все счетчики на 1.

Ссылки

^ Хан, Цзявэй. (2006). Интеллектуальный анализ данных: концепции и методы . Камбер, Мишлин. (2-е изд.). Амстердам: Эльзевир. ISBN 978-0-08-047558-5 . OCLC 143252170 .

Мотвани, Р; Маньку, Г.С. (2002). «Приблизительное количество частот в потоках данных». VLDB '02 Материалы 28-й Международной конференции по очень большим базам данных : 346–357.

Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее .

[1] Хан, Цзявэй. (2006). Интеллектуальный анализ данных: концепции и методы . Камбер, Мишлин. (2-е изд.). Амстердам: Эльзевир. ISBN 978-0-08-047558-5 . OCLC 143252170 .

[ 1 ]