Cold Filter
Cold Filter
复制标题
冷过滤器
DOI：
10.1145/3183713.3183726
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Steve Uhlig
中科院分区：
文献类型：
--
作者：
Yang Zhou;Tong Yang;Jie Jiang;Bin Cui;Minlan Yu;Xiaoming Li;Steve Uhlig
近似流处理算法，如Count-Min sketch， Space-Saving等。，支持数据库、存储系统、网络和其他领域的众多应用程序。然而，实际数据流的不平衡分布对现有算法提出了很大的挑战。为了增强这些算法，我们提出了一个称为冷过滤器（CF）的元框架，它可以实现更快，更准确的流处理。与现有的主要针对热点的过滤器不同，我们的过滤器在第一阶段捕获冷项，在第二阶段捕获热项。此外，现有的过滤器需要双向通信——在两个阶段之间频繁交换；另一方面，我们的过滤器是单向的——每个项目最多进入一个阶段一次。我们的过滤器可以准确地估计冷项目和热项目，使其具有通用性，使其适用于许多流处理任务。为了说明我们的过滤器的好处，我们将其部署在三个典型的流处理任务上，实验结果表明速度提高了4.7倍，精度提高了51倍。所有源代码都在Github上公开提供。
Approximate stream processing algorithms, such as Count-Min sketch, Space-Saving,etc., support numerous applications in databases, storage systems, networking, and other domains. However, the unbalanced distribution in real data streams poses great challenges to existing algorithms. To enhance these algorithms, we propose a meta-framework, called Cold Filter (CF), that enables faster and more accurate stream processing.Different from existing filters that mainly focus on hot items, our filter captures cold items in the first stage, and hot items in the second stage. Also, existing filters require two-direction communication - with frequent exchanges between the two stages; our filter on the other hand is one-direction - each item enters one stage at most once. Our filter can accurately estimate both cold and hot items, giving it a genericity that makes it applicable to many stream processing tasks. To illustrate the benefits of our filter, we deploy it on three typical stream processing tasks and experimental results show speed improvements of up to 4.7 times, and accuracy improvements of up to 51 times. All source code is made publicly available at Github.