O (n) Heavy-Hitters с пространством O (1 / эпсилон)?

Я знаю следующий алгоритм для тяжелых нападающих:

Algorithm findHeavyHitters(epsilon, inputStream)
    integer k = ceiling(1 / epsilon) - 1
    initialize hashmap H of size k

    while an item i from the input stream arrives:
        if H[i] exists
            increment the value associated with H[i]
        elsif number of items in H < k
            put H[i] into map with value of 1
        elseif there exists an entry j with a value of 0
            remove j and put H[i] into map with value of 1
        else
            decrement all values in H by 1
    endwhile

    return H

Поправьте меня, если я ошибаюсь, но этот алгоритм не работает за O(n). Можно ли изменить этот алгоритм так, чтобы он работал за O(n), сохраняя при этом использование пространства O(1/эпсилон)?

Для потока данных суть алгоритма состоит в том, чтобы вернуть верхние эпсилон*t элементов. Эпсилон задается в процентах (например, введите 0,1 для данных, которые появляются не менее 10% времени).


bigdata algorithm streaming-algorithm
person fluffychaos    schedule 16.06.2016    source источник
comment
Почему вы думаете, что он не работает за O(n)?   -  person rici    schedule 16.06.2016
comment
В блоке else нам нужно пройтись по всем существующим тяжелым нападающим, чтобы уменьшить каждый на 1.   -  person fluffychaos    schedule 16.06.2016
comment
Я думал, что это было ваше возражение, поэтому я рассмотрел его в своем ответе. Возможное возражение о том, что поиск в хэш-таблице в худшем случае O(n), не может быть так легко устранено; afaik, вы не можете получить наихудший случай меньше, чем O (n log n).   -  person rici    schedule 16.06.2016
comment
Связано: stackoverflow.com/a/21705869/1566221   -  person rici    schedule 16.06.2016
comment
@fluffychaos Я планирую реализовать мощные нападающие, используя скетч count-min. Не могли бы вы объяснить, какие случаи обрабатывает блок else (уменьшает все значения на 1)? Также как добавление новой переменной базы помогает в решении, предложенном в ответе?   -  person user3508140    schedule 25.08.2019

Ответы (1)


arrow_upward
1
arrow_downward

Алгоритм работает в среднем за время O(n), исходя из того, что поиск хэша в среднем занимает O(1).

Есть две детали реализации. Во-первых, последний шаг, который, кажется, включает в себя прикосновение к каждому значению в H:

  • уменьшить все значения в H на 1

Чтобы сделать это O (1), мы добавляем одно дополнительное место хранения, называемое base, которое инициализируется равным 0. Затем мы модифицируем алгоритм следующим образом:

while an item i from the input stream arrives:
    if H[i] exists
        increment the value associated with H[i]
    elsif number of items in H < k
        put H[i] into map with value of base + 1
    elseif there exists an entry j with a value of base 
        remove j and put H[i] into map with value of base + 1
    else
        increment base
endwhile

Вторая проблема — найти запись со значением base (или 0) в O(1). Это можно сделать, сохранив элементы в виде «гребенки»: связанного списка из двусвязных списков. Каждый внутренний связанный список содержит записи с определенным количеством. Внешний связанный список содержит списки счетчиков, упорядоченные по количеству, причем заголовок указывает на список с наименьшим количеством. Если вы нарисуете эту структуру данных, она будет выглядеть как гребенка:

[  base    ] -> entry a -> entry b -> entry c
    |
[ base + i ] -> entry d
    |
[ base + j ] -> entry e -> entry f
    |
   etc.

Хэш-таблица теперь указывает на записи, а не содержит их. Чтобы увеличить количество одной записи, запись удаляется из ее списка (если список содержит более одного элемента) и либо вставляется в следующий список, либо помещается в одноэлементный список, который вставляется после списка, в котором она находилась. , в зависимости от количества, связанного со следующим списком. Эта операция O (1).

Структура данных гребенки по-прежнему равна O(k), где k — количество элементов в хеше, потому что не может быть больше различных счетчиков, чем элементов.

Вместо двусвязных списков можно использовать простой массив и список индексов первой записи с каждым счетчиком. Чтобы переместить запись в следующее ведро подсчета, вы начинаете с того, что заменяете ее последней записью с этим подсчетом, а затем либо продвигаете начало следующего списка подсчета, либо вставляете новую запись списка подсчета, в зависимости от того, является ли подсчет следующего списка подсчета. один больший или более чем один больший. Чтобы выполнить замену, необходимо обновить расположение двух замененных записей в хэше, но это все еще O (1).

person rici    schedule 16.06.2016
comment
Классная структура данных - спасибо! У меня все еще есть проблемы с пониманием того, как поиск записи выполняется в O (1). Если вы используете LinkedList из LinkedList, в худшем случае вам не придется перебирать все значения внешнего LinkedList, чтобы найти, с каким счетчиком связана запись? Потенциально это все еще может быть обход O (k). Или, в случае, когда все k элементов сопоставлены с одним и тем же счетчиком, не потребуется ли потенциально пройти все k элементов внутреннего списка, чтобы найти нужный узел? - person fluffychaos; 16.06.2016
comment
@fluffychaos: вы используете хэш-таблицу, как и в исходном алгоритме. Хэш-таблица содержит указатели на узлы связанного списка. Объединение связанных списков не перемещает узлы, поэтому указатели хеш-таблиц будут работать. Если вы используете структуру данных секционированного массива (в конце), вам нужно изменить ссылки хеш-таблицы для замененных элементов, но всегда есть не более двух замененных элементов (иногда замена не требуется). (Я упомянул все это в ответе.) - person rici; 16.06.2016