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.0227856e-05
- Overall Rank
- 4,653 | 67.64%
- 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,064 |
Feasible Itemset Distributions in Data Mining: Theory and Application |
2003 |
PODS |
4.4039656e-05 |
| 12,031 |
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity |
2013 |
PODS |
4.1945683e-05 |
| 4,449 |
False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams |
2004 |
VLDB |
6.1780147e-05 |
| 4,919 |
Optimization of Constrained Frequent Set Queries with 2-variable Constraints |
1999 |
SIGMOD |
5.8256934e-05 |
| 10,001 |
A Unifying Algorithm for Hierarchical Queries |
2026 |
PODS |
4.1945683e-05 |
| 9,565 |
Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs |
2017 |
SIGMOD |
4.3254416e-05 |
| 5,043 |
The Complexity of Mining Maximal Frequent Subgraphs |
2013 |
PODS |
5.7411631e-05 |
| 2,339 |
Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract) |
1989 |
PODS |
9.005745e-05 |
| 11,438 |
New Algorithms for Monotone Classification |
2021 |
PODS |
4.1945683e-05 |
| 8,315 |
Computational Complexity of Itemset Frequency Satisfiability |
2004 |
PODS |
4.5435639e-05 |