В Google Dremel, какой алгоритм использует этот запрос top-k?
Алгоритм Google Dremel поддерживает топ-k запросов. Может ли кто-нибудь сказать мне, какой алгоритм использует запрос top-k?
2 ответа
Как куча?
Куча может использоваться для ответа на запрос, запрашивающий верхние k элементов в отсортированном списке, за O(nlogk) время.
Я думаю, вы знаете о Dremel Paper?
Вот ссылка: https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36632.pdf
Это говорит:
Некоторые запросы Dremel, например top-k и count-различным, возвращают приблизительные результаты, используя известные однопроходные алгоритмы (например, [4]).
Ссылка следующая:
[4] З. Бар-Йосеф, Т.С. Джайрам, Р. Кумар, Д. Сивакумар и Л. Тревизан. Подсчет отдельных элементов в потоке данных. В СЛУЧАЙНОМ, страницы 1–10, 2002.
Это помогает?