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: 3625
Venue: SIGMOD
Year: 2004
Pagerank: 9.4928569e-05
Overall Rank: 1,913 | 86.88%
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
517	Query by Output	2009	SIGMOD	0.00017169735
1,182	SQAK: Doing More with Keywords	2008	SIGMOD	0.00011778765
2,405	DBLife: A Community Information Management Platform for the Database Research Community	2007	CIDR	8.6217909e-05
2,538	Tuning Schema Matching Software using Synthetic Scenarios	2005	VLDB	8.4548936e-05
3,387	Data Profiling – A Tutorial	2017	SIGMOD	7.4534663e-05
4,228	Discovering Topical Structures of Databases	2008	SIGMOD	6.819835e-05
7,327	Reducing Ambiguity in Json Schema Discovery	2021	SIGMOD	5.6435519e-05
8,405	Information Theory for Data Management	2010	SIGMOD	5.4323037e-05
11,020	FDepHunter: Harnessing Negative Examples to Expose Fakes and Reveal Ghosts	2025	VLDB	5.093636e-05
11,564	Statistical Schema Learning using Occam's Razor	2022	SIGMOD	5.093636e-05
12,548	Information Theory For Data Management	2009	VLDB	5.093636e-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.0006567919
31	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00050347119
58	The Merge/Purge Problem for Large Databases	1995	SIGMOD	0.00040116748
94	Potter's Wheel: An Interactive Data Cleaning System	2001	VLDB	0.00034616103
306	Eliminating Fuzzy Duplicates in Data Warehouses	2002	VLDB	0.00021839661
394	A Case for Fractured Mirrors	2002	VLDB	0.00019306179
416	Translating Web Data	2002	VLDB	0.00018877803
432	Mining Database Structure; Or, How to Build a Data Quality Browser	2002	SIGMOD	0.00018572055
2,797	Vertical Partitioning for Database Design: A Graphical Algorithm	1989	SIGMOD	8.1135051e-05
3,141	Information Dependencies	2000	PODS	7.7170066e-05
3,432	An Information-Theoretic Approach to Normal Forms for Relational and XML Data	2003	PODS	7.4182332e-05
5,307	Materialized View and Index Selection Tool for Microsoft SQL Server 2000	2001	SIGMOD	6.2728074e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,456	Automatic Discovery of Attributes in Relational Databases	2011	SIGMOD
2	618	A Hybrid Approach to Functional Dependency Discovery	2016	SIGMOD
3	3,222	Comprehensive Approach to the Design of Relational Database Schemes	1984	VLDB
4	203	Dependency Inference	1987	VLDB
5	14,504	Information Theoretic Aspects Of Data Bases	1983	PODS
6	6,516	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD
7	729	Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms	2015	VLDB
8	7,187	Discovery Algorithms for Embedded Functional Dependencies	2020	SIGMOD
9	12,679	On Redundancy vs Dependency Preservation in Normalization: An Information-Theoretic Study of 3NF	2006	PODS
10	3,609	Embedded Functional Dependencies and Data-completeness Tailored Database Design	2019	VLDB