点击下方“PaperEveryday”，每天获得顶刊论文解读
题目：Learning to Sketch: A Neural Approach to Item Frequency Estimation in Streaming Data学习素描：流数据中项目频率估计的神经方法
作者：Yukun Cao; Yuan Feng; Hairu Wang; Xike Xie; S. Kevin Zhou
摘要
最近，设计神经数据结构的趋势超越了手工制作的数据结构，通过利用数据分布的模式来提高准确性和适应性。在实时网络分析、网络监控和自动驾驶中，草图被广泛使用，以在有限的空间内估计数据流的项目频率。然而，现有的草图没有充分利用数据流分布的模式，这使得它们很难与擅长记忆模式信息的神经网络紧密结合。基于此前提，我们设想了一个纯粹的神经数据结构作为基础草图，我们称之为元草图，以重塑传统草图的基本结构。元草图在预训练阶段从由合成数据集构成的元任务中学习基本的草图能力，这些数据集遵循Zipf分布，并可以在适应阶段快速适应真实（偏斜）分布。元草图不仅在草图传统数据流方面超越了其竞争对手，而且在支持更复杂的流数据方面也显示出良好的潜力，例如多媒体和图流场景。广泛的实验表明了元草图的优越性，并提供了对其工作机制的见解。
关键词
神经数据结构，草图，元学习，记忆增强神经网络。
I. 引言
在流数据处理中，估计项目频率是一个基本主题，它在网络、数据库和机器学习等领域有着广泛的应用，如实时数据分析、网络流量监控、自然语言处理和搜索排名。面对无限的数据流，一类常见的解决方案使用一种数据结构，以亚线性空间计算每个流项目的出现次数，称为草图。简而言之，草图是一种紧凑地总结流以计算项目频率的结构，且空间预算有限。
在数据流普遍存在偏斜分布的证据下，现有的基于草图的解决方案可以分为两类：基础草图和增强草图，如图1所示。第一类，即基础草图，通过哈希和近似聚合流项目来实现空间紧凑性。基础草图，即CM草图和C草图，使用二维计数器数组作为核心结构。按照基础草图的二维数组结构，一些变体，如CMM草图和CU草图，实现了不同的聚合方法用于频率估计。此外，MLSketch作为基础草图的辅助工具，在网络测量中，通过迭代采样真实流来训练回归模型，从而利用短期流分布模式来优化草图的聚合过程。
![]()
第二类，即增强草图，在基础草图中引入额外的过滤器来分流偏斜分布中的高或低频项目，如A草图、Cold过滤器和Elastic草图。通过过滤高或低频项目，增强草图努力减少由哈希冲突引起的估计误差。此外，（学习）增强草图通过使用预训练的神经网络（简称NN）分类器来记忆短期高或低频项目，从而改进增强草图的过滤器。然而，目前尚不清楚预训练的NN如何适应动态流场景，在这些场景中，项目和频率之间的对应关系会发生变化。此外，许多工作扩展了基础/增强草图以支持多样化的查询类型，从而适应不同的应用场景。
通过回顾性分析，观察到草图的演变符合数据分布的利用。因此，考虑一个通常和自动捕获分布模式的草图是自然的进步，且在有限的空间预算下。在本文中，我们提出了一种新颖的神经结构，称为元草图，其目标是超越基础草图的固有结构，同时专注于流数据领域的一项基本任务，即在严格的空间限制内估计项目频率。元草图作为未来后续工作的新基础草图。例如，它为一系列增强草图提供了性能增益，如果用元草图替换它们相应的基础草图。
简而言之，元草图由元学习和记忆增强神经网络提供支持，并从自动生成的元任务中学习草图能力。根据元任务的类型，我们研究了两个版本的元草图，称为基础和高级元草图。基础元草图在离线方式下用遵循Zipf分布的基础元任务进行训练。
高级元草图通过快速适应流处理的特定运行时来增强其基本草图能力。这是通过模型适应实现的，使用通过采样少量历史数据流生成的自适应元任务。
我们的工作遵循典型的设置，其中项目频率的分布遵循偏斜分布，但项目和频率之间的对应关系会变化。例如，在软件定义网络（SDN）中，草图被部署到可编程交换机上以收集每个流的统计信息，其中IP数据包遵循重尾分布。在分布式数据库中，它有助于收集数据片段的统计信息以优化数据放置和查询缓存，其中查询短语大致遵循Zipf分布。鉴于项目总体遵循特定分布，局部分布，即片段或流上项目-频率对应关系是不同的。与在每个局部分布上重新训练（学习）增强草图相比，高级元草图可以对不同的局部分布保持鲁棒性，性能几乎不受项目-频率对应关系变化的影响。
作为神经数据结构家族的成员，元草图在结构和工作机制上与传统基础草图不同。元草图利用NN的强大编码/解码能力来感知数据分布，并表达/压缩显式或隐式信息，以更好地检索项目频率。同时，元草图是可微分的，可以完全感知频率模式以自我优化。
在本文中，我们在几个重要方面构建并扩展了我们之前的工作：1）我们通过提出一种用于多媒体项目的统一编码策略，解决了将元草图部署到多媒体流场景的挑战（第IV-A节）。2）我们通过展示元草图在建立图摘要和回答两个基本图摘要任务，即边权重和边存在查询方面的优越性，适应元草图的结构和训练以适应图流（第IV-B节）。3）我们提供了元草图的更多技术细节，特别是讨论了对训练稳定性和性能有重大影响的读头（第II-C节）。4）我们提出了新的实验结果，包括对所有主要实验的更新（第V节），分析实验（第VI节）。本文的主要贡献可以总结如下。
我们提出了元草图，这是一种新的基草图和第一个用于流频率估计的神经数据结构。基础元草图通过学习合成流获得草图能力，并在真实流中超越了基草图。高级元草图通过进一步利用真实分布实现更好的准确性和鲁棒性。它实现了与增强草图相当甚至更好的性能，而无需额外的过滤器。
我们提出了一种新的学习数据流分布模式的视角。具体来说，我们专注于分布的偏斜性，而不是像以前的作品那样简单地预测高和低频项目。
元草图可以扩展到各种类型的数据流和相应的查询，基于其总结流数据的能力。在本文中，我们探索了元草图在多媒体和图流场景中的扩展，证明了其有效性。
通过在真实和合成数据集上的广泛实证研究，我们评估了我们提出的元草图，并分析了其主要模块的机制，为提出的神经数据结构提供了见解。
II. 元草图结构
A. 概述
我们考虑一个标准的数据流场景。假设一个数据流，其中包含个项目和个不同项目。每个项目取自项目域中的一个值，其中。频率等于项目在中出现的次数。为了利用学习技术进行项目频率估计，一种朴素的方式是训练一个NN模型（例如，MLP/LSTM），通过多次训练迭代学习/记忆项目和频率之间的映射关系，类似于以前的工作。然而，这违反了流处理的典型设置，其中项目观察是短暂的，因此需要一次处理[31]。此外，对于新的数据流，昂贵的过程必须从头开始重复，这对于实时应用是不可行的。受元布隆过滤器的启发，我们考虑使用元学习和记忆增强网络进行一次性学习（适合单次流处理）的情况。元学习使用采样的元任务来学习解决一类域任务的能力，而不是记忆特定任务的模式。记忆增强网络将外部记忆纳入NN模型，显著增强了NN模型的潜力，拥有更多的可学习参数。同时，它为外部记忆执行高效和显式的操作（即读写），使NN模型能够像传统数据结构一样处理信息。元草图的框架由4个功能模块组成：嵌入（FE）、稀疏寻址（FSa）、存储（M）和解码（Fdec），如图2所示。与传统草图类似，元草图在一次通过中编码并记忆在线流项目，并通过对存储结构的解码来回答查询。因此，我们为元草图定义了2个操作：存储和查询。具体来说，存储操作首先将每个传入的流项目传递给FE以获得嵌入表示，然后将嵌入向量写入M，根据FSa派生的地址。当估计项目的频率时，查询操作通过FSa计算项目在M中的地址，从M中读取相应的信息向量，并通过Fdec从检索到的信息向量中解码频率。![]()
B. 模块和操作
嵌入：模块FE有两个主要目的：1）它将传入的项目转换为一个密集的嵌入向量，该向量捕获与项目频率相关的隐式特征，并作为识别数据流中项目的基础。2）它通过解耦生成一个精炼向量，而不是直接使用进行寻址，从而增强寻址功能并消除其他干扰因素。然后，精炼向量用于派生项目在存储中的地址。相应地，FE由嵌入网络和寻址网络组成。我们假设项目被数值编码以唯一标识，遵循流处理的惯例。因此，我们有这里，是维度为的嵌入向量，是维度为的精炼向量。向量具有多个明确意图：1）它为在FSa中派生项目的地址提供基础。2）它作为写入的项目的压缩向量。3）它为解码项目频率提供了部分输入给Fdec。除了上述功能外，还在感知和压缩特定频率分布的模式中起着至关重要的作用，这将在分析部分中讨论。稀疏寻址：模块FSa的目标是确定嵌入向量存储在存储矩阵中的地址（即，）。实际上，FSa的功能类似于传统草图中的哈希函数，但关键区别在于FSa是可微分和参数化的。元草图的寻址机制依赖于一个3D寻址矩阵和可学习参数以及一个稀疏SoftMax函数：这里，A和的转置的批量矩阵乘法结果在寻址向量。和的值决定了存储嵌入向量地址空间的大小。典型的寻址方法使用一个2D矩阵（）来记录嵌入向量到插槽的映射（其中是插槽的数量）。然而，在我们的方法中，我们增加了一个额外的维度来模拟传统草图的多哈希设置，这提供了更健壮和有效的频率解码。这种增加的动机是，一个2D寻址矩阵可以实现哈希函数的可微分模拟。因此，3D矩阵A模拟了多个哈希函数，从而为学习优化提供了更多的合理性。注意，A的每个2D切片（）是由堆叠个单位向量形成的，A的参数在每次梯度更新后进行归一化，以确保每个切片由单位向量组成。这种归一化步骤有助于防止在通过降低数据精度来压缩A的大小时出现的溢出问题，同时也提高了可解释性（见第VI-A节）。此外，我们使用Sparse SoftMax而不是SoftMax来归一化地址。假设，一种Sparse SoftMax从中获得，符合优化目标，即最小化的。这里，Sparse SoftMax返回输入到概率单纯形的欧几里得投影。通过将的某些位约束为零，Sparse SoftMax带来了几个好处：1）促进在反向传播期间快速派生；2）通过跳过M中对应于零位的插槽来减少存储矩阵访问的开销；3）通过向量压缩实现去噪。存储：对于元草图的存储结构，我们使用一个矩阵来存储基于相应地址的嵌入向量。M的功能类似于传统草图中的2D计数器数组，但具有更好的存储压缩能力。虽然传统草图存储项目计数，但M存储密集向量，由于不同位上值的变化多样性，提供了更大的信息压缩能力。解码：为了估计查询项目的频率，我们使用一个解码模块Fdec，它由一个神经网络组件组成。的输入向量由连接三个向量形成：这里，表示基于地址从存储矩阵中读取的堆叠向量信息，其中操作符表示存储矩阵的读取操作。辅助解码模块的辅助信息是嵌入向量，以及N，表示计数器中记录的当前项目数。显然，读取操作（）的设计，也称为读头，在元草图的性能中起着至关重要的作用。存储操作通过将传入项目馈送到FE和FSa以获得嵌入向量和地址，然后将加权写入M来执行：。这里，也可以使用其他类型的写入[27]，[33]，[34]，[35]，但简单的加性写入更有效，并且允许并行计算梯度[27]。此外，加性写入还允许定义删除操作，即从M中减去。查询操作估计给定查询项目的频率。首先，像存储操作一样获得和。然后，从M中检索向量，N可以通过一个小计数器轻松获得。最后，将，和N一起输入以获得查询项目的估计频率作为返回值。两个操作如图1所示。![]()
C. 读头
接下来，我们详细介绍了为元草图特别设计的几种类型的读头。基本读头：基本读头采用了记忆增强网络领域中常用的读取方法，如下所示本质上，元草图模拟了传统草图的多哈希函数设置（即，个哈希函数），并以与写入的嵌入向量相同长度的信息从M中读取。计数最小读头：基本读头简单高效。然而，由于其他数据项的堆叠在中造成大量高值位，它读取的信息是初步和不均匀的。尽管解码模块可以轻易利用这些高值位上的信息，但它们也包含冲突信息，这会干扰当前数据项频率信息的恢复。同时，解码模块可能会忽略可能对当前数据项至关重要的低值位上的信息，这些信息可能被忽略。因此，我们需要设计辅助读头，以提供有助于解码模块的信息增益。在本文中，我们探索了两种优化形式的，受到CM草图的“计数最小”机制的启发。“计数最小”机制选择CM草图读取的多个近似计数值中的最小值，以减少哈希冲突引起的误差。这种机制暗示了与辅助读头目标一致的读出信息的进一步细化。遵循机制的直觉，我们实现了两种类型的读头。第一种计算中每一行的最小值，旨在突出低值位上的信息。这里，表示的归一化形式，表示哈达玛德积。需要广播，并且平滑零值以符合操作。第二个读头从中减去一个阈值（例如，中所有位的最小值），然后按照第一个读头的相同程序进行。实际上，第二个读头旨在消除低值位上信息冲突引起的噪声，这可能导致训练不稳定。在我们的论文中，通过两种读头的协作实现了最优性能，我们将在第VI-B节中提供详细分析。总的来说，元草图的读头设计是多样化的，并且仍然是一个开放的问题。在设计读头时，我们需要根据特定的流应用考虑一个自然的权衡：增加读头的数量可以在一定程度上提高解码性能，但也可能导致读取速率变慢。III. 元草图训练
A. 训练框架
元草图采用了高效的一次性元训练方法。训练过程包括两个阶段，预训练和适应阶段。两个训练阶段都在线下进行，完成后，元草图可以在线直接部署和使用，而不需要任何训练开销。在预训练阶段，元草图学习一组初始模块参数，包括，，和。预训练在训练单元上进行，即基础元任务，以获得流频率估计的能力。然后，在适应阶段，预训练的元草图快速适应一组轻量级训练单元，即自适应元任务，以快速获得特定于任务的知识，即在运行时草拟真实数据流的参数。训练单元，即元任务，对于两个阶段至关重要。元草图在单个元任务上的训练过程相当于模拟存储和查询数据流实例，同时计算误差以优化可学习参数。因此，元任务由存储集（也称为支持集）和查询集组成。存储集可以被视为数据流的一个实例，，其中是流项目的数量。查询集可以由一组在中具有配对频率的项目表示，正式地，，其中是中不同项目的数量。在本文中，我们定义了两种类型的元任务，基础和自适应元任务，分别对应预训练和适应阶段。![]()
这两个阶段，基于不同类型的元任务，遵循相同的训练框架，如图2所示，除了采样器和初始参数。为了优化减少绝对误差和相对误差，即AAE = ；ARE = ，我们为元草图设计了一个自适应混合损失函数：这里，和是学习参数，和分别是项目的真实和估计频率。B. 基础元任务生成
在预训练阶段，基础元任务应该使元草图模拟传统草图并保持一定的通用性，而不是过多依赖特定分布的模式。因此，我们根据Zipf分布生成元任务，这在真实数据流场景中普遍存在。元任务本质上是一个具有项目大小的数据流实例，可以通过总项目数和相对频率分布来确定。我们可以通过预设不同的，和来生成元任务，其中是频率均值，因为。因此，基础元任务的生成基于采样器。注意，元任务是为了让元草图学习草图能力，而不是机械地记忆的参数。这意味着训练有素的元草图具有处理未覆盖的案例的泛化能力。在我们的实现中，是从真实数据集中构建的，该数据集从数据流中划分而来，如下所示。项目池是项目域的一个子集。如果项目域是预先知道的，它可以直接作为项目池。否则，如果项目域只是部分知道甚至未知，项目池可以通过从中收集项目来构建。即使项目池没有完全覆盖项目域，由于领域特定嵌入空间的均匀性，所谓的“缺失”项目仍然可以被识别，前提是不同项目的数量少于项目池容量。频率均值范围是频率均值的范围。我们计算的真实频率均值（表示为），并设置，其中是一个常数。分布池由许多根据相对频率分布的不同参数生成的实例组成。在本文中，我们考虑一系列具有不同参数的Zipf分布，作为构建的基础。可以从广泛的范围中选择，以很好地覆盖不同的分布。然后，可以根据采样器生成，如下所示。我们首先从中随机抽取个项目的一个子集，并抽取一个频率均值。注意的范围是，其中是我们设置的最大采样项目大小。然后，我们抽取一个分布实例，并使个项目的频率符合和。例如，个项目的频率可以设置为，其中是一个随机变量。上述步骤重复进行，直到构建了存储集和查询集。基础元任务的生成是完全自动化和自监督的，不需要真实数据存储。因此，基础元任务的存储可以动态分配和释放，节省训练资源。C. 自适应元任务生成
在处理真实数据流时，我们可以通过从训练数据集中在线采样来获得项目集及其分布。和然后用于生成自适应元任务集。对于每个自适应元任务，从中抽取一个项目子集，并且从中抽取与每个项目相对应的相对频率。该过程与基础元任务的生成类似。与基础元任务生成的唯一区别是不再有分布池，因为真实流分布是唯一的。此外，我们有意随机化项目与其原始数据记录上的相对频率之间的对应关系。这相当于构建了项目频率动态变化的元任务。例如，一个项目的频率可能首先增加，然后突然下降。通过自适应元任务，元草图学会了快速适应，同时对项目频率变化保持灵活性。自适应元任务是利用少量真实数据生成的，只需要少量临时存储。同时，由于适应训练涉及快速微调，生成的自适应元任务数量仍然相对有限，消耗的训练资源很少。生成基础/自适应元任务的详细算法如图3和图4所示。![]()
![]()
IV. 元草图的扩展
元草图为总结流数据提供了一个通用框架，因此在支持不同类型的数据流方面具有多样性。在本节中，我们研究了元草图在处理多媒体和图流数据场景中的两个扩展，分别在第IV-A节和第IV-B节中讨论，超越了处理传统数据流的频率估计。特别是，我们研究了这些元草图扩展是如何通过元任务的可定制性来实现的。A. 多媒体流场景
多媒体数据的体积，如文件、图像和视频，呈指数级增长，并在我们的日常生活中变得无处不在。这些数据通常以流的形式连续到达，对实时总结提出了挑战。例如，互联网上庞大的视频数据以帧为单位传输，使得在不同视频源上执行实时帧计数变得困难，特别是在存储有限的设备上。在另一个分布式NoSQL数据库的例子中，监测文件流中键值对的频率非常重要，这些文件流存储在SSTables中，并在数据同步期间传输。为了克服这一挑战，已经开发了用于多媒体流频率查询的草图技术，为后续的挖掘和分析提供了基础。接下来，我们研究元草图如何扩展到多媒体流场景。在典型的记忆增强网络配置中，数据项是嵌入模块的直接输入，生成封装特定领域特征的嵌入向量，从而促进项目差异化。然而，当应用程序中的数据项包含复杂的多媒体数据时，简化变得必要。直接使用原始多媒体数据项将给元草图带来大量的训练和执行开销，因为嵌入模块可能需要额外的参数来处理多媒体数据。另一方面，某些多媒体数据类型（如视频帧）的表示仍然是一个挑战，可能导致嵌入模块难以收敛，最终导致训练失败。解决上述问题的一个实用方法是为每个多媒体数据项分配一个唯一的数字ID，类似于传统草图所采用的方法。因此，一个基本问题出现了，即元草图是否可以在不依赖数据项的原始信息的情况下保持其核心性能。我们对嵌入模块（在第VI节中讨论）的深入检查揭示了其主要关注点在于利用数据流的频率分布的偏斜性，而不是数据项的内在特征。不同数据项的特征仅作为区分它们的一种方式。这意味着在元草图中使用随机标识符ID和数据项本身之间几乎没有区别，尽管在标识符ID案例中有一些可接受的信息损失。因此，我们为每个多媒体数据项分配一个唯一的数字ID，并使用其二进制编码作为元草图嵌入模块的输入。自然地，可以使用任何类型的编码方法在原始数据项和数字标识符之间建立一一映射。在开发了多媒体数据的统一二进制编码方案后，元草图的训练和部署变得更加方便和通用，如图3所示。本质上，我们只预训练一次基本元草图，并多次部署它（即，将其复制到不同的应用中）。具体来说，我们可以使用固定的编码方法构建基础元任务，并训练一个通用的基本元草图。对于各种多媒体流，我们只需要使用相同的编码方法处理数据项，然后直接部署训练有素的基本元草图进行处理或自适应训练。![]()
假设我们在预训练阶段使用24位二进制编码，并表示所有可能的ID集合为。为了支持不同的流应用，建议在基本元草图训练中使用更大的进行二进制编码，这允许在处理数据流中不同项目数量时具有灵活性。此外，为了促进嵌入模块在上的鲁棒泛化性能，训练基本元草图的项目池（即，包含在中的项目）应该在位二进制编码空间中广泛且分散地采样。因此，当将训练有素的基本元草图部署到特定的流应用中时，唯一的要求是获得的子集，作为该特定应用中数据流项目的编码集。之后，元草图可以直接部署以处理数据流。在本文中，我们提出了关于构建的策略的见解：我们的策略是确保中的二进制ID在位0/1编码空间内尽可能均匀分布。通过实现这一点，输入到嵌入模块的项目集将展现出多样化的特征，这反过来又促进了嵌入模块更有效地区分数据项。因此，构建的优化目标如下：我们的目标是最小化中所有二进制ID的每个位位置的期望值的方差（表示为），这可以使用各种贪婪优化算法进行近似。在本文中，我们并不刻意最小化，而是采用简单的策略，从中顺序采样，并执行线性缩放的编码，通过模乘法。B. 图流场景
数据的快速增长在各个领域带来了重大挑战，其中动态图流数据占据了大数据的很大一部分。这些图流数据描述了图的连续演变，其中边缘及其相关权重随时间顺序更新，例如社交网络图中不断变化的用户关系（权重表示关系密切程度）或通信网络图中的快速信息交换（权重表示信息优先级）。在实际应用中，对图流进行实时处理，使我们能够响应各种图查询，例如边缘的存在或权重。例如，总结基于社交网络的图流数据使我们能够确定给定时间用户之间关系的存在和密切程度，为进一步的图挖掘提供了基础。图流的概念可以正式定义如下。定义1（图流）：设是一个具有顶点集和边集的图。中的每条边在时间处有一个权重。图流是一系列边更新的序列，其中表示边在时间处权重的变化。实时处理图流数据并非易事，由于其庞大的体积和高度动态的特性，在存储和查询图流数据的空间和时间效率方面提出了巨大挑战。管理图流数据的一个被广泛接受的方法是基于草图的图总结。例如，CM草图可以直接应用于存储图流的边。更先进的TCM通过分别压缩图流的顶点和边来保留近似的图结构信息。GSS通过不断分配辅助存储来增强查询精度，增强了TCM的基础结构。Auxo在GSS的基础上，集成了一个前缀嵌入树，加速了GSS的存储扩展过程，使其更适合于拥有慷慨空间预算的场景。然而，现有的基于哈希的图流显式压缩方法没有充分利用图流的内在模式，如权重的分布信息。此外，在有限的小空间预算场景中，现有结构面临挑战。其中，TCM面临严重的哈希冲突，导致大量查询错误。GSS（Auxo）无法获得外部存储，导致许多项目无法写入/查询，导致无法接受的查询命中率。相比之下，元草图在利用和利用流数据的模式方面特别有效，使其成为草图图流的有前景的解决方案。接下来，我们研究元草图如何扩展以捕捉图流中的深刻模式。特别是，我们研究元草图如何支持图流上的两个基本查询，即边存在查询和边权重查询。边存在查询旨在确定特定边在给定时间是否存在于图中。例如，监测和检测高权重边的存在非常重要，这表明两个节点之间频繁的交互，例如社交网络中两个人之间的交互或财务网络中账户之间的交易。边权重查询旨在准确检索特定边的当前累积权重值，即。为了使元草图框架适应图流，我们首先明确图流的输入格式，并建立训练目标。元草图将图流中的每条边视为基本处理单元，结合了两个顶点和边权重的连接信息。随后，图流的边被顺序写入元草图的存储中。我们的主要训练目标是使解码模块能够根据从存储器中读取的信息输出特定边的相应标签（即，边存在查询）或权重（即，边权重查询）。对于这两个查询任务，一个自然的见解是，边权重查询在解码读取信息时更具挑战性，并且可以为边存在查询提供基础。因此，我们主要训练元草图进行边权重查询，然后对其进行微调以适应边存在查询，提高训练效率并优化压缩信息的使用。对于边权重查询，我们遵循典型的元草图训练，对两个阶段的元任务生成进行更改。基础元任务是使用更接近图流权重分布模式（即，广泛的幂律分布）的分布池生成的。同时，自适应元任务是从真实的图流中生成的，利用权重分布模式，同时考虑边和权重分布之间的动态变化。对于边存在查询，我们在训练用于边权重查询的高级元草图上构建自适应元任务。自适应元任务从图流中采样边，选择存在边或随机构造不存在的边，并分配相应的标签。在自适应训练期间，我们对基本元草图采用新的解码模块，输出二进制标签，并适应二元分类损失。为了提高效率，我们只调整解码模块的参数，冻结其他模块的参数。图4展示了我们在图流场景下的框架，其中图流中顺序更新的边被输入到元草图中，结合了顶点和边权重信息。此外，元草图的训练包括两个阶段。首先，它被训练以获得处理边权重查询的基本能力。其次，它快速适应真实的图流，并扩展到边存在查询。元草图使得图总结的高效处理成为可能，从而促进了复杂图流的实时分析。![]()
V. 实验
A. 设置
数据集：我们使用多个真实世界数据集评估元草图的性能。根据不同场景，我们将这些数据集分类如下：主要数据集：我们使用两个广泛使用的真实数据集进行主要实验和分析实验。Word-query是一个流式搜索查询记录，每个查询包含多个单词（例如，“今日新闻”）。IP-trace由IP数据包组成，每个数据包由唯一的IP地址对标识（例如，192.168.1.1/12.13.41.4）。IP-trace遵循重尾分布，Word-query遵循Zipf分布。这两个数据集中的所有项目都根据其固有信息进行编码，类似于相关工作。多媒体流数据集：我们使用三个流数据集评估元草图在多媒体流场景下的性能：Webdocs、Kosarak和Video-Frames。Webdocs和Kosarak中的每个数据项对应于一个文本/文件对象，而Video-Frames中的每个数据项是视频中的采样帧。这些数据集中的所有项目都被分配了数字ID，随后进行二进制编码。图流数据集：对于图流，我们使用两个常用的数据集Lkml和Enron，它们是社交/通信图，其中节点代表对象，边代表两个节点之间的通信。我们将每个数据集通过时间戳（或对于无时间戳的数据集则随机）分割为训练集和测试集，旨在使两个数据集中的项目数量相似，并且项目重叠最小（例如，分割后的项目重叠率对于Word-query为14%，对于IP-trace为30%）。基线：我们使用多种基线评估基本/高级元草图（MS）。在这里，我们将基础版本的我们的方法，基本MS，与传统草图进行比较。随后，对于我们方法的优化版本，高级元草图，我们将其与增强草图进行比较。值得注意的是，大多数增强草图使用的优化技术与我们的基础/高级MS正交，预示着我们方法在当前比较方式下的未开发优势。对于图流场景，我们选择了专为图流设计的草图作为基线。基础草图：计数最小草图（CMS）、计数草图（CS）和计数最小均值草图（CMM）是其他草图变体的基础，也是最常用的基线。因此，我们选择它们作为基本MS的竞争对手。对于MLSketch，我们基于CM草图和C草图开发了两个版本，MLSketch (CM)和MLSketch (C)。注意，在所有实验中，两个版本都需要从数据集中额外采样以训练回归模型。增强草图：我们将高级MS与基于CM/C草图的各种增强草图进行比较。根据是否使用学习方法，这些最具代表性和最先进的增强草图分为两类。第一类包括学习增强C/CM草图（LCS/LCMS）；第二类包括弹性草图（ES）和冷过滤器（CF）。图流草图：对于图流，最典型和广泛使用的基于草图的总结结构TCM，以及当前最先进的结构Auxo，被用作比较基线。所有基线都遵循其最优默认设置。我们的主要评估指标是频率估计准确性，以绝对平均误差（AAE）和相对平均误差（ARE）衡量，这在神经数据结构中是常见的。我们为分析部分（第VI节）保留了对延迟和吞吐量的深入讨论。参数：我们实现了和为具有2层大小的MLP，分别为128和48，随后进行批量归一化，为具有3层256的MLP，具有残差连接。我们对层连接使用relu函数。空间预算B用于存储M，与神经数据结构中的设置相同。其他模块，如哈希库，通常被接受为可重用和可摊销的资源，用于多次部署草图。在本文中，我们控制以压缩A/M。A/M的详细参数设置显示在我们的GitHub项目网站上。B. 基础元草图
设置：对于每个数据集的，我们在具有四个最大项目大小（即，）的元任务下训练基础元草图：{5 K, 10 K, 20 K, 40 K}。我们设置，因此频率均值范围。元任务采样器具有Zipf分布，我们使用构建分布池。对于基本MS，默认的最大训练步数为500万，学习率为0.0001，使用Adam优化器。我们在上考虑两种类型的任务，Tr和Ts。Tr是通过在两个真实数据流上随机采样直接获得的，具有不同的值，即不同项目的数目。注意，Tr的频率分布不一定遵循Zipf分布。Ts是合成任务，其中频率遵循具有的Zipf分布。为了评估基本MS的泛化和稳定性，Ts(0.5)和Ts(1.5)的分布不受元任务采样器的覆盖。性能：表I显示了所有竞争者在真实数据集Tr上的性能。它表明，基本MS在所有测试案例中都优于传统基础草图，即CMS和CS。例如，在Word-query上的结果显示，当且时，基本MS的ARE为0.74，而CMS和CS的ARE分别为4.90和1.94。从空间预算的角度来看，当预算进一步收紧时（即，从5 K增加到40 K），MS相对于基线的优越性变得更加明显。MS在测试Ts时，对于不同的值也显示出显著的优势，如表II所示。![]()
![]()
我们展示了ARE与空间预算趋势的关系，如图5(a)（Tr，，Word-query）。与传统草图性能急剧下降相比，基本MS保持稳定性能。我们展示了ARE与不同项目数量趋势的关系，如图5(b)（Tr，，Word-query）。与传统草图相比，基本MS的ARE随着值的增加而亚线性增加。此外，MS在紧缩预算下的表现优于基线，随着预算的收紧，其优越性增加。![]()
泛化性：我们测试了元草图对不在元任务采样器范围L内的频率均值（即，）的泛化性，如图6所示（，，Word-query）。实验是通过采样一系列Ts任务完成的，其流长度（即，）在10 K到100 M之间。它表明，随着真实流长度的增加，估计长度线性增加，因此ARE保持稳定。![]()
高频项目：鉴于有限的空间，有效地使用草图识别数据流中的前K个频繁项目（高频项目）至关重要。因此，我们评估了基本MS（）在真实和合成数据集上查询前5%和前10%高频项目的性能，如图7和图8所示。它表明，基本MS显著优于基线，同时在项目大小方面保持良好的稳定性。此外，我们评估了基本MS（，）在不同偏斜度的数据流中查询高频项目的性能，如图9所示。结果表明，基本MS在数据流偏斜度变化时，在ARE方面显示出显著的鲁棒性。![]()
![]()
![]()
C. 高级元草图
设置：自适应元任务的生成与传统元任务类似，只是每个项目池都读取真实频率分布进行适应，如自适应元任务生成部分所述。在适应阶段，最大训练步数为0.002 。性能：表III比较了高级MS与传统草图及其变体LS和CF在评估集Tr上的性能。我们根据[15]实现了两个LS，学习CM草图(LCMS)和学习C草图(LCS)，遵循默认设置，即（前1%和5%）高频项目分别存储。对于CF，我们遵循[14]中的参数设置，并使用CF40、CF70和CF90分别设置过滤器百分比为40%、70%和90%。结果表明，高级MS的性能优于LS和CF。此外，随着不同项目数量n的增加，高级MS的AAE/ARE增长更为温和，与其竞争对手相比。![]()
此外，我们比较了高级MS和LS在动态流场景下的性能，如图10所示。我们选择了一组Tr（n = 5 K，B = 9 KB），并逐渐混合项目和频率之间的对应关系。结果表明，高级MS的平均ARE在IP-trace数据集上仅在1.29到1.35之间轻微波动。相比之下，LCS或LCMS的ARE从2.75以上开始，并随着混合比率的增加而显著增加，达到最大值7.24。LS的分类器容易受到项目频率变化的影响，经常导致更多的哈希冲突，从而降低了估计准确性。![]()
D. 多媒体流场景
设置：我们使用24位二进制编码（编码空间大小为(2^{24})）来处理多媒体数据项，并从该编码空间中均匀采样300万个项目作为Dtrain的项目池。此外，生成元任务和评估任务的设置与之前进行的主要实验一致。在训练基本元草图后，我们将其直接应用于三个数据集，并根据VIi的优化目标获得三个二进制ID子集。性能：表IV和表V分别展示了基本元草图在真实评估任务（Tr）和合成评估任务（Ts）上的性能。结果表明，元草图仍然具有显著优势，从而验证了我们之前的分析。同时，表VI显示了在适应训练基本元草图后，高级元草图的性能与直接输入数据项的设置保持一致。接下来，我们评估了元草图的性能与具有不同方差VIi的二进制ID集之间的关系，在Kosarak数据集上进行了评估。图11（B = 11 KB）表明，基本和高级元草图的性能随着VIi的增加而逐渐下降，这验证了我们优化目标的合理性。![]()
![]()
![]()
E. 图流场景
设置：对于边权重查询，我们选择了广泛的幂律分布来构建基础元任务，而自适应元任务是从Dtrain的真实边权重分布中采样的。我们为元草图选择了两个较大的预算（60 KB和120 KB）以与TCM的设置保持一致，因为TCM在较小预算下的性能急剧下降。其余训练设置与之前的基础实验相似。对于评估任务，我们直接从Dtest中采样了不同长度的真实图流。对于边存在查询，我们在Dtrain上以1:1的比例构建自适应元任务，选择存在或随机构造不存在的边，并分配相应的标签。在自适应训练期间，我们对基本元草图采用了新的解码模块，输出二进制标签，并适应二元分类损失。为了提高效率，我们只调整解码模块的参数，冻结其他模块的参数。性能：表VII显示了边权重查询的结果。基本和高级元草图都优于TCM，展示了元草图在处理广泛流数据方面的潜力。图12（B = 60 KB）展示了边存在查询的结果，我们选择二进制分类准确率作为指标。我们观察到，随着边大小的增加，元草图的性能逐渐超过TCM。更重要的是，元草图在确定高权重边的存在方面具有显著优势，因为它利用了权重分布信息。相比之下，TCM未能利用权重分布模式，导致在三个评估任务中表现均匀较差。![]()
![]()
我们进一步比较了元草图与另一个最新技术Auxo的性能。我们发现，在紧张的空间预算约束下，Auxo在查询中出现了大量遗漏命中，经常无法检索到图流中大量低权重查询边的结果。为了进行有意义的比较，我们转而关注重边查询，这是边查询的一个变体，强调高权重边，这在流应用中具有重要意义。![]()
我们从两个原始数据集中识别出前5%和前10%的重边作为真值。对于每个重边，我们从基本MS、TCM和Auxo（B = 60 KB）中获取其权重，并与真值进行比较。在Lkml和Enron数据集上的结果显示，基本MS的性能通常优于TCM和Auxo，特别是在紧张的预算下。VI. 分析
元草图是基于由不同流分布组成的元任务进行训练的。我们期望元草图能够学习草图能力。然而，元草图的能力受到给定元任务模式的限制是不可避免的。为了解决这个限制并实现权衡，我们采用了两阶段训练过程。在预训练阶段，我们选择了最具代表性的Zipf分布来形成基础元任务，使基本元草图能够适应广泛的数据流。在适应阶段，我们从原始数据流中采样自适应元任务，使高级元草图更加专业化。接下来，我们分析了元草图模块的工作机制以及它们在获得这两种能力中的作用。同时，我们评估了三个读头的功能，并通过两个案例研究展示了元草图的自我优化能力。A. 模块
稀疏寻址：我们以A矩阵的2D切片（大小为）为例，分析了精炼向量通过此模块获得寻址的过程。由于是由堆叠单位向量形成的，我们有：这里，是应用于的逐元素变换函数，在我们的论文中。根据Sparsegen的原则，主要影响向量的稀疏性（即，向量中非零位的比例），而决定了非稀疏位的位置和值。图14显示了训练过程中平均和的稀疏性之间的强相关性（n = 5 K，B = 9 KB，Word-query，基础MS）。由于嵌入向量不直接参与寻址过程，平均保持稳定。进一步，我们观察到的稀疏性最终收敛到大约1，这意味着每个项目通常存储在一个与精炼向量和中具有最大余弦相似度的单位向量相对应的插槽中。![]()
因此，的作用是将精炼向量映射到寻址向量。中的个单位向量是映射的参考标准，相当于精炼向量空间的个互斥划分。基于此，我们构建了两个与大小相同的矩阵和。中的个单位向量来自采样精炼向量的聚类中心。为了实现互斥划分，我们执行了具有和余弦相似性标准的K均值聚类。然后，我们归一化得到的个聚类中心，并将它们堆叠为。相比之下，中的单位向量是随机生成的。图15(a)显示了在训练有素的元草图中用/替换的结果。使用的元草图表现最差，但使用的元草图性能接近原始的。此外，我们统计了、、的每个插槽中映射的项目数，并在图15(b)中展示了它们的标准差。的标准差远高于和，一个更好的元草图倾向于将项目更均匀地存储在每个插槽中。因此，寻址模块模拟了传统草图的机制。它的功能是将项目嵌入向量尽可能均匀地存储在多个存储槽中，且一个项目只写入一个插槽。![]()
嵌入：元草图中的主要冲突来源是不同的嵌入向量在单个插槽中的堆叠。因此，嵌入向量的稀疏性成为决定冲突程度的重要指标。图17显示了嵌入向量的稀疏性与流分布之间的关系（n = 5K，B = 9KB，Word-query，高级MS）。我们选择了在不同偏斜水平下的Zipf、三角形和均匀分布的元任务。结果表明，嵌入向量的稀疏性与分布的偏斜性成正比。![]()
因此，我们推测元草图通过自我调整嵌入向量的稀疏性来记忆正在适应的分布的模式信息。解码：解码模块作为元草图中最深的神经网络，整合了各种信息来预测项目频率，并实现了泛化能力。为了验证这一点，我们获得了两个特殊自适应元任务的高级MS。第一个元任务是从真实数据流中采样的，但具有固定的项目大小（5000），而第二个元任务使用固定的实际频率均值。这样的元任务迫使元草图更多地关注固定模式（即，项目大小和频率均值），从而破坏了其泛化能力，使我们能够进行比较实验，观察解码模块的能力。因此，我们训练了带（或不带）冻结解码模块参数的高级MS，基于上述元任务。图16(a)显示了两个模型在不同项目大小的任务（Tr）上的性能变化。可以观察到，没有冻结解码模块的元草图失去了对项目大小的泛化能力。相比之下，冻结解码模块的元草图保持了其泛化能力，并在除了项目大小为5000的任务之外的其他任务中取得了最佳性能，其中未冻结解码模块的元草图过度拟合。类似地，如图16(b)所示，没有冻结解码模块的元草图在频率均值方面也失去了一定的泛化能力。![]()
B. 读头
我们进行了实验（n = 5 K，B = 9 KB，基础MS），以展示不同读头的影响。首先，我们检查了读头组合对训练稳定性的影响，基于三个读头：基本读头（简称BC）和两个计数最小读头（简称CM1和CM2）。图18表明，只有BC+CM1的组合在训练期间导致大的波动，可能导致训练失败。我们推测CM1在带来信息增益的同时放大了低值位的噪声，影响了训练稳定性。相反，CM2进一步去除了低值位上的噪声，因此BC+CM2和BC+CM1+CM2的组合展现了相对稳定的训练性能。此外，我们评估了确保稳定训练的读头组合在评估任务中的性能。图19表明，BC+CM1+CM2的组合实现了最佳性能，表明了信息增益（即CM1）和噪声降低（即CM2）之间的平衡。![]()
![]()
C. MLSketch案例研究
由于MLSketch早期采用学习技术来优化草图，我们从多个方面阐明了元草图相对于它的优势：1）元草图是一个新型的基础草图，具有更优越的数据压缩和自我优化能力。然而，MLSketch作为辅助工具，依赖于基础草图，保持了其基本的草图结构。2）基于元学习的元草图充分利用了广泛的长期分布模式，提供了对分布变化的稳定性，无需频繁重新训练。相比之下，MLSketch依赖于频繁的在线采样来获取短期分布模式。3）元草图适应于各种数据流应用，而MLSketch专为网络测量量身定制。图20(a)表明，在分布漂移的场景中（n = 5 K，B = 9 KB），“一次性训练”的MLSketch相较于“频繁采样和训练”的MLSketch，其性能出现了下降。相反，我们的基础元草图只需一次训练就能有效地应对这些变化。![]()
此外，作为基础草图的元草图也可以从MLSketch的辅助优化中受益，从而提高其在管理具有复杂偏斜模式的流中的精度。例如，元草图（n = 5 K，B = 9 KB）可以最初在α ∈ [0.8, 1.3]的Zipf分布上进行训练。然后，它可以在较窄的α范围[0.5, 1.0]和[1.0, 1.5]上进行微调，创建两个不同的解码模块，以更好地预测这些范围内的频率。遵循MLSketch的方法，可以采样真实流来训练回归模型，结合多个解码模块，根据当前流的偏斜性进行准确预测。如图20(b)所示，对于在每个时间步T内随机在α ∈ [0.5, 1.5]的Zipf分布范围内变化的测试流，MLSketch增强的元草图（MLSketch (基础MS)）的表现优于仅训练一次的元草图。D. （学习）增强草图案例研究
（学习）增强草图利用（相对）稳定的项目和频率之间的对应关系来过滤高频项目（称为稳定情况）。通过进一步优化，适应自适应元任务的高级元草图学会了处理项目和频率之间的动态对应关系。实际上，稳定情况自然包含在高级元草图的范围内，我们并没有刻意优化它。为了理解元草图的自我优化机制，我们可以设计匹配稳定情况的元任务并进行自适应训练，以观察性能的变化。同时，我们对元草图的寻址模块是否会像增强草图那样差异化处理高/低频项目感兴趣。因此，元任务是从具有固定项目大小和真实频率均值的真实流中采样的。同时，我们没有改变项目和频率之间的对应关系。对于自适应训练（n = 5 K，B = 9 KB，Word-query，高级MS），我们固定了嵌入/解码模块的参数，使得高级元草图（称为稳定元草图）只专注于调整寻址能力。图21显示了稳定元草图在不同项目大小的测试任务（Tr）上的性能变化。由于场景更简单且利用了更多的频率-项目对应关系信息，稳定元草图表现出比普通高级元草图更好的性能并不奇怪。![]()
接下来，我们分析了在存储矩阵M的2D切片中多个插槽中高/低频项目的存储情况。在图22中，我们使用密度热图来直观显示低90%频率项目在存储插槽中的堆叠程度，由于这些项目数量较多，其堆叠现象相对稳定，使得观察更为直观。这里，热图的x轴表示插槽的索引，而y轴显示不同项目在插槽中的堆叠程度，用[0, 1]中的值表示（0表示严重堆叠，而1表示相反）。结果表明，在稳定情况下的元草图可以将低频项目集中存储在某些插槽中，以避免与高频项目冲突。有趣的是，元草图并没有像（学习）增强草图那样有意为之。相反，这是通过其在训练期间的自我优化实现的。![]()
E. 延迟和吞吐量
我们评估了MS（n = 40 K，B = 9 KB，Word-query）的写入/查询吞吐量和延迟。作为比较基线，我们选择了两个基础草图，CS和CMS，因为它们作为其他草图变体的基础结构，在延迟和吞吐量方面具有显著优势。如表VIII所示，MS在CPU上的吞吐量与CMS和CS保持了相似的水平。此外，由于MS的简单并行代数操作在GPU上得到了显著加速，存储和查询操作的吞吐量分别比CPU提高了14.9倍和29.5倍。因此，MS有望利用GPU/TPU在流应用中的日益普及趋势，其中输入要么是短暂的，要么以高吞吐量交付。![]()
在延迟方面，与其他神经数据结构类似，MS由于其相对复杂的结构和计算过程，导致其串行执行延迟高于CMS和CS。然而，由于MS的网络模块规模紧凑，主要由2到3层的小网络组成，MS能够将单个写入和查询操作的延迟保持在1毫秒以下，这对于流应用来说是足够的。此外，在实际场景中，单个项目的串行写入/查询通常是不经济的，因此通常会建立一个小缓冲区，当缓冲区满时，项目被一次性传输到草图中。这种设置允许MS利用并行写入/查询，从而实现平均延迟的近线性降低，如图23所示。它表明，随着缓冲区大小的增加，MS的平均延迟呈线性降低趋势，而传统基线则几乎没有好处。![]()
VII. 结论
在本文中，我们提出了一种作为基础草图的神经数据结构——元草图，用于估计数据流中的项目频率。元草图利用元学习和记忆增强神经网络来增强草图性能。元草图通过Zipf分布进行预训练，并且可以快速适应特定的运行时流。为了实现这一点，我们设计了基础和自适应元任务的生成，分别对应预训练和适应阶段。我们还研究了元草图在支持多媒体和图流方面的扩展。在真实数据集上进行了广泛的实证研究，以评估我们的提议。声明
本文内容为论文学习收获分享，受限于知识能力，本文对原文的理解可能存在偏差，最终内容以原论文为准。本文信息旨在传播和学术交流，其内容由作者负责，不代表本号观点。文中作品文字、图片等如涉及内容、版权和其他问题，请及时与我们联系，我们将在第一时间回复并处理。你是否有这样的苦恼：自己辛苦的论文工作，几乎没有任何的引用。为什么会这样？主要是自己的工作没有被更多的人了解。
计算机书童为各位推广自己的论文搭建一个平台，让更多的人了解自己的工作，同时促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 计算机书童 鼓励高校实验室或个人，在我们的平台上分享自己论文的介绍、解读等。
稿件基本要求：
• 文章确系个人论文的解读，未曾在公众号平台标记原创发表，
• 稿件建议以 markdown 格式撰写，文中配图要求图片清晰，无版权问题
投稿通道：
• 添加小编微信协商投稿事宜，备注：姓名-投稿
![]()
△长按添加 PaperEveryday 小编
