Scalable Discovery of Unique Column Combinations

Summary: Ducc discovers all unique and non-unique column combinations by framing uniqueness as graph coloring and combining hybrid lattice traversal with row-based pruning. Parallel scale-up/out enables million-row, hundreds-attribute datasets, outperforming prior methods by up to 631×. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h44e03e140ef1dad4
Venue: VLDB
Year: 2014
Pagerank: 6.7151469e-05
Overall Rank: 4,226 | 71.60%
DOI: 10.14778/2732240.2732247
PDF: Download (CC BY-NC-ND 3.0)

Incoming Non-self Citations Over Time

Authors

1. Arvid Heise (Hasso Plattner Institute)
2. Jorge-Arnulfo Quiane-Ruiz (Qatar Computing Research Institute)
3. Ziawasch Abedjan (Hasso Plattner Institute)
4. Anja Jentzsch (Hasso Plattner Institute)
5. Felix Naumann (Hasso Plattner Institute)

BibTeX Citation

@article{heise_vldb14,
        title = {{Scalable Discovery of Unique Column Combinations}},
        author = {Heise, Arvid and Quiane-Ruiz, Jorge-Arnulfo and Abedjan, Ziawasch and Jentzsch, Anja and Naumann, Felix},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {4},
        pages = {301--312},
        doi = {10.14778/2732240.2732247},
        url = {https://doi.org/10.14778/2732240.2732247},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,394	Data Profiling with Metanome	2015	VLDB	0.00010791559
1,488	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010513265
1,620	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	0.00010050865
1,972	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.2829634e-05
3,419	Data Profiling – A Tutorial	2017	SIGMOD	7.3175997e-05
3,421	UGuide – User-Guided Discovery of FD-Detectable Errors	2017	SIGMOD	7.3120636e-05
4,342	Possible and Certain SQL Keys	2015	VLDB	6.6478954e-05
5,279	MATE: Multi-Attribute Table Extraction	2022	VLDB	6.1973533e-05
5,283	Fast Approximate Denial Constraint Discovery	2023	VLDB	6.1963542e-05
6,860	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.6615714e-05
6,924	CtxPipe: Context-aware Data Preparation Pipeline Construction for Machine Learning	2024	SIGMOD	5.6405901e-05
8,211	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB	5.3761077e-05
8,269	Discovery and Ranking of Embedded Uniqueness Constraints	2019	VLDB	5.3631903e-05
8,764	Exploratory Training: When Annotators Learn About Data	2023	SIGMOD	5.2815275e-05
9,626	Interactive and Deterministic Data Cleaning: A Tossed Stone Raises a Thousand Ripples	2016	SIGMOD	5.1477881e-05
11,327	How and Why False Denial Constraints are Discovered	2025	VLDB	4.9769913e-05
12,025	A Demonstration of RELIC: A System for REtrospective Lineage InferenCe of Data Workflows	2021	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
70	The End of an Architectural Era (It’s Time for a Complete Rewrite)	2007	VLDB	0.00037851432
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027827605
501	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017273167
1,031	On Generating Near-Optimal Tableaux for Conditional Functional Dependencies	2008	VLDB	0.00012399252
1,291	Extending Dependencies with Conditions	2007	VLDB	0.00011150915
1,533	On Multi-Column Foreign Key Discovery	2010	VLDB	0.00010328081
1,663	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.942673e-05
2,294	GORDIAN: Efficient and Scalable Discovery of Composite Keys	2006	VLDB	8.6831732e-05
2,904	Estimating the Confidence of Conditional Functional Dependencies	2009	SIGMOD	7.87641e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,053	Crowd-Based Deduplication: An Adaptive Approach	2015	SIGMOD
2	10,311	Data Chunk Compaction in Vectorized Execution	2025	SIGMOD
3	3,426	Modeling and Querying Possible Repairs in Duplicate Detection	2009	VLDB
4	7,716	Scalable Column Concept Determination for Web Tables Using Large Knowledge Bases	2013	VLDB
5	6,528	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB
6	885	Framework for Evaluating Clustering Algorithms in Duplicate Detection	2009	VLDB
7	2,949	Distributed Data Deduplication	2016	VLDB
8	3,909	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD
9	8,211	Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery	2020	VLDB
10	8,269	Discovery and Ranking of Embedded Uniqueness Constraints	2019	VLDB