Ranked Enumeration of Minimal Triangulations

Summary: First algorithm to rank-enumerate proper tree decompositions (minimal triangulations) for a broad class of cost functions beyond width/fill-in, yielding many candidate decompositions for specialized or learned objectives. Achieves polynomial-delay under the poly‑MS assumption or constant width; empirically validated on queries, Bayesian networks, and standard benchmarks against prior methods. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h089e81fc47db35b2
Venue: PODS
Year: 2019
Pagerank: 5.3917406e-05
Overall Rank: 8,098 | 45.58%
DOI: 10.1145/3294052.3319678

Incoming Non-self Citations Over Time

Authors

1. Noam Ravid (Technion)
2. Dori Medini (Technion)
3. Benny Kimelfeld (Technion)

BibTeX Citation

@inproceedings{ravid_pods19,
        address = {New York, NY, USA},
        series = {{PODS} '19},
        title = {{Ranked Enumeration of Minimal Triangulations}},
        url = {https://dl.acm.org/doi/10.1145/3294052.3319678},
        doi = {10.1145/3294052.3319678},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ravid, Noam and Medini, Dori and Kimelfeld, Benny},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,105	Soft and Constrained Hypertree Width	2025	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
391	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019245666
684	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00014791388
3,909	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	6.9287689e-05
8,160	Optimizing and Parallelizing Ranked Enumeration	2011	VLDB	5.3863592e-05
9,527	Efficiently Enumerating Minimal Triangulations	2017	PODS	5.1666108e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,926	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS
2	7,801	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS
3	5,487	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB
4	7,438	Efficient Computation of Quantiles over Joins	2023	PODS
5	10,798	Subgraph Enumeration: Beyond Tree Decomposition	2026	VLDB
6	10,519	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
7	8,203	On Tree-Based Techniques for Query Evaluation	1992	PODS
8	2,593	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
9	2,728	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS
10	9,527	Efficiently Enumerating Minimal Triangulations	2017	PODS