查询的复杂性估计加权平均数

1、查询的复杂性估计加权平均数注：公式部分请查看原稿。Amit Chakrabarti - Venkatesan Guruswami AndrewWirth AnthonyWirth收稿日期：2010年2月20日/9月8日2011 /在线出版：2011年11月17日施普林格出版社2011摘要由一些0，1变量查询的复杂性估计均值的理解，以及查克拉巴蒂在一些评估检索系统工作上的启发和 Moffat和Zobel的新提议作出了这样的评价，我们检查查询的复杂性加的平均计算，一般情况下，确定具有很 高的精度内的答复概率，需要（厂2 ）次查询。由于平均值是一个特例，有一个匹配加权平均值的上限。如 果权重是一个发

2、散的系列归前缀，持有相同的结果。但是，如果权重按照等比数列，样本大小为。（log（1/力 就足够了。我们的主要贡献是权重幕律序列的调查。我们证明，如果第，个最大权重比例为LP，p 1，则查 询的复杂性是口 （ 8 2/（ 1-2 p）。一引言在本文中，我们建立了查询的复杂性估计的上限和下限加权平均二元变量的集合。理论界已建立查询复杂性 估计的多项函数。特别是，查询复杂的瞬时函数，如平均值和一些的对称函数像我们所知的1,2。A. Chakrabarti计算机科学系，达特茅斯学院，汉诺威，NH 03755，美国V.Guruswami计算机科学系，美国卡内基-梅隆大学，匹兹堡，PA 15213,美国

3、A. Wirth机械工程学系，墨尔本大学，帕克维尔，VIC3010，澳大利亚A. Wirth （B ）计算机科学与软件工程，墨尔本大学，帕克维尔，VIC 3010，澳大利亚电子邮件： HYPERLINK mailto:.au .au1.1正式定义首先考虑估算的投入数量的平均值的标准问题。一个平均值的实例中S个输入值（1，,xm），每一个都在集 合。0 1中。我们的任务是返回值的以（x） =m x./m。四a （y）三乌a1 ai需要注意的是。的值时固定和已知的：他们是定义的一部分问另一个例子加权平均值作为输入n个值（y 1，*

4、），在集合Q 01，任务是返回值n每个a.都在Q0 1中，且相邻对满足a.君a. + 1。题。为了方便，权重代表aj/_n1aj，b-权重不增加且总和为1。最后，我们让.代表）.与，权重的尾部。在本文中，我们了解了矢量a在确定查询复杂的加权平均值中所扮演的重要角色。一些分析将涉及随机算法。 在本文中，我们只关心绝对偏差的真实值。因此，一个随机决策程序（定义见下文）侣，仞如果近似一个问题 （一个特定的输入的大小），对于每个实例，概率为1 -凯输出于满足侦-四（x） 8或（or侦-四a （y）| 8,，视 情况而定）。在查询的复杂性环境中，算法的成本不计算。我们完成了解决平均值或加权平均值的问题，

5、只是我们输 入查询元素x （或y）的数量。1.1.1 策程序Bar-Yossef et al 1 中描述了分析查询复杂性决策过程的框架。我们认为一个算法（近似的）解决了决策树中 的这些问题之一。树中的每个节点代表一个单一的数据元素的查询。因此该决策树（确定性）最差的表现是 查询节点的数量是从根到叶子的最长路径。预计查询性能的一个随机决定树或者为此事分配的确定性决定输入x，超过预计数路径上的节点对应输 入乂。预计查询的复杂性作为一个功能树输入的大小，是最大预期大小的所有实例的查询性能最后，预期查询的复杂性（最差情况），一个家庭的问题实例，关于侣，仞，是最低的预期（最坏情况下） 查询所有随机的复杂

6、性决策树侣，a）近似的问题。它明确定义预计查询的复杂性的一个问题是最坏情况的复杂 性。1.2动机信息检索社会的利益在检索系统的评价3动机这项研究中。给定一个主题，正在评估一个系统返回一个 文件的排名名单索赔有关的话题。人权法官确定每一个文件是否相关：他们必须支付要做到这一点。因此， 每个系统的性能是一个函数文档的排名和相关性的判断：这一个指标是事先商定后。查询的复杂性是一个合 适的的理论模型评价成本。文件相关的决定是昂贵的，随之而来的计算是非常便宜的。然而，评价指标没有达成共识。有些指标似乎比其他的更稳定，而另一些更容易解释用户在建模方面的 行为。Moffat和Zobel6提出了一种度量与几何

