# 迭代构建机制和𝞪-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**](https://github.com/doubleheiker/algorithmic-foundation-of-dp-zh-cn/blob/master/4-Releasing-Linear-Quries-with-Correlated-Error/An-online-mechanism-private-multiplicative-weights/The-multiplicative-weight-update-rule.html)取$$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**](https://github.com/doubleheiker/algorithmic-foundation-of-dp-zh-cn/blob/master/4-Releasing-Linear-Quries-with-Correlated-Error/An-offline-algorithm-SmallDB/An-offline-algorithm-SmallDB.html)中使用不同$$\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）算法也有相同的现象——它也使用完全由查询的小“网络”确定的数据结构来回答大量线性查询。