迭代构建机制和𝞪-nets

迭代构造机制的实现方式与Net机制不同，但在其核心，它的分析仍然基于查询$C$的小型$\alpha-\text{nets}$的存在。这种关联对于由网络参数化的中位数机制是显式的，但它适用于所有数据库更新算法。请注意，迭代构建数据库算法的数据库输出完全由输入的最多$T$个函数$f_1,...,f_T\in \mathcal{Q}$ 决定，由算法运行时的区分器选择。每一个函数可以由最多$\log|\mathcal{Q}|$位索引，因此该机制的每个数据库输出都可以仅使用$T\log|\mathcal{Q}|$位来描述。换句话说，IC算法本身描述了一个大小最多为$\mathcal{N}_\alpha(\mathcal{Q})\leq|\mathcal{Q}|^T$的$\mathcal{Q}$的$\alpha-\text{net}$。为了使用可乘权重算法作为迭代数据库构造器来获得错误的$\alpha$，通过定理 4.10取$T=4\log|\mathcal{X}|/\alpha^2$就足够了，这给了我们$\mathcal{N}_\alpha(Q)\leq |Q|^{4\log|\mathcal{X}|/\alpha^2}=|\mathcal{X}|^{4\log|Q|/\alpha^2}$。请注意，指数中的因子为4，这正是我们在定理 4.2中使用不同$\alpha-\text{net}$给出的界限！这里，我们通过考虑$\log|\mathcal{Q}|/\alpha^2$个数据点的所有集合构建了一个$\alpha-\text{net}$，每个数据点后可以由$\log|\mathcal{X}|$位索引。两种方式，我们都得到了相同大小的$\alpha-\text{nets}$！ 实际上，我们也可以使用IC机制定义的$\alpha-\text{net}$来运行Net机制，以获得相同的效用界限。从某种意义上说，一个网络是另一个网络的“双重”：一个由数据库构成，另一个由查询构成，但两个网络的大小相同。我们将会看到在下一节中的“提升查询”（boosting for queries）算法也有相同的现象——它也使用完全由查询的小“网络”确定的数据结构来回答大量线性查询。