问题标签 [streaming-algorithm]

给定的原始问题是包含 5GB URL 的文件，该文件包含最后一天访问的 URL，找到前 k 个频繁访问的 URL。该问题可以通过使用哈希映射来计算不同 URL 的出现次数并在最小堆的帮助下找到前 k 个来解决，花费 O(n log k) 时间。

现在我在想，如果输入的是无限的在线数据流（而不是静态文件），那我怎么知道最后一天的前k个URL呢？

或者我可以对系统进行任何改进，使我能够动态获取最后一分钟、最后一天和最后几个小时的前 k 个 URL？

任何提示将不胜感激！

我正在寻找一种方法来有效地维护来自给定数据流的 1 分钟滑动窗口中的一组值（~100k 值/秒）。

我正在寻找最多对数插入时间的解决方案（因为值的基本时间排序向量具有o（n））

我有一个以一定速率到达的 int 值流。每 5 分钟，我想根据这些值计算一些百分位数，然后重新开始。

问题：我不想浪费太多内存，所以我只想保留几个 KB 的值。如果我的缓冲区在 5 分钟内没有填满，我可以完美地计算百分位数。但是，如果缓冲区确实填满，我想开始删除一些值（可能使用此处建议的水库采样和随机驱逐 - Percentiles of Live Data Capture）。不幸的是，我找不到在这两种情况下都适用的解决方案 - 如果缓冲区未满，我不想驱逐或忽略值，一旦它满了并且我开始驱逐，我总是会引入偏见。

我有两个流，streamA并且streamB. 每个streamA都有一个 ID，并且匹配的事件streamB将具有相同的 ID。

我想知道在1 分钟的滑动窗口之后streamA哪些 ID 没有进入。streamB

我试过这个，但没有成功：

from streamA as A join streamB#window.time(1 min) as B on A.id == B.id select S.Id insert expired events into streamC;

让我知道如何解决这个问题。

我知道以下针对重击手的算法：

如果我错了，请纠正我，但这个算法不会在 O(n) 中运行。是否可以修改此算法，使其在 O(n) 中运行，同时保持 O(1/epsilon) 的空间使用？

对于数据流，算法的重点是返回顶部 epsilon*t 项。Epsilon 以百分比形式给出（例如，对于至少出现 10% 的时间的数据，输入 0.1）。

Count min sketch 使用不同的散列函数将流中的元素映射到散列函数。如何从草图映射回来以找到最常见的项目？考虑到已经传递了足够多的元素（数百万）并且我们不知道这些元素。

我正在寻找一种方法来计算流数据的香农信息熵估计 H'(X)。随机变量 X 的状态空间很大，数千次这样的计算会并行运行，因此在内存中存储每个 X 观测值和对应的计数器是不可行的，因此无法使用常规计算公式。

据我所知，互联网上没有这种算法的实现。我所能找到的只是几篇包含大量数学内容（可能还有一些伪代码）的论文，我要么无法从实际的角度解读，要么算法无法用于一般目的（例如要求流大小已知） - 示例：[1]。

是否有任何可用的实现/可用算法或 Python 库用于我无法找到的数据流的熵估计计算？或者是否有另一种方法如何以内存友好的方式检索熵估计？提前致谢。

[1] LALL A. 等人。用于估计网络流量熵的数据流算法。2006. [在线]。可在：https ://www.cc.gatech.edu/~jx/reprints/Sigm06_entropy.pdf