分析数据流中子立方体重要元素的算法及应用

17050在分析数据流中找到子立方体重要元素0Branislav Kveton �0Adobe Researchkveton@adobe.com0S. MuthukrishnanRutgers Universitymuthu@cs.rutgers.edu0Hoa T. Vu †0University of Massachusettshvu@cs.umass.edu0Yikun Xian RutgersUniversitysiriusxyk@gmail.com0摘要0现代数据流通常具有高维度。例如，数字分析流包括用户在线活动（例如，网络浏览活动，商业网站活动，应用程序和社交行为以及对广告的反应）。一个重要的问题是找到子维度的频繁联合值（重要元素）。形式上，数据流由d维项目和k维子立方体T的子集组成，其中T是k个不同坐标的子集。给定阈值γ，子立方体重要元素查询Query(T,v)如果f_{T}(v)≥γ，则输出YES，如果f_{T}(v)<γ/4，则输出NO，其中f_{T}是具有联合值v的坐标T的流项目数量的比率。所有子立方体重要元素查询AllQuery(T)输出所有返回YES给Query(T,v)的联合值v。问题是正确回答所有T和v的这些查询。我们提出了一个简单的一次遍历抽样算法来解决子立方体重要元素问题，其空间复杂度为˜O(kd/γ)。˜O(∙)抑制了多对数因子。根据Liberty等人的下界，这是最优的，除了多对数因子。在最坏的情况下，这个界限变为Θ(d^2/γ)，对于大的d来说是禁止的。我们的主要贡献是通过基于模型的方法来避免这个二次瓶颈。特别地，我们假设维度之间通过朴素贝叶斯模型相关。我们为我们的问题提出了一个新的两次遍历，˜O(d/γ)空间算法，并提供了一个快速算法来回答AllQuery(T)，其时间复杂度为˜O((k/γ)^2)。我们在合成数据集以及来自Adobe和Yandex的真实数据集上展示了我们方法的有效性。我们的工作展示了基于模型的方法在数据流中的潜力。0关键词0算法，数据流，重要元素，图模型0ACM参考格式：Branislav Kveton，S. Muthukrishnan，Hoa T. Vu和YikunXian。2018年。在分析数据流中找到子立方体重要元素。在WWW2018：2018年Web会议上，2018年4月23日至27日，法国里昂。ACM，美国纽约，10页。https://doi.org/10.1145/3178876.31860820�作者按字母顺序排列。†本工作的一部分是在AdobeResearch完成的。0本文根据知识共享署名4.0国际（CC BY4.0）许可发布。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW 2018，2018年4月23日至27日，法国里昂。©2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.318608201 引言0我们研究在高维数据流中找到重要元素的问题。大多数公司在时间上与销售的物品、时间、商店位置、价格等进行交易。现代在线公司看到用户网络活动的流，通常包括用户信息的组成部分，包括ID（例如，cookie），硬件（例如，设备），软件（例如，浏览器，操作系统）以及网站属性，应用程序。活动流还包括事件（例如，展示，查看，点击，购买）和事件属性（例如，产品ID，价格，地理位置，时间）。即使经典的IP流也具有许多维度，包括源IP地址、目标IP地址、端口号和IP连接的其他特征，例如应用程序类型。此外，在自然语言处理等应用中，文档流可以被视为大量的单词组合（bigrams或multi-grams）的流[8]。正如这些例子所示，许多应用中都存在具有数百或数千个维度的分析数据流。在此背景下，我们研究了在数据流中找到重要元素的问题，重点是参数d，即维度的数量。在实践中，给定d，d^2的空间使用是禁止的，无法解决此类流的重要元素问题。形式上，让我们从一维项目x_{1},...,x_{m}的流开始，其中每个x_{i}∈[n]:={1,2,...,n}。我们可以查看计数c(v)=|{i:x_{i}=v}|或频率比率f(v)=c(v)/m。重要元素值v是满足c(v)≥γm或等价地f(v)≥γ的值，其中γ是某个常数。标准的数据流模型是我们维护大小为polylog(m,n)的数据结构，并确定v是否是重要元素的成功概率至少为3/4，即如果f(v)≥γ，则输出YES，如果f(v)<γ/4，则输出NO。我们注意到，如果γ/4≤f(v)<γ，则任何答案都可以接受。在网络、数据库、数据挖掘、信号分析等领域，检测数据流中的重要元素是一个基本问题。有关早期调查，请参阅[4]，有关最近调查，请参阅[19]。0子立方体重要元素问题。我们关注的是现代数据流，例如在分析案例中，具有d个维度，对于大的d。数据流由d维项目x_{1},...,x_{m}组成。01间隙常数4可以任意缩小，成功概率可以放大到1-δ，我们在讨论中省略了这些因素。0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, France.17060特别地，0x_{i}=(x_{i,1},...,x_{i,d})，其中每个x_{i,j}0一个k维子立方体T是k个不同坐标{T1,...,Tk}�[d]的子集。我们将xi的坐标T的联合值xi,T称为xi的联合值。具有联合值v的坐标T的项的数量用cT(v)表示，即cT(v)=|{i:xi,T=v}|。最后，我们使用XT来表示随机项的坐标T的联合值的随机变量。我们有以下关系0f_{T}(v):=Pr[X_{T}=v]=c_{T}(v)0对于单个坐标i，我们稍微滥用符号，通过f_i和f_{i}可以互换使用。例如，f_{T_i}(v)与f_{T_{i}}(v)是相同的。同样，X_i与X_{i}是相同的。我们现在准备定义我们的问题。它们以k，γ作为参数，以流作为输入，并构建数据结构来回答：•子立方体重要元素：查询(T，v)，其中|T|=k，且v∈[n]^{k}，如果f_{T}(v)≥γ，则返回一个估计值。具体而言，如果f_{T}(v)≥γ，则输出YES，如果f_{T}(v)<γ/4，则输出NO。如果γ/4≤f_{T}(v)<γ，则任何输出都可以接受。所有k维子立方体T和v∈[n]^{k}的所需成功概率至少为3/4。•所有子立方体重要元素：AllQuery(T)输出所有返回YES给Query(T，v)的联合值v。这取决于用于Query(T，v)的算法。强调的重点是，在算法接收任何查询之前，流以单次遍历或常数次遍历的方式呈现给算法。子立方体重要元素在任何一维重要元素已经应用的地方都是相关的：源和目标IP地址的组合形成了检测网络攻击的子立方体重要元素；商店、销售季度和产品性质的组合形成了可能是数据中感兴趣的模式的子立方体重要元素等。鉴于多维度在数字分析中的无处不在，可以说，子立方体重要元素比单一维度的视图更好地描述了重要的数据属性。0相关工作。我们所解决的问题与数据挖掘社区中研究的频繁项集挖掘直接相关。在频繁项集挖掘中，每个维度是二进制的（n =2），我们考虑的是Query(T, v)，其中v = (1,...,1) :=U^k。已知计算具有频繁项集的所有最大子立方体T，即f_T(U^k) ≥γ，是#P-完全问题[21]。此外，找到一个最大尺寸的T，使得f_T(U^k) ≥ γ，是NP困难问题[9,13]。最近，Liberty等人证明了回答Query(T,U^k)的任何常数次通过流算法需要Ω(kd/γ ∙log(d/k))的内存[13]。在最坏情况下，对于大的k，这是Ω(d^2/γ)，忽略多项式对数因子。对于这个特定的问题，采样算法将几乎满足它们的空间下界。我们的问题更一般，具有任意的n和v。0我们的贡献。显然，当 k = 1 时，可以通过在每个 d维度上构建许多已知的单维度数据结构来解决重要项问题；当 k = d时，可以将其视为一个巨大的单维度问题0将所有值在[n]^k的空间线性化；对于其他k，子立方体T有�d^k�个不同的选择，可以将其视为单独的一维问题，通过线性化每个子立方体。一般来说，这需要�d^k�和log(n^d)的空间或时间复杂度，相对于一维情况，我们希望避免这种情况。此外，我们的问题可以通过使用n位的一元编码来将其约化为二进制情况，并解决频繁项集挖掘问题：查询然后具有kn个维度。得到的界限将有一个额外的n因子，这是很大的。首先，我们观察到蓄水池采样方法[18]比上述方法更高效地解决子立方体重要项问题。我们的分析表明，我们使用的空间在二进制维度和查询向量U^k的下界[13]的多项式对数因子内。因此，子立方体重要项问题可以使用˜O(kd/γ)的空间解决。然而，这在最坏情况下是Ω(d^2)。我们的主要贡献是避免找到子立方体重要项的这种二次瓶颈。我们采用了一个假设，即数据背后存在一个概率模型，并且在朴素贝叶斯模型的精神下，我们假设在观测到的潜在维度给定的情况下，维度之间几乎（不完全）相互独立。这可以被认为是维度的低秩分解。特别地，可以通过限制数据的联合分布与从朴素贝叶斯公式导出的分布之间的总变差距离来形式化这个假设。这个假设在统计数据分析中很常见，在机器学习中非常普遍。根据这种建模，我们做出了两个主要贡献：0• 我们提出了一个两次通过的、˜O(d/γ)空间流算法来回答Query(T,v)。这将空间复杂度从采样中的kd因子改进到仅为d，假设朴素贝叶斯，这使得该算法对于大的k是可行的。我们的算法在每个维度中使用草图来检测重要项，并且需要第二次通过来精确估计它们的频率。•我们提出了一个快速算法来回答AllQuery(T)在˜O((k/γ)2)时间内。通过考虑每个维度中重要项的笛卡尔积，朴素的方法将需要指数时间Ω((1/γ)k)。相反，我们的方法利用朴素贝叶斯假设的结构，逐个维度地构建子立方体重要项。0我们的工作发展了基于模型的数据流分析方向。基于模型的数据分析在其他领域已经取得了成效。例如，在压缩感知中，包括信号系数的值和位置之间的依赖关系的现实信号模型改进了无约束情况[7]。在统计学中，使用树约束模型的多维数据有时会改进点估计和密度估计。在高维分布测试中，也研究了基于模型的方法来克服维度灾难[6]。在数据流模型中，[2, 3, 10]研究了独立性测试问题。McGregor和Vu[15]研究了评估贝叶斯网络的问题。在另一项工作中，Kveton等人[11]假设了一个树形图模型，并设计了一个一次通过的算法来估计联合频率；然而，他们的工作只解决了k =d的情况。我们的模型有些不同，更重要的是，我们解决了子立方体重要项问题（解决了所有的�d^k�个子立方体），而之前的工作没有解决。在遵循这样的方向时，我们已经将基本的重要项问题扩展到了更高维的数据。鉴于我们使用的草图已经存在许多实现作为一维重要项的黑盒子，因此我们的算法很容易实现。0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, FrancePr [X1 = x1,. . . ,X= x ,Y = y].(1).17070Pr[X1 = x1,...,Xd = xd, Y = y]0朴素贝叶斯模型及其在我们的上下文中的应用背景。朴素贝叶斯模型[17]是一个包含 d 个特征 X1,...,Xd 和一个类变量 Y的贝叶斯网络。该模型表示了以下形式的联合概率分布：0= Pr[Y = y]0j = 1 Pr[Xj = xj | Y = y],0这意味着在给定类变量的值的情况下，特征的值是条件独立的。朴素贝叶斯模型的简单性使其成为文本处理和信息检索中的流行选择[12,14]，在垃圾邮件过滤[1]、文本分类[12]等方面具有最先进的性能。0实证研究。我们对子立方体重要项进行了详细的实验研究。我们使用一个合成数据集，其中生成符合朴素贝叶斯模型的数据。然后，我们使用来自Yandex（搜索）和Adobe（营销云）的真实数据集进行实验，这些数据集提供了多维分析流。我们使用基于蓄水池采样的算法作为没有建模假设的基准，并且使用改进了该算法的两次通过子立方体重要项算法来处理满足模型的数据。我们还采用我们的方法来提供一个更简单的一次通过算法，其理论保证较弱。我们的实验结果显示，与基准算法相比，基于模型的算法在合成数据集和真实数据集上都有显着的改进，并进一步展示了第二次通过的好处。02 采样算法0在本节中，我们展示了与独立运行每个 k维子立方体的一维重要项算法相比，采样方法可以高效地解决问题。它还与[13]中的下界相匹配，多项式对数因子。0算法细节。算法使用蓄水池采样[18]从流中随机采样m' =˜O(γ^(-1kd))个项目z1,...,zm'。令S ={z1,...,zm'}为样本集。给定Query(T,v)，当且仅当v的样本频率，记为ˆf_T(v)，至少为γ/2时，我们输出YES。具体地说，0ˆ f T ( v ) := |{ x i : x i ∈ S and x i ,T = v }|0m'。0对于所有子立方体 T 和 T 的联合值 v，期望的样本频率 ˆ f T ( v )等于 f T ( v )。直观地说，如果 v 是频繁的联合值，则其样本频率 ˆ fT ( v ) ≈ f T ( v)；否则，ˆ f T ( v ) 保持较小。0让我们固定一个k维子立方体T，并假设对于所有的v∈[n]k，我们有0ˆfT(v)=fT(v)±max{γ,fT(v)}0很容易看出，如果fT(v)<γ/4，则ˆfT(v)<γ/4+γ/4=γ/2。否则，如果fT(v)≥γ，则ˆfT(v)≥3fT(v)/4≥3γ/4>γ/2。因此，对于所有ˆfT(v)≥γ/2的v，我们输出YES，否则输出NO。0引理2.1.（切尔诺夫界）设X1,...,Xn是独立或负相关的二元随机变量。设X=∑ni=1Xi，µ=E[X]。那么，0Pr[|X−µ|≥ϵµ]≤exp(−min{ϵ2,ϵ}µ/3)。0回顾一下，S={z1,z2,...,zm'}是算法返回的样本集。对于固定的v∈[n]k，我们使用Zi作为事件zi,T=v的指示变量。由于我们是无放回地进行采样，随机变量Zi是负相关的。以下引理通过切尔诺夫界证明了对于所有的v和k维子立方体T，等式1成立。0引理2.2.对于所有的k维子立方体T和联合值v∈[n]k，至少有0.9的概率，0ˆfT(v)=fT(v)±max{γ,fT(v)}0证明。令m'=cγ-1log(dk∙nk)，其中c是足够大的常数。我们首先考虑固定的v∈[n]k，并定义上述的随机变量Zi，即如果zi,T=v，则Zi=1。假设fT(v)≥γ。根据引理2.1，我们有0Pr�0m'≤0Zim'��−fT(v)�����≥fT(v)0�������0=Pr����ˆfT(v)−fT(v)���≥fT( )0�0≤exp(−fT(v)/m')03×160≤1010dknk。0另一0Pr[ˆfT(v)−fT(v)]≥γ0≤exp(−γ04fT(v)0fT(v)/m'0�0≤010dknk。0因此，通过对所有的�dk�∙nk≤dk∙nk进行并集界，我们能够以至少0.9的概率正确回答所有的Query(T,v)，其中v∈[n]k和k维子立方体T。由于存储每个样本zi需要˜O(d)的空间，该算法使用˜O(dkγ-1)的空间。我们注0对于所有的k维子立方体和相应的联合值v∈[n]k的可能组合，我们得出结论。□0定理2.3.存在一个使用˜O(dkγ-1)的空间的一遍扫描算法，可以解决k维子立方体的重要项问题。此外，回答Query(T,v)和AllQuery(T)的时间复杂度分别为O(dkγ-1)和O(dkγ-1)。0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, France17080时间。0Query(T,v)和AllQuery(T)的时间复杂度分别为O(dkγ-1)和O(dkγ-1)。03 近似独立假设0更正式地说，我们假设总变差距离受到小量α的限制。此外，我们假设α相对于控制重要项的γ是合理的。例如，α≤γ/10就足够了。0f{1,...,d}(v)≈f1(v1)f2(v2)∙∙∙fd(vd)。0maxv∈[n]|T|0正式的近似独立假设如下：对于所有的子立方体T，存在α≤γ/10，使得0|T|≤0f(T)(v)−0当且仅当对于所有的i，f(Ti)(vi) <α时，i=1。0i=10|T|0f(Ti)(vi)≥f(T)(v)−γ/10>γ/2。0i=10|T|0f(Ti)(vi)≤f(T)(v)+γ/10<γ/2。0λ:=γ/2。0当且仅当对于所有的i，f(Ti)(vi)≥γ/2时，i=1。为，令0i∈V0算法细节。我们注意到，仅仅计算所有的f(Ti)(x)对于所有的i=10对于所有的V�[|T|]（即{Ti:i∈V}是T的子立方体），我们输出YES。0引理3.1. 对于所有的子立方体T，0|T|0i=10fTi(vi)≥λ意味着0�0i∈V0当且仅当f(Ti)(vi)≥λ时，i=10对于所有的V�[|T|]（即{Ti:i∈V}是T的子立方体）。0证明是显然的，因为所有的f(Ti)(vi)≤1。因此，我们有0以下推论。0推论3.2. 对于所有的子立方体T，0|T|0i=10fTi(vi)≥λ意味着fTi(vi)≥λ对于所有的i∈[|T|]。0因此，我们只需要在x是重要项时计算fi(x)。0在坐标i上，为了实现这一点，对于每个坐标i∈[d]，我们可以使用（例如）Misra-Gries算法[16]或Count-Minsketch[5]找到一个集合Hi，使得如果fi(x)≥λ/2，则x∈Hi，如果fi(x)<λ/4，则x�Hi。在第二遍扫描中，对于Hi中的每个x，我们精确计算fi(x)以获得0Si:={x∈[n]:fi(x)≥λ}。0如果且仅如果所有的vi∈STi，并且�|T|0当且仅当对于所有的i，f(Ti)(vi)≥λ时，i=1。注意，如果vi∈Si，则fi(v0该算法因为在第二遍扫描中精确计算，所以是精确的。详细算法如下。0(1)第一遍扫描：对于每个坐标i∈[d]，使用Misra-Gries算法找到Hi。(2)第二遍扫描：对于每个坐标i∈[d]，对Hi中的每个x，精确计算fi(x)得到Si。(3)当且仅当对于所有的i∈[|T|]，vi∈STi时，输出Query(T,v)的结果为YES。0|T|0当且仅当对于所有的i，f(Ti)(vi)≥λ时，i=10定理3.3.存在一个使用˜O(dγ-1)空间的两遍扫描算法，可以解决k维子立方体的重要项问0在近似独立的假设下，该算法使用O(k)的时间回答Query(T,v)和O(kγ-1)的时间回答AllQuery(T)。其中，k是T的维度。0证明。第一次遍历使用˜O(dλ-1)空间，因为Misra-Gries算法0算法对于每个坐标i ∈[d]使用˜O(λ-1)空间。由于每个Hi的大小为O(λ-1)，第二次遍历也使用˜O(dλ-1)空间。回想一下，λ =γ/2。然后我们得出结论，该算法使用˜O(dγ-1)空间。0对于任意的查询(T, v)，算法的正确性遵循0立即从推论3.2和观察到如果vi ∈STi，则fTi(vi)是可用的，因为它在第二次遍历中被精确计算。具体来说，如果0|T|0i = 10fTi(vi) ≥ λ，(2)0然后vi ∈ STi对于所有i ∈[|T|]，我们可以验证不等式并输出YES。另一方面，假设不等式2不成立。那么，如果vi �STi对于某个i，我们正确地输出NO。但是如果所有vi ∈STi，则我们能够验证不等式不成立（并正确输出NO）。0参数k只影响查询时间。我们现在分析0回答k维子立方体T的查询(Query(T, v)和AllQuery(T))所需的时间。0我们可以很容易地看出，查询(Query(T, v))需要˜O(k)时间，因为我们需要计算i = 10检查所有vi ∈ STi（例如，使用二分查找）并计算�k0注意，我们需要检查所有的vi ∈STi（例如，使用二分查找）并计算�k0注意，以朴素方式检查S T1 × ST2 × ∙ ∙ ∙ ×STk中的所有组合(v1,...,vk)在最坏情况下需要指数级的Ω(γ-k)时间。0回答k维子立方体T的查询(Query(T, v))和AllQuery(T)所需的时间。==17090我们的方法逐步找出重要的项，并利用近独立性假设。特别地，定义Wj := {v ∈ [n]j : fT1(v1) ∙ ∙ ∙ fTj(vj) ≥ λ}。0回想一下，目标是找到Wk。注意到W1 =S1可以直接通过算法获得。我们现在展示可以在˜O(λ-1)时间内从Wj构造Wj+1，从而意味着我们可以在˜O(kλ-1)时间内找到Wk。我们使用符号T[j] := {T1,...,Tj}和v[j] := (v1,v2,...,vj)。我们注意到� �� Wj � �� ≤5/(4λ)。这是因为如果y ∈ Wj，则� j i=1 fTi(yi) ≥λ。根据近独立性假设，我们有0fT[j](y) ≥0i = 1 fTi(yi) - α ≥ λ - α ≥ 4/5 ∙ λ.0对于每个y ∈ Wj，我们收集所有的x ∈ Sj+1，使得0i = 1 fTi(yi) � � � fTj+1(x) ≥λ0并将(y1,...,yj,x)放入Wj+1。由于|Wj| ≤ 5/4 ∙ λ-1和|Sj+1| ≤λ-1，这一步显然需要O(λ-2)时间。然而，通过观察到对于每个y ∈Wj，可能有至多λ-1个满足这样的x，x和y的组合数的上界为0�0y ∈ Wj01λ0i = 1 fTi(yi) ≤ �0y ∈ Wj01 λ (fT[j](y) +α)0= �0y ∈ Wj0αλ + �0y ∈ Wj0fT[j](y)0λ0≤ � ��  +10λ ≤ 0λ.0最后一个不等式来自于α ≤ λ/5和�y ∈ Wj fT[j](y) ≤1的假设。因此，算法可以在˜O(λ-1)时间内找到Wj+1，给定Wj。因此，我们可以在˜O(kλ-1) =˜O(kγ-1)时间内找到Wk。该过程的正确性直接来自于引理3.1和归纳，因为v = (v1,...,vj+1) ∈ Wj+1意味着v[j] ∈ Wj和vj+1 ∈Sj+1。因此，通过检查Wj中的所有组合y ∈ Wj和x ∈Sj+1，我们可以正确构造Wj+1。□04朴素贝叶斯假设0朴素贝叶斯假设。在本节中，我们关注受朴素贝叶斯模型启发的数据流，该模型严格比近独立性假设更一般。特别地，我们假设在额外的(d+1)th可观测类坐标中给定一个值在{1,...,ℓ}中的情况下，坐标是近独立的。第(d+1)th坐标通常也被称为潜在坐标。与朴素贝叶斯分析中一样，我们假设ℓ是一个常数，但是以ℓ为单位计算问题的复杂性。非正式地说，该模型断言表示坐标X1,...,Xd的随机变量在给定表示类坐标的随机变量Xd+1的条件下是近独立的。0我们引入以下符号0fT | d+1(v | z) := ���{xi : xi, T = v ∧ xi, {d+1} = z}���0���{xi : xi, {d+1} = z}��� = Pr[XT= v | Xd+1 = z].0换句话说，fT | d+1(v |z)是流中在T坐标中具有类坐标d+1值为z的项中v的频率。0形式化的朴素贝叶斯假设如下：对于所有的子立方体T，存在α ≤ γ/0max v ∈ [n]|T|0�������fT(v) − �0z ∈ [ℓ]fd+1(z)0i = 1 fTi | d+1(vi | z) <α。0算法细节。正如前一节所讨论的，只需0当且仅当对于查询(T, v)，输出YES时0�0z ∈0fd+1(z)0|T|0i = 10fTi | d+1(vi | z) ≥ γ/2 =λ。0然而，朴素地计算所有f i | d+1(vi |z)使用Ω(ℓdn)的空间。我们通过将引理3.1推广如下来避免这个问题。如果一个联合值v是朴素贝叶斯公式中子立方体T的重要项，并且T'是T的子立方体，则vT'是子立方体T'的重要项。0引理4.1. 对于所有的子立方体T，0q(v) :=0�0z ∈[ℓ0fd+1(z)0|T|0i = 10fTi | d+1(vi | z) ≥ λ0意味着0�0z ∈0fd+1(z)0�0i ∈ V0fTi | d+1(vi | z) ≥ λ0对于所有的V � [|T|]（即{Ti : i ∈ V}是T的子立方体）。0证明。对于固定的z，观察到0�0yj ∈0fTj | d+1(yj | z) = 1.0假设q(v) ≥ λ，并考虑任意的V � [|T|]。我们有0�0z ∈[0fd+1(z)0�0i ∈ V0fTi | d+1(vi | z)0�0z ∈[0fd+1(z)0�0i0f T i  |  d + 1（vi  |  z）0�0j ∈ V0�0�0y j ∈[n]0f T j  |  d +1（y j  |  z）� 0�0≥0�0z ∈[0f d + 1（z）0�0i ∈V0f T i  |  d + 1（vi  |  z）0�0j ∈ V0f T j  |  d + 1（vj  |  z）0�0z ∈0f d + 1（z）0| T| �0f T i  |  d + 1（v i  |  z） =q（v）≥ λ。0另一种证明是注意到q（v）是| T|个变量的有效概率密度函数。通过对不在V中的变量进行边际化，得出结论。□0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, France17100设置V = {i}对于每个i ∈ [| T  |]并利用以下事实0z ∈ [ℓ] f d + 1（z）f T i  |  d +1（v i  |  z） = �0z ∈ [ℓ] f { T i , d + 1 } (( v i , z ))=  f T i  ( v i  )  ,0我们推断以下推论。0推论4.2.对于所有子立方体T，0z ∈ [ℓ] f d +1（z）0| T0i = 1 f T i  |  d + 1（v i  |  z）≥ λ意味着f Ti（v i）≥ λ0对于所有i ∈ [| T0因此，我们只需要计算所有坐标i ∈ [d]，值z ∈ [ℓ]的f i  |  d + 1（x|  z），如果x是坐标i的重要项。与前一节类似，对于每个维度i ∈[d]，我们在第一遍中找到Hi，并在第二遍中使用Hi找到Si。根据推论4.2，我们推断如果0q（v）0z ∈ [ℓ] f d +1（z）0| T0i = 1 f T i  |  d + 1（v i |  z）≥ λ0那么对于所有i = 1, 2，...，| T  |，我们有f T i（v i）≥λ，这反过来又意味着v i ∈ S T i。因此，我们仅当所有v i ∈ S Ti且q（v）≥ λ时输出YES。为此，我们只需要计算所有x ∈ Hi，z ∈[ℓ]和i ∈ [d]的f i  |  d + 1（x  |  z）和f d +1（z）。详细算法如下。0（1）第一遍：（a）对于每个值z ∈ [ℓ]，精确计算f d +1（z）。 （b）对于每个坐标i ∈[d]，使用Misra-Gries算法找到Hi。（2）第二遍：（a）对于每个坐标i ∈ [d]和每个值x ∈Hi，精确计算f i（x）以获得Si。 （b）对于每个值z ∈[ℓ]，坐标i ∈ [d]和x ∈ Hi，精确计算f i  |  d + 1（x  |z）。 （3）仅当对于所有i ∈ [| T  |]和0z ∈ [ℓ] f d +1（z）0| T0i = 1 f T i  |  d + 1（v i|  z）≥ λ。0定理4.3.存在一种2遍算法，使用˜O（ℓdγ−1）的空间解决子立方0空间并在朴素贝叶斯假设下解决子立方体重要项。回答查询（T，v）和AllQuery（T）的时间分别为˜O（ℓk）和O（ℓ（k /γ）2），其中k是T的维度。0˜O（dλ−1）。此外，计算所有i∈[d]，z∈[ℓ]和x∈Hi的f i  |  d +1（x  |z）需要˜O（ℓdλ−1）位的空间。因此，我们需要的总空间是˜O（ℓdλ−10回答任意查询（T，v）的正确性遵循0直接来自推论4.2。具体来说，如果0�0z ∈[ℓ]0f d + 1（z）0| T| �0f T i  |  d + 1（v i  |  z）≥λ，（3）0然后，v i ∈ S T i � H T i对于所有i ∈ [| T|]如所述。因此，在第二遍中，对于所有z ∈ [ℓ]，计算f T [j]（y）≥ λ− α = 4 / 5 ∙ λ − 1。根据朴素贝叶斯假设。这意味着| W j | ≤ 5/（4λ）。0显然，查询（T，v）对于k维的k维子立方体T需要˜O（ℓk）的时间0子立方体T。我们现在展示一个快速算法来回答k维子立方体T的AllQuery（T）。定义0Wj：= {v ∈[n]j：0�0z ∈0f d + 1（z）0j �0f T i  |  d + 1（v i  |z）≥ λ}。0回想一下，目标是找到Wk。我们注意到W1 =S1直接由算法获得。接下来，我们展示如何从Wj获得Wj +1，时间复杂度为˜O（λ−2）。注意到| Wj | ≤ 5/（4λ），因为如果y ∈ Wj，则0�0z ∈[ℓ]0f T 1  |  d + 1（y 1  |  z）∙∙∙  f T j  |  d + 1（y j  |z）f d + 1（z）≥ λ0因此f T [j]（y）≥ λ − α = 4 / 5 ∙ λ −1根据朴素贝叶斯假设。这意味着| Wj | ≤ 5 /（4λ）。0对于Wj中的每个（v1，∙∙∙，vj），我们收集所有的vj + 1∈Sj +1，0�0z ∈0f T 1  |  d + 1（v 1  |  z）∙∙∙  f T j + 1  |  d + 1（v j + 1  |z）f d + 1（z）≥ λ0并将（v1，∙∙∙，vj + 1）放入Wj + 1。由于|Wj | ≤ 5 /（4λ）和|Sj +1 | ≤ 1 / λ，这一步显然需要˜O（ℓkλ−2）的时间。由于我们需要对j= 2, 3，...，k进行此操作，所以我们在˜O（ℓ（k /γ）2）的时间内获得Wk。此过程的正确性直接遵循引理4.1和归纳法，因为（v1，...，vj + 1）∈Wj +1意味着（v1，...，vj）在Wj中，并且vj + 1在Sj +1中。由于我们检查了所有可能的（v1，...，vj）∈Wj和vj + 1∈Sj +1的组合，我们保证正确构造Wj + 1。□05实验研究0概述。我们在合成数据集上对我们的算法进行实验0从朴素贝叶斯模型生成的数据集以及Adobe Marketing Cloud2和Yandex的两个真实数据集。我们彻底比较以下方法：0•  第2节中的采样方法（采样）。•第3节中描述的2遍算法（TwoPassAlg）和0根据实验的上下文，我们可以选择使用不同的方法，具体取决于实验的上下文0•  Count-Min草图启发式（启发式）：该启发式使用0Count-Min草图的点查询估计（参见[5]）来估计由近似独立公式给出的频率（而不是通过流的第二次遍历来计算它们的精确值）。我们注意到这种方法没有理论保证。0我们强调第3节和第4节中理论算法与实际实现之间的主要区别：02 http://www.adobe.com/marketing-cloud.html0Track: Web Search and Mining WWW 2018，2018年4月23日至27日，法国里昂17110•与运行我们的算法的理论内存界限不同，我们运行并比较它们在不同内存限制下的性能。这种方法在实施角度更加实用和自然。•理论上，Sampling和TwoPassAlg使用固定的阈值γ* = γ /2来决定输出YES还是NO。然而，当内存更有限或者假设在真实数据中不完美时，我们尝试不同的γ*值是有帮助的。0重要元素阈值γ被精心选择，使得重要元素数量与总共的联合值的比例相对较小，即在本文中大约最多为1%。因此，我们针对每个数据集使用不同的γ值（有关实际参数值，请参见表1）。05.1合成数据集0合成数据集是从一个预训练的朴素贝叶斯模型中采样得到的，该模型用于估计页面浏览的概率。该模型由[11]提供，并建立在我们在第5.2节中使用的相同点击流数据集上。坐标包括一个类变量Z和五个特征变量（X1，...，X5），具有高基数。该数据集严格遵循X1，...，X5在给定Z的条件下相互独立的属性。具体来说，变量及其对应的近似基数如下：国家（7），城市（10,500），页面名称（8,500），起始页面名称（6,400），活动（3,500），浏览器（300），其中国家是类变量。0热身实验。我们首先在这个合成数据集上评估Sampling和Heuristic。如前所述，我们比较了两种方法在每个固定内存大小下的性能。30我们选择了一个子集，约有135,000条记录，以固定且最频繁的Z值为条件，以便在该子集中使X1，...，X5相互独立。然后，我们在三个不同的子立方体上运行实验：{X1，X2，X3}，{X2，X3，X4}和{X3，X4，X5}。在这个热身实验中，主要目标不是找到重要元素，而是比较Heuristic和Sampling给出的重要元素频率估计的准确性。我们通过均方误差（MSE），平均绝对误差（MAE）和平均绝对百分比误差（MAPE）来衡量性能。为此，真实频率已经预先计算好了。我们使用了上述每个子立方体中前10个重要元素的频率。结果（见图1）表明，在限制内存较小的情况下，Heuristic的性能优于Sampling。这个热身实验证明了了解底层分布结构有助于改进小空间启发式算法在估计重要元素频率方面的性能。0近独立性假设的实验。我们比较了三种上述方法在近独立性假设下找到重要元素的性能。在这个实验中，我们使用与之前实验中相同的数据子集和子立方体。我们将内存固定为数据大小的2%。03我们将Sampling的内存使用量计算为维度和样本大小的乘积。Heuristic的内存使用量计算为维度和Count-Min sketch的大小的乘积。0数据集 内存 子立方体 γ 重要元素数量 重要元素比例0合成（固定Z）2% 3 0.002 29.7 0.079% 合成（全部）2% 3 0.00228.7 0.054% 点击流10% 4 0.002 42.0 0.165% Yandex 0.2% 8 0.1 2.21.51%0表1：每个实验的参数值。（列对应于相对于数据集的内存大小，实验的子立方体数量，平均重要元素数量，平均重要元素百分比。）0我们根据真正和假正例的数量来衡量性能，对于不同的γ*值。如图2所示，对于较小的内存，Heuristic和TwoPassAlg都能找到比Sampling更多的重要元素。在假正例方面，TwoPassAlg在较小的空间中击败了Heuristic和Sampling。一个可能的解释是，当γ*很小时（接近γ），TwoPassAlg凭借第二次遍历的优势，准确地估计了潜在重要元素的频率，而其他两种方法，特别是Heuristic，高估了频率，因此报告了更多的假正例。对于较大的γ*，假正例变得不太可能，三种方法的性能都相似。总的来说，TwoPassAlg在ROC曲线中获得了最佳性能。0朴素贝叶斯假设的实验。我们使用约168,000条记录的整个数据集，不固定Z，并保持其他设置不变。我们只比较TwoPassAlg和Sampling的性能，因为无法直接从Heuristic中推导出条件概率。如图3所示，当限制在较小的内存时，TwoPassAlg通过报告更多的真正重要元素和更