Алгоритм подсчета с потерями - Lossy Count Algorithm

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

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

Алгоритм

Общий алгоритм описан ниже.^[1]

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

Рекомендации

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

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