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.2892451e-05
Overall Rank: 1,970 | 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
519	Query by Output	2009	SIGMOD	0.00016937515
1,183	SQAK: Doing More with Keywords	2008	SIGMOD	0.0001161406
2,462	DBLife: A Community Information Management Platform for the Database Research Community	2007	CIDR	8.427832e-05
2,580	Tuning Schema Matching Software using Synthetic Scenarios	2005	VLDB	8.2677597e-05
3,419	Data Profiling – A Tutorial	2017	SIGMOD	7.3175997e-05
4,307	Discovering Topical Structures of Databases	2008	SIGMOD	6.6723067e-05
7,465	Reducing Ambiguity in Json Schema Discovery	2021	SIGMOD	5.5187501e-05
8,575	Information Theory for Data Management	2010	SIGMOD	5.3109376e-05
11,391	FDepHunter: Harnessing Negative Examples to Expose Fakes and Reveal Ghosts	2025	VLDB	4.9769913e-05
11,879	Statistical Schema Learning using Occam's Razor	2022	SIGMOD	4.9769913e-05
12,844	Information Theory For Data Management	2009	VLDB	4.9769913e-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.00064391979
32	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00049714561
60	The Merge/Purge Problem for Large Databases	1995	SIGMOD	0.00039440583
95	Potter's Wheel: An Interactive Data Cleaning System	2001	VLDB	0.00034367518
307	Eliminating Fuzzy Duplicates in Data Warehouses	2002	VLDB	0.00021489374
401	A Case for Fractured Mirrors	2002	VLDB	0.00019102313
427	Translating Web Data	2002	VLDB	0.00018475614
435	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.0001831946
2,823	Vertical Partitioning for Database Design: A Graphical Algorithm	1989	SIGMOD	7.9667062e-05
3,191	Information Dependencies	2000	PODS	7.5488555e-05
3,502	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS	7.2490781e-05
5,434	Materialized View and Index Selection Tool for Microsoft SQL Server 2000	2001	SIGMOD	6.1303275e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	603	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD
2	3,288	Comprehensive Approach to the Design of Relational Database Schemes	1984	VLDB
3	209	Dependency Inference	1987	VLDB
4	14,819	Information Theoretic Aspects Of Data Bases	1983	PODS
5	6,648	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD
6	10,804	Storage-Centric Relation Design via High-Quality Approximate Functional Dependencies	2026	VLDB
7	728	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB
8	7,289	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
9	12,975	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