algorithm - 在google的dremel中，top-k查询使用的是什么算法？

Question

Google 的 Dremel 算法支持 top-k 查询。有人能告诉我 top-k 查询使用什么算法吗？

score 1 · Accepted Answer

像堆？

堆可用于在 O(nlogk) 时间内回答询问排序列表中前 k 个元素的查询。

score 0 · Accepted Answer

我想你知道 Dremel 纸吗？

它说：

一些 Dremel 查询，例如 top-k 和 count-distinct，使用已知的一次性算法（例如，[4]）返回近似结果。

参考如下：

[4] Z. Bar-Yossef、TS Jayram、R. Kumar、D. Sivakumar 和 L. Trevisan。计算数据流中的不同元素。在 RANDOM，第 1-10 页，2002 年。

这有帮助吗？

2 回答 2