摘要：
提出了一种新的sketch，称为Slim-Fat（SF）sketch，其内存要小得多。 支持更新的查询足迹。
SF sketch的关键思想是维护两个单独的sketch：一个称为Slimsubsketch的小sketch和一个称为Fat-subsketch的大sketch。 Slimsubsketch支持快速准确的查询。 Fat-subsketch用于辅助Slim-subsketch的插入和删除。
我们实施并评估了SF sketch以及几个先前的sketch，实验结果表明，就准确性而言，SF sketch明显优于最常用的CM sketch。
背景/问题：
Count sketch被提出后，面临着两种类型的错误——过高估计错误（查询结果的值大于真实值）和低估错误（查询结果的值小于真实值）。
在改进Count sketch时，提出了Count-min（CM）sketch，该sketch不会遭受估计不足的误差，而只会遭受估计过高的误差。
后来又提出了保守更新（CU）sketch，以不支持项目删除为代价提高了准确性，即一旦将有关项目的信息插入到CU sketch中，就不能从sketch中删除它，而不会影响sketch中其他项目的信息。
由于CM sketch支持删除并且没有低估错误，因此它仍然是最受欢迎的sketch。但是，我们发现CM sketch未压缩。
解决办法：
本文的设计目标是在保留优势的同时节省空间并提高CM sketch的准确性。
提出了一个新的sketch，称为SlimFat（SF）sketch，与现有技术相比，它可以实现更高的精度，同时支持删除操作，并实现与广泛使用的CM sketch相同的查询速度。
关键思想是维护两个单独的sketch：一个用于称为Slim-subsketch的查询，另一个用于称为Fat-subsketch的更新。与Fat-subsketch相比，Slim-subsketch具有明显更少的计数器。
这两个层次体系结构背后的动机是将查询和更新分开。
因此，我们将包含所有信息的大sketch存储在本地，并仅发送包含信息的小sketch以进行查询，以减少通信开销。
具体实现：
接下来将介绍SF-sketch的五个不同版本，我们将它们命名为SF1-sketch到SF4-sketch，最后是SFF-sketch，这是我们的最终设计。
每个版本都解决了其先前版本的限制。
有一个Slim-subsketch，以及一组数组，每个数组具有相对更多的计数器，称为Fat-subsketch。
在插入或删除项目时，我们首先更新Fat-subsketch，然后根据对Fat-subsketch的观察来更新Slim-subsketch。
在插入项目时，如果传入项目映射到的Slim-subsketch中任何计数器的值已经大于该项目已被插入的次数，则递增该计数器只会降低查询操作期间的准确性。因此，这种计数器不应增加。
Fat-subsketch使我们能够确定Slimsubsketch中的此类计数器是否已经大于项目已出现的次数。
SF1：
如图所示，SF1-sketch由Slim-subsketch和Fat-subsketch的d个数组组成。 Fat-subsketch恰好是标准的CM-sketch，与Slim-subsketch相比，计数器要多得多。
一个项目e进入时，现在Fat的CM sketch上找到最小值，用Bmin e表示当前的最小频率。
插入：要将项e插入Slim-subsketch中，我们计算d个哈希函数并标识d个计数器中的最小计数器，如果最小计数器不小于Bmin e，则插入操作结束， 否则我们将最小的计数器增加1。
查询：完全由Slimsubsketch回答，计算d个哈希函数，返回左边slim部分的最小值。
SF2：
为了支持删除，除了Slim和Fatsubsketch外，SF2-sketch还维护了另一个sketch，称为Deletion-subsketch，由C表示。
与Fatsubsketch不同，它的所有参数与Slim-subsketch相同，Deletion-subsketch有助于确定删除项目时Slim-subsketch中哪些计数器递减。
只有当Slim-subsketch的值大于Deletion-subsketch的值得时候，才将Slim-subsketch的值减一。
SF3：
不采用单独的Deletion-subsketch，把其和Fatsubsketch整合在了一起。
通过一个与slim关联的z counter去与slim比较，删除的时候slim里比z counter大的部分才减一，这是基于Slim-subsketch中的计数器的值应小于或等于Fat-subsketch中其所有关联计数器的值的总和。
SF4：
如图所示，在SF4-草图的Fat-subsketch中，我们有d个数组，每个数组具有w个存储桶，并且每个存储桶现在包含z个计数器而不是一个计数器。 我们用Bi [j] [k]表示Fat-subsketch中第i个数组的第j个存储桶中的第k个计数器。
Fat-subsketch中的每个数组Bi与两个均匀分布的独立哈希函数相关联。
SFF:
SFFsketch的结构以及查询和插入过程与SF4-sketch的结构完全相同。
SFF sketch背后的关键思想是，执行删除操作时，我们使Slim子草图中的每个计数器的值始终小于或等于最大计数器的值，而不是相应的Fat桶的总和。
网友评论