Information-Theoretic Tools for Mining Database Structure from Large Data Sets

Summary: Information-theoretic summaries infer database structure when the model is unknown or incomplete, robust to noise, missing values, and duplicates. Scalable algorithms extract these summaries from large categorical data; ranking functional dependencies by redundancy guides vertical decompositions that boost information content, with real-data validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h7ac480a6dc38e861
Venue: SIGMOD
Year: 2004
Pagerank: 9.2935435e-05
Overall Rank: 1,969 | 86.77%
DOI: 10.1145/1007568.1007650

Incoming Non-self Citations Over Time

Authors

1. Periklis Andritsos (University of Toronto)
2. Renée J. Miller (University of Toronto)
3. Panayiotis Tsaparas (Sapienza University)

BibTeX Citation

@inproceedings{andritsos_sigmod04,
        title = {{Information-Theoretic Tools for Mining Database Structure from Large Data Sets}},
        author = {Andritsos, Periklis and Miller, Renée J. and Tsaparas, Panayiotis},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007650},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007650},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
518	Query by Output	2009	SIGMOD	0.00016944862
1,182	SQAK: Doing More with Keywords	2008	SIGMOD	0.0001161771
2,462	DBLife: A Community Information Management Platform for the Database Research Community	2007	CIDR	8.4317833e-05
2,580	Tuning Schema Matching Software using Synthetic Scenarios	2005	VLDB	8.2716518e-05
3,418	Data Profiling – A Tutorial	2017	SIGMOD	7.3210362e-05
4,306	Discovering Topical Structures of Databases	2008	SIGMOD	6.6754157e-05
7,461	Reducing Ambiguity in Json Schema Discovery	2021	SIGMOD	5.5213638e-05
8,568	Information Theory for Data Management	2010	SIGMOD	5.3134519e-05
11,385	FDepHunter: Harnessing Negative Examples to Expose Fakes and Reveal Ghosts	2025	VLDB	4.9793485e-05
11,873	Statistical Schema Learning using Occam's Razor	2022	SIGMOD	4.9793485e-05
12,838	Information Theory For Data Management	2009	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
13	Mining Association Rules between Sets of Items in Large Databases	1993	SIGMOD	0.00064420972
32	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00049737458
60	The Merge/Purge Problem for Large Databases	1995	SIGMOD	0.000394583
95	Potter's Wheel: An Interactive Data Cleaning System	2001	VLDB	0.00034382643
307	Eliminating Fuzzy Duplicates in Data Warehouses	2002	VLDB	0.00021499031
401	A Case for Fractured Mirrors	2002	VLDB	0.00019108281
426	Translating Web Data	2002	VLDB	0.00018483901
435	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.0001832766
2,823	Vertical Partitioning for Database Design: A Graphical Algorithm	1989	SIGMOD	7.9702688e-05
3,190	Information Dependencies	2000	PODS	7.5524237e-05
3,502	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS	7.2525074e-05
5,430	Materialized View and Index Selection Tool for Microsoft SQL Server 2000	2001	SIGMOD	6.1331043e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD
2	3,287	Comprehensive Approach to the Design of Relational Database Schemes	1984	VLDB
3	209	Dependency Inference	1987	VLDB
4	14,814	Information Theoretic Aspects Of Data Bases	1983	PODS
5	6,643	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD
6	10,794	Storage-Centric Relation Design via High-Quality Approximate Functional Dependencies	2026	VLDB
7	727	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB
8	7,287	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
9	12,969	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS
10	3,475	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB