Towards Better Bounds for Finding Quasi-Identifiers
Ryan Hildebrant, Quoc-Tung Le, Hoang Ta, Hoa T. Vu · 2023
We revisit the problem of finding small ε-separation keys introduced by Motwani and Xu (2008). In this problem, the input is a data set consisting of m-dimensional tuples {x1,x2,...,xn}. The goal is to find a small subset of coordinates that separates at least (1-ε)(n2) pairs of tuples. When n is large, they provided a fast algorithm that runs on Θ(m/ε) tuples sampled uniformly at random. We show that the sample size can be improved to Θ(m/√ε). Our algorithm also enjoys a faster running time.