多叉树定义为可以有多于两个子节点的树。如果多叉树最多可以有 m 个子节点，则此树称为 m 阶多叉树。与其他已研究的树一样，m 叉树中的节点将由 m-1 个键字段和指向子节点的指针组成。5 阶多叉树为了简化 m 叉树的处理，会在每个节点内的键上施加某种约束或顺序，从而得到 m 阶多叉搜索树…… 阅读更多

基本概念多维二叉搜索树（简称 k-d 树）定义为用于存储多键记录的数据结构。此结构已实现用于解决统计和数据分析中的一些“几何”问题。k-d 树（k 维树的简称）定义为一种用于组织 k 维空间中点的空间划分数据结构。数据结构 k-d 树已用于多种应用程序，例如涉及多维搜索键的搜索（例如范围搜索和最近邻搜索）。k-d 树被视为二叉空间划分树的特例。非正式描述k-d 树是一种二叉树…… 阅读更多

再平衡算法可以通过以下方式执行：Day-Stout-Warren 算法我们可以使用 Day-Stout-Warren 算法实现实际的再平衡方法。它是节点数量的线性函数。以下是伪代码中基本 DSW 算法的表示。分配一个名为“伪根”的节点，并将树的实际根作为伪根的右子节点。调用树到藤函数，将树转换为具有伪根作为其参数的有序链表。调用藤到树函数，再次使用伪根和树的大小（元素数量）作为其参数，将有序链表转换为树。树的实际…… 阅读更多

我们首先选择一个内存块。然后我们选择每个块内的局部布隆过滤器。这可能会导致内存块之间不平衡此过滤器效率高，但错误肯定率 (FPR) 差。在第一次实例中，分块布隆过滤器应与相同大小的标准布隆过滤器的 FPR（错误肯定率）相同。分块布隆过滤器由一系列块 b 组成，这些块比标准布隆过滤器（布隆过滤器块）小得多，每个块都适合一个高速缓存行。分块布隆过滤器方案与分区方案不同，在分区方案中，每个位都插入到不同的块中。分块布隆过滤器以以下方式实现：位…… 阅读更多

计数器大小我们必须选择足够大的计数器以避免溢出。泊松近似建议大小为 4 位/计数器。实现 k = (ln 2)m/n 计数器的平均负载为 ln 2。计数器负载至少为 16 的概率：≈e-ln2(ln 2)16/16！≈6.78E-17我们考虑 4 位/计数器进行比较。计数器溢出当计数器溢出时，它可能达到其最大值。这种情况以后只会导致假阴性，如果计数器最终在应该保持非零值时下降到 0。这种情况的预期时间非常长，但对于不允许假……的任何应用程序，我们都需要牢记这一点 阅读更多

基本概念计数布隆过滤器定义为布隆过滤器的广义数据结构，用于测试当给出一系列元素时给定元素的计数是否小于给定阈值。作为布隆过滤器的广义形式，存在错误肯定匹配的可能性，但没有错误否定的机会——换句话说，查询返回“可能高于或等于阈值”或“肯定低于阈值”。算法描述计数布隆过滤器下使用的许多参数与布隆过滤器相同，例如 n，…… 阅读更多

布隆过滤器有三个可以权衡的性能指标：计算或执行时间（对应于哈希函数的数量 k）、过滤器的大小（对应于位数 m）和错误概率（对应于错误肯定率 f = (1 − p)k）布隆过滤器 (BF) 引入误差容限以提高查找性能和空间效率。布隆过滤器返回真或假。因此，布隆过滤器的结果属于以下类别之一：真阳性、假阳性、真阴性和假阴性。布隆……的最大数量 阅读更多

布隆过滤器定义为一种数据结构，旨在以快速且内存高效的方式识别元素在一个集合中的存在。概率数据结构名为布隆过滤器。此数据结构可帮助我们确定元素是否存在于集合中。位向量被实现为基础数据结构。这是一个我们将用来解释的小例子123456789101112131415表中每个空单元格指定一个位及其下方的数字是其索引或位置。要将元素添加到布隆过滤器，我们只需哈希…… 阅读更多

多重选择哈希之所以如此命名，是因为它使用了多个哈希函数的实现。在高层次上，当存在多个哈希函数时，每个项目都映射到多个桶，因此算法设计者可以自由选择项目将驻留在其中的桶。事实证明，这种自由允许算法获得比使用单个哈希函数所获得的分配更平衡的分配。我们将介绍主要的算法思想和用于证明这些算法产生的分配边界的数学工具。我们将看到分析是…… 阅读更多

定义动态完美哈希定义为一种编程方法，用于解决哈希表数据结构中的冲突。应用程序虽然比其哈希表对应物更占用内存，但此方法非常适合必须对大量元素执行快速查询、插入和删除的情况。实现Dietzfelbinger 等人解释了一种动态字典算法，当将一组 m 个项目增量添加到字典时，成员资格查询始终消耗恒定时间，因此为 O(1) 最坏情况时间，所需的总存储空间为 O(m)（线性），并且 O(1) 预期摊销插入和删除时间（摊销恒定时间）。在动态情况下，当…… 阅读更多