Towards Better Bounds for Finding Quasi-Identifiers *

Summary: Improves bounds for epsilon-separation keys (quasi-identifiers): Θ(m/√ε) uniform-sampling suffices, beating Motwani–Xu’s Θ(m/ε) baseline and speeding discovery. Provides tight uniform-sampling limits and sketching costs: strong failure requires Θ(√(m/ε)) samples; constant δ needs Ω(√(log m/ε)); coordinate-sketching uses Ω(mk log(1/ε)) space, vs Θ(mk/(αε^2)) with sampling. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1919
Venue: PODS
Year: 2023
Pagerank: 5.093636e-05
Overall Rank: 11,368 | 22.01%
DOI: 10.1145/3584372.3588668

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Ryan Hildebrant (University of California Irvine)
2. Quoc-Tung Le (CNRS; Claude Bernard Lyon 1 University; Ecole Normale Superieure de Lyon; INRIA; University of Lyon)
3. Duy-Hoang Ta (National University of Singapore)
4. Hoa T. Vu (San Diego State University)

BibTeX Citation

@inproceedings{hildebrant_pods23,
        address = {New York, NY, USA},
        series = {{PODS} '23},
        title = {{Towards Better Bounds for Finding Quasi-Identifiers *}},
        url = {https://dl.acm.org/doi/10.1145/3584372.3588668},
        doi = {10.1145/3584372.3588668},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hildebrant, Ryan and Le, Quoc-Tung and Ta, Duy-Hoang and Vu, Hoa T.},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
158	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00028199923
306	Eliminating Fuzzy Duplicates in Data Warehouses	2002	VLDB	0.00021839661
7,918	Subspace Exploration: Bounds on Projected Frequency Estimation	2021	PODS	5.5181056e-05
7,926	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS	5.5181056e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,194	Towards Tight Bounds for the Streaming Set Cover Problem	2016	PODS
2	6,753	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
3	82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
4	7,091	Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald	2024	PODS
5	5,599	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS
6	4,472	Relative Error Streaming Quantiles	2021	PODS
7	7,926	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS
8	2,443	Independent Range Sampling	2014	PODS
9	10,168	Tight Lower Bounds for l2 Sampling	2026	PODS
10	777	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS