Алгоритм для 'k' 'наиболее часто встречающихся чисел

Я искал наиболее эффективный (потоковый ??) алгоритм, который сообщает мне «k» наиболее часто встречающихся элементов в потоке данных в любой момент времени. Этот пост: «Разделяй и властвуй» алгоритмы потока данных заинтересовали меня.

Например, предположим, что есть числа: (4,3,5,1,6,2,4,3,3,8,9,1), и я запрашиваю 3 наиболее часто встречающихся числа (скажем), тогда я должен получить (3,4,1) в качестве ответа.

Я пытался искать в Интернете, но не смог найти место, которое дает подход и говорит, что это лучшее. Тривиальным решением было бы использование кучи или сбалансированного бинарного дерева, но я думаю, что есть лучший способ, и я хотел знать, документировано ли оно где-нибудь.

Редактировать: я ищу алгоритм, который всегда дает правильный ответ, а не алгоритм согласования (многие из которых всплывают в результатах поиска), которые так или иначе полагаются на распределение данных

$k=1$$o(n)$

$n/k$

$k$$k$

Я также рекомендую прочесть раздел 8.1.3 «Поиск по частоте в потоках данных» следующей книги:

Джавэй Хан, Мишлин Камбер. Data Mining --- Концепции и методы, второе издание, издательство Morgan Kaufmann , 2006.

Он вводит алгоритм, известный как подсчет потерь , который аппроксимирует частые элементы (элементы, чья поддержка выше некоторого min_support ) с произвольной точностью.

Не совсем то, что вы хотите, но я подумал, что это может помочь.