, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension, Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC '86, pp.273-282, 1986.
, The tao of inference in privacy-protected databases, Proc. VLDB Endow, vol.11, pp.1715-1728, 2018.
, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. Syst. Sci, vol.13, issue.3, pp.335-379, 1976.
, US Census Bureau. US Census Bureau name statistics, 2016.
, as desired 4. It remains to show that ?i, p i+1 ? p i ? N. This is true whenever the p i values both correspond to ? i 's (resp. µ i 's, ? i 's) in the sequence P : indeed consecutive ? i 's (resp. µ i 's, ? i 's) belong to consecurive buckets of size g ? N/2, and hence are at most N apart. Hence we only need to prove something for edge cases, i.e. whenever p i or p i+1 is equal to either s LM or s M R. This leads to four cases. Case 1 : p i = s LM, We have already shown in Lemma D.6 that P is strictly increasing. We continue by proving the third point. It is clear that P i forms an interval, by construction of the P i 's; and since ? 0 ? d ? N/2, and ? 0 ? N + 1 ? d ? N + 1 ? N/2, we have that, vol.3
, In the remainder of the proof, we show that, roughly speaking, the partition induced by the children of node T must be a refinement of P. Hence we will be able to deduce that they satisfy the same three properties, which will conclude the proof, Recall that r a , r b denote records with respective value a and b
, Let r denote a record such that val(r), a, b belong to distinct P i 's. Then for every order on records compatible with Q, must match the real order on r, r a, vol.8
, Since a < b there are only three possibilities for the position of x relative to a and b: x < a, a < x < b or b < x. Case 1 : x < a. We have x ? ? 0 by construction of P, Let x = val(r)