How to Approximate a Set without Knowing it's Size in Advance
79 views · Published 14 March 2016 · 49:06 · Indexed 31 October 2026
Channel: Institut Henri Poincaré · 2016 · Science & Technology
By Udi Wieder (VMware Research) Abstract: The dynamic approximate membership problem asks to represent a set [Math Processing Error] of size [Math Processing Error], whose elements are provided in an on-line fashion, supporting membership queries without false negatives and with a false positive rate at most [Math Processing Error]. That is, the membership algorithm must be correct on each [Math Processing Error], and may err with probability at most [Math Processing Error] on each [Math Processing Error]. We study a well-motivated, yet insufficiently explored, variant of this problem where the size [Math Processing Error] 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 [Math Processing Error] 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 [Math Processing Error]. 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 [Math Processing Error] bits of space are necessary and sufficient. However, when the size is not known in advance, we prove that at least [Math Processing Error] bits of space must be used. In particular, the average number of bits per element must depend on the size of the set. If time allows we will show that this space lower bound is tight, and can be matched by an efficient data structure. The data structure supports membership queries in constant time in the worst case with high probability, and supports insertions in expected amortized constant time.
More from this channel
-
29:47
10 ans du Groupe Calcul : Histoire du Calcul - Introduction
-
52:14
Gauss, Jacobi, Seidel, Richardson, Krylov: the Invention of Iterative Methods
-
55:33
Les "invariants arithmétiques" de H. Poincaré
-
1:08:53
Henri Poincaré, a founding father of the modern theory of PDEs
-
57:13
Sympletic topology from Poincaré to Gromov
-
57:35
Structural Realism, Then and Now
-
46:26
Poincaré inequalities in probability and geometric analysis
-
1:02:05
On the contributions of Henri Poincaré to modern geophysics...