Back to papers
Deciding Monotone Duality and Identifying Frequent Itemsets in Quadratic Logspace
Summary: Shows monotone duality/hypergraph transversal testing is in DSPACE[log^2 n] via Boros–Makino problem decomposition, giving a quadratic‑logspace algorithm. Consequence: given maximal frequent and minimal infrequent itemsets, existence of any other (in)frequent itemset decidable in quadratic logspace.
(summarized by gpt-5-mini on Feb 09 2026)
- Paper ID
- 1596
- Venue
- PODS
- Year
- 2013
- Pagerank
- 6.0169698e-05
- Overall Rank
- 4,651 | 67.68%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
Outgoing Citations (Sorted by Pagerank)
Showing 0 of 0 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 9,062 |
Feasible Itemset Distributions in Data Mining: Theory and Application |
2003 |
PODS |
4.3997447e-05 |
| 12,039 |
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity |
2013 |
PODS |
4.1905499e-05 |
| 4,451 |
False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams |
2004 |
VLDB |
6.172063e-05 |
| 4,805 |
Optimization of Constrained Frequent Set Queries with 2-variable Constraints |
1999 |
SIGMOD |
5.9050441e-05 |
| 10,000 |
A Unifying Algorithm for Hierarchical Queries |
2026 |
PODS |
4.1905499e-05 |
| 9,564 |
Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs |
2017 |
SIGMOD |
4.3212967e-05 |
| 5,041 |
The Complexity of Mining Maximal Frequent Subgraphs |
2013 |
PODS |
5.7356447e-05 |
| 2,343 |
Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract) |
1989 |
PODS |
8.9968717e-05 |
| 11,441 |
New Algorithms for Monotone Classification |
2021 |
PODS |
4.1905499e-05 |
| 8,309 |
Computational Complexity of Itemset Frequency Satisfiability |
2004 |
PODS |
4.5392079e-05 |