Counting distinct elements over sliding windows
Counting distinct elements over sliding windows
复制标题
计算滑动窗口上的不同元素
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Yaron Kassner
中科院分区：
文献类型：
--
作者：
Eran Assaf;R. Ben;Gil Einziger;R. Friedman;Yaron Kassner
在分布式拒绝服务（DDoS）攻击中，攻击者试图通过来自多个设备的大量看似合法的请求来禁用服务;这通常伴随着在短时间内访问系统的不同IP地址/流的数量急剧增加。因此，滑动窗口上的不同元素的数量是DDoS识别中的基本信号。此外，评估特定流最近是否访问过系统（称为集合成员问题）可以帮助我们识别攻击方。在这里，我们展示了如何扩展的功能，一个国家的最先进的算法集成员在W元素滑动窗口。我们现在还支持不同流计数的估计，使用少至log 2（W）的附加位。
In Distributed Denial of Service (DDoS) attacks, an attacker tries to disable a service with a flood of seemingly legitimate requests from multiple devices; this is usually accompanied by a sharp spike in the number of distinct IP addresses / flows accessing the system in a short time frame. Hence, the number of distinct elements over sliding windows is a fundamental signal in DDoS identification. Additionally, assessing whether a specific flow has recently accessed the system, known as the Set Membership problem, can help us identify the attacking parties. Here, we show how to extend the functionality of a state of the art algorithm for set membership over a W elements sliding window. We now also support estimation of the distinct flow count, using as little as log2 (W) additional bits.