Хранить лучшие k результатов из count-min-sketch

BYsBro спросил: 07 октября 2018 в 02:15 в: java

Мне нужно хранить топ k наиболее часто встречающихся элементов в потоке. Для оценки частоты я использую алгоритмы count-min-sketch. Мой поток состоит из ключей (в виде строки). Таким образом, в основном каждый раз, когда я сталкиваюсь с новым ключом в своем потоке, я вычисляю частоту текущего ключа до сих пор, просматривая структуру данных count-min-sketch. Однако я не могу хранить самые верхние k наиболее часто используемых ключей.

Моей первой идеей было хранить их в мини-куче с фиксированным размером k. И я храню [частоту, ключ] внутри этой минимальной кучи с частотой компаратора. Таким образом, каждый раз, когда я получаю частоту ключа, я пытаюсь увидеть, превышает ли размер кучи k, если это так, то я сравниваю частоту текущего ключа с максимальной (самой маленькой) частотой в минимальной куче, если мой текущий ключ Частота больше, чем я открываю верхнюю часть и вставляю свой ключ в кучу.

Однако я понимаю, что min-куча не является набором, что означает, что она допускает дублирование. Допустим, у меня есть очень горячая клавиша, и я продолжаю считать ее в потоке, поэтому каждый раз, когда я вставляю эту [частоту, ключ] в кучу, в итоге моя куча будет заполнена одним и тем же ключом, только разными частотами.

Так что мне интересно, есть ли хороший способ сохранить верхний k различный более частый элемент в count-min-sketch.


0 ответов