Towards Better Bounds for Finding Quasi-Identifiers

Ryan Hildebrant, Quoc-Tung Le, Duy-Hoang Ta +1

We revisit the problem of finding small $\epsilon$-separation keys introduced by Motwani and Xu (2008). In this problem, the input is $m$-dimensional tuples $x_1,x_2,\dots ,x_n$. The goa…