Efficient Differential Dependency Discovery

Summary: Introduces 'diff-set', a compact encoding of value differences, and a set-cover-based miner for differential dependencies (DDs) that generalize FDs and capture similarity/dissimilarity. Diff-set construction plus non-minimal pruning yields orders-of-magnitude speedups vs prior DD/RFD discovery. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h6179f7e94b51fcdd
Venue: VLDB
Year: 2024
Pagerank: 5.0789354e-05
Overall Rank: 10,106 | 32.06%
DOI: 10.14778/3654621.3654624

Incoming Non-self Citations Over Time

Authors

1. Shulei Kuang (Fudan University)
2. Honghui Yang (Fudan University)
3. Zijing Tan (Fudan University)
4. Shuai Ma (Beihang University)

BibTeX Citation

@article{kuang_vldb24,
        title = {{Efficient Differential Dependency Discovery}},
        author = {Kuang, Shulei and Yang, Honghui and Tan, Zijing and Ma, Shuai},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {7},
        pages = {1552--1564},
        doi = {10.14778/3654621.3654624},
        url = {https://doi.org/10.14778/3654621.3654624},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,529	Minimum Change ≠ Best Cleaning: Parallel and Incremental Error Detection under Integrity Constraints	2026	SIGMOD	4.9793485e-05
11,254	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 29 of 29 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
104	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00033690989
188	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD	0.00025872962
500	Dependencies Revisited for Improving Data Quality	2008	PODS	0.00017280722
603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD	0.00015699254
697	NADEEF: A Commodity Data Cleaning System	2013	SIGMOD	0.00014694048
727	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB	0.00014443394
1,488	Efficient Discovery of Approximate Dependencies	2018	VLDB	0.00010517437
1,619	Efficient Denial Constraint Discovery with Hydra	2018	VLDB	0.00010055625
1,887	Sequential Dependencies	2009	VLDB	9.4321643e-05
1,971	Discovery of Approximate (and Exact) Denial Constraints	2020	VLDB	9.2873596e-05
2,055	Combining Quantitative and Logical Data Cleaning	2016	VLDB	9.1128336e-05
2,443	Approximate Denial Constraints	2020	VLDB	8.4586656e-05
3,360	Cleaning Denial Constraint Violations through Relaxation	2020	SIGMOD	7.3767115e-05
3,418	Data Profiling – A Tutorial	2017	SIGMOD	7.3210362e-05
3,422	UGuide – User-Guided Discovery of FD-Detectable Errors	2017	SIGMOD	7.3138834e-05
4,067	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	6.8216078e-05
4,465	Effective and Complete Discovery of Order Dependencies via Set-based Axiomatization	2017	VLDB	6.5873563e-05
4,843	Pattern Functional Dependencies for Data Cleaning	2020	VLDB	6.3839159e-05
5,130	Distributed implementations of dependency discovery algorithms	2019	VLDB	6.2603084e-05
5,280	Fast Approximate Denial Constraint Discovery	2023	VLDB	6.1992888e-05
5,522	MDedup: Duplicate Detection with Matching Dependencies	2020	VLDB	6.0956156e-05
6,171	Fundamentals of Order Dependencies	2012	VLDB	5.8623235e-05
6,424	Expressiveness and Complexity of Order Dependencies	2013	VLDB	5.7895404e-05
6,855	Fast Incremental Discovery of Pointwise Order Dependencies	2020	VLDB	5.6642528e-05
7,287	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD	5.5658087e-05
8,263	Discovery and Ranking of Embedded Uniqueness Constraints	2019	VLDB	5.3657304e-05
8,507	DataProf: Semantic Profiling for Iterative Data Cleansing and Business Rule Acquisition	2018	SIGMOD	5.3269911e-05
9,120	Discovering Similarity Inclusion Dependencies	2023	SIGMOD	5.2259037e-05
9,608	Discovering Top-k Rules using Subjective and Objective Criteria	2023	SIGMOD	5.1527671e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	209	Dependency Inference	1987	VLDB
2	2,125	Discovery of Genuine Functional Dependencies from Relational Data with Missing Values	2018	VLDB
3	6,910	Efficient Discovery of XML Data Redundancies	2006	VLDB
4	727	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB
5	7,243	Discovering Graph Functional Dependencies	2018	SIGMOD
6	9,958	Discovering Functional Dependencies through Hitting Set Enumeration	2024	SIGMOD
7	9,107	DAFDiscover: Robust Mining Algorithm for Dynamic Approximate Functional Dependencies on Dirty Data	2024	VLDB
8	603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD
9	7,287	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
10	11,254	Efficient Discovery of Relaxed Functional Dependencies	2025	VLDB