How to Approximate a Set without Knowing Its Size in Advance
How to Approximate a Set without Knowing Its Size in Advance
复制标题
DOI：
10.1109/focs.2013.17
复制
发表时间：
2013-04
期刊：
影响因子：
--
通讯作者：
Rasmus Pagh;Gil Segev;Udi Wieder
中科院分区：
文献类型：
--
作者：
Rasmus Pagh;Gil Segev;Udi Wieder
动态近似隶属度问题要求表示一个大小为 n 的集合 S，其元素以在线方式提供，支持没有误报且误报率最多为 ε 的隶属度查询。也就是说，隶属算法在每个 x ∈ S 上必须是正确的，并且在每个 x ∉ S 上最多可能出错 ε 。我们研究了这个问题的一个动机良好但尚未充分探索的变体，其中集合的大小 n 事先未知。现有的最佳近似隶属数据结构要求预先知道大小，但在许多实际场景中这不是一个现实的假设。此外，即使预先知道集合的最终大小n，当当前插入元素的数量小于n时，也希望具有尽可能最小的空间使用。我们的贡献包括以下结果：（1）我们展示了预先已知大小时的空间复杂度与预先未知大小时的空间复杂度之间的超线性差距。当预先知道大小时，众所周知，θ(n log(1/ε)) 位空间是必要且充足的（Bloom '70，Carter et al. '78）。然而，当事先不知道大小时，我们证明至少必须使用 (1 -o(1))n log(1/ε)+Ω(n log log n) 位空间。特别是，每个元素的平均位数必须取决于集合的大小。 。我们证明了我们的空间下界是紧的，甚至可以通过高效的数据结构来匹配。我们提出了一种数据结构，它使用 (1+o(1))n log(1/ε)+O(n log log n) 位空间来近似任何大小 n 的任何集合，而无需提前知道 n。我们的数据结构以高概率支持最坏情况下恒定时间的成员资格查询，并支持预期摊销恒定时间的插入。此外，只需将其空间使用量增加到 O(n log(1/ε) + n loglogn) 位，就可以对其进行“去摊销”，以高概率支持最坏情况下恒定时间的插入。
The dynamic approximate membership problem asks to represent a set S of size n, whose elements are provided in an on-line fashion, supporting membership queries without false negatives and with a false positive rate at most ε. That is, the membership algorithm must be correct on each x ∈ S, and may err with probability at most ε on each x ∉ S. We study a well-motivated, yet insufficiently explored, variant of this problem where the size n of the set is not known in advance. Existing optimal approximate membership data structures require that the size is known in advance, but in many practical scenarios this is not a realistic assumption. Moreover, even if the eventual size n of the set is known in advance, it is desirable to have the smallest possible space usage also when the current number of inserted elements is smaller than n. Our contribution consists of the following results: (1) We show a super-linear gap between the space complexity when the size is known in advance and the space complexity when the size is not known in advance. When the size is known in advance, it is well-known that Θ(n log(1/ε)) bits of space are necessary and sufficient (Bloom '70, Carter et al. '78). However, when the size is not known in advance, we prove that at least (1 -o(1))n log(1/ε)+Ω(n log log n) bits of space must be used. In particular, the average number of bits per element must depend on the size of the set. . We show that our space lower bound is tight, and can even be matched by a highly efficient data structure. We present a data structure that uses (1+o(1))n log(1/ε)+O(n log log n) bits of space for approximating any set of any size n, without having to know n in advance. Our data structure supports membership queries in constant time in the worst case with high probability, and supports insertions in expected amortized constant time. Moreover, it can be “de-amortized” to support also insertions in constant time in the worst case with high probability by only increasing its space usage to O(n log(1/ε) + n loglogn) bits.