Data mining, Hypergraph Transversals, and Machine Learning

Summary: Maps discovery of maximally-specific “interesting” sentences in databases to the hypergraph-transversal problem, enabling formal complexity analysis. Analyzes two algorithms—one efficient for small patterns (improves a special-case transversal), the other uses transversal subroutines with near-optimal bounds and ties results to exact learning. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1117
Venue: PODS
Year: 1997
Pagerank: 5.8364579e-05
Overall Rank: 6,578 | 54.87%
DOI: 10.1145/263661.263684

Incoming Non-self Citations Over Time

Authors

1. Dimitrios Gunopulos (IBM)
2. Roni Khardon (Harvard University)
3. Heikki Mannila (University of Helsinki)
4. Hannu Toivonen (University of Helsinki)

BibTeX Citation

@inproceedings{gunopulos_pods97,
        address = {New York, NY, USA},
        series = {{PODS} '97},
        title = {{Data mining, Hypergraph Transversals, and Machine Learning}},
        url = {https://dl.acm.org/doi/10.1145/263661.263684},
        doi = {10.1145/263661.263684},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gunopulos, Dimitrios and Khardon, Roni and Mannila, Heikki and Toivonen, Hannu},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
304	Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications	1998	SIGMOD	0.00021917388
9,212	Feasible Itemset Distributions in Data Mining: Theory and Application	2003	PODS	5.3058708e-05
12,812	How to Quickly Find a Witness	2003	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,724	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD
2	558	An Efficient Algorithm for Mining Association Rules in Large Databases	1995	VLDB
3	7,522	The Complexity of Mining Maximal Frequent Subgraphs	2013	PODS
4	11,188	Language-Model Based Informed Partition of Databases to Speed Up Pattern Mining	2024	SIGMOD
5	14,219	Data Mining Techniques	1996	SIGMOD
6	7,466	Mining Attribute-structure Correlated Patterns in Large Attributed Graphs	2012	VLDB
7	11,067	Machine Learning for Graph Data Management and Query Processing	2025	VLDB
8	9,212	Feasible Itemset Distributions in Data Mining: Theory and Application	2003	PODS
9	13,712	Database Systems Research on Data Mining	2010	SIGMOD
10	9,703	Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs	2017	SIGMOD