7、权重序列相关分数。因此，我们检查查询的复杂性，加权指 标平均水平，也就是直线职能的相关性值。检索社会研究系统评价的理论：有在其实一个专门的车间EVIA:国际研讨会上评价信息访问。然而， 这些结果往往承担一些相关的统计分布文件的主题。我们热衷于研究最坏情况的查询的复杂性，或预期复杂 性，期望算法中随机选择，而不是随意性在数据中。1.3前期工作虽然查询的复杂性和通信的复杂性在理论社会有悠久的历史，但是只有很少的几篇论文关于估计平均值。Canetti et al.表明0厂2奖（1仞样本是必需的，表现出了高效的采样器（硬币投掷发生器）为目的。在随机 取样的分布值背景下，Dagum et al. 4估计

8、平均提供一个有效的停止规则分布在乘法因子。Bar-Yossef et a.的 2001年文献1是主要参考。它描述了不牢固的却有用的，预计查询的复杂性下界技术，和一个在最坏情况下 在对称函数上强一点的技术。他们的主要结果是，平均数问题最坏情况的查询的复杂性在Q（厂2 ）。定理1平均输入大小为n时,最坏情况下的查询复杂性的平均值，至少是对8 8” WQ（1/n）和 3 1)(n1 /(p-1/ 2)log( 1/3)t-c最坏的情况1.5组织的文件在第2节，从Moffat和Zobel的评价指标中，我们考虑了几何级数的连续。然后，我们开发一个通用的上界， 查询的复杂约束加权平均值在第3节，以及一个幕

9、律权重的特殊约束。第4节有较强的下界技术，并提供一 个匹配较低的幕律约束权重。在最后一节我们概述了今后的工作。2几何权重几何递减权重是最简单的的分析。在这样做之前，我们总结了块灵敏度的概念，参考Bar-Yossef et al文献1建 立了定义4和定理5。估计问题是e敏感块(输入的一个子集)，如果有一些输入的例子在更改块中的所有元素会导致真正的输出 改变至少2疑例如，如果一些b.(标准化)权重至少2&然后加权平均值问题是e敏感到相应的输入值切e 块灵敏度定义是最大的问题是e敏感的两两不相交的块数。较低的e块灵敏度容易导致预期查询的复杂性出 问题。引论1 (Bar-Yossef et al 1)

10、对于每一个非负的和在0，1 / 2中的，预期查询的复杂性至少是(1 - 2仞乘以 8块灵敏度。为了分析的几何权重情况，我们让a. = q，一些q 2s是这是(log(1/s力。我们应用这个估计引理1，获得接下来的下界。引论2当a. = q-，加权平均值a预计查询的复杂性是在口(1 - 2仞log(1/s力中 请注意，这个下界很容易匹配(内加常数)接下来的算法。查询每个七，其中zVe是满足的最低值%/疚2。查询所有y, i s上通用计划标准化上的b-权重在i:is。 返回 m 1 + Bm 2。输入被查询元素的总数和下式成正比通用计划i : i s精度e/（2B）查询每一个系数至少e/2的y,很

11、有意义。然而，在分离规则下，B2/e2项可能主宰在表达式中的S项（1）。如果我 们增加明确被查询的输入元素的数量（增大s的值），并在较小的尾部上运行通用的计划，然后B的权重将下 s降。我们因此选择5使两个贡献表示的（1）大致相等。3.2.1 Power权重定理Power权重定理是一个自然家庭研究。如果气=一些p 1（使级数收敛），然后Bs = b约为si-P/（ p -1），当 pp样本大小为0（n 1/（p-1/2）iog（ 1而）就够了。请注意，此函数增长相当缓慢比着在3.1节的约束平。4下界在本节中，我们运用比块敏感性更强的技术为特殊的加权平均值a比重家庭开发查询复杂性下界。4.1降低技

12、术我们开始降低技术概述。我们知道，为适当的选择e和的值，平均查询的复杂性是Q（e-2 log（1/Q）。给一个 实例（x 1，xm）的平均值我们设立所附实例（y1，yn）的加权平均值a，解决了几乎同样的问题（在允许的误差 内）。首先我们把加权平均值a的问题中的n权重分割成m个子集51,. , Sm 。对每个j w死，我们有效地设 置y,等于x.。如果j不在一些子集中，那么把yj设置为0。请注意，我们实际上并没有对x值做最初的访问， 而是我们对它们的引用，因此，如果需要的话，他们可以查询。如果我们选择的子集，使 .b.y.和Zxc./m之间的差异接近e。那么）的加权平均值a逼近（2e, 8）的平

13、 均数。此外，每一个新的x.项的加权平均值算法都是查询一个新的y/项的查询结果。因此，在最坏情况下（或 预期）的查询的复杂性加权平均值a问题必须至少是平均数那个问题。再次，在构造集合S.时降低计划不知 道x的值。关于平均值的例子唯一重要的事实约在降低的是其输入的大小，而不是输入项的顺序。4.2发散权重几何递减权重收敛速度非常快。相反的极端是一个不衔接的权重系列。现在，我们假设na发散随着n增加。i引理5对于足够大的n，如果a -权重系列发散，那么最坏情况下的查询复杂性是Q（e-2log（ 1/8）。证明考虑下面的过程：从第k权重S形式的子集0,. , ak，其中k满足我们能够实现这一目标是因为

14、权重系列发散和对所有的i，ai 1。让1表示(k ai) - / .我们重复这个过程，形成S2和2,等等，直到我们至少有log(1/43)/6s2个子集(这种表达的起源见定理1)。 “四a (y)值是，其中aS,为代表权重在该子集的总和。如果我们创建了两个新的变数。=i a i,和7 =m ixi,然后七(y)的值是(2)由于n 2s，为指数i建立块。对于b.其余的项，通过紧密组合在一起的连续序列形成块，其总和至 少是2s。回顾以往的注释，让s是最大的指数I,b2s。s-块敏感度至少是(3)因为b-权重的每一块接近s小于4s (每项不少于2 )。对于a. = i-p，s清楚地在(s-1/p)

15、= (n 1/p)中。由于Bs 是(s 1-1/p)中，第二项在约束下(3)也在(n1/p)中。这下界弱于我们在3.2节中获得的O(n 1 /(p-1/2)上界。4.3.2降低我们现在模仿第4.2节的过程。除去更复杂的降低平均数问题。我们把一些权重n分开为一个加权平均值a 的例子，尽可能看起来很像平均值。假设那一刻，我们有一个不相交的子集Sz.的集合m，满足p s /(2m) bs P一些p，我们将尽快指定，其中bSi三 j爻b。我们的结论是(P xz.)-s/2 bjyj t2 t和一些心n和所有的咨N我们知道ttj/(m - 1)如果我们将LPT启发式，然 后在完成时间的差异对每个机器之间

16、至多tN + 101证明我们两个边界，在完成时间上的差异。让e表示最后作业完成。LPT规则确保，当工作e开始时，所有 的机器都很忙，除非e=1，因此它是最长的工作。无论哪种方式，每一对机器在下班时间之间的的差异最多 是te。另一方面，e+ 1, e + 2,. , n等所有的工作都在e后启动，在e前完成。这些工作的剩余机容量以(m - 1)t为界。因此，Ze+1 tj (m - 1) te因此，如果所有的工作z N + 1，因此在完成时间的区别最多是tN+1.。为了应用引理6,我们专注加权序列中小的项，那些满足条件B. (m -1您的i。在一些权重，如幕律序列， 序列，最初的项是非常大的，并不

17、小。最终项不小因为尾部是如此之小，但在两者之间的项很小。设r是最 小的指数：从今以后，我们忽略了对j r。为了确保bS值非常接近，我们假设权重序列是如此的长，每一 个r和k之间的指数是轻易满足bkr.由于= B,，b-权重和每对子群之间的差异是最8/(4m)，我们知道，不等式(4)满足p = Br/m + 8/(4m)。因此，我们有一个(8/(mp),仞-作为平均值的逼近。定 理1说，在最坏情况下的查询的复杂性是成正比m2p2/82,在O(m)上提供这种表达是在O(m)。现在，我们可以证明下界和第3.2节的结果相匹配。引理7当a. = i-P是在最坏情况下的查询的复杂性的加权平均值a证明我们需要选择r和m满足这三个条件。假设n是非常大的，意味着，如果r mp，那么第一个条件成立。我们希望m表示所需的样本大小，对b