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: 1772
Venue: PODS
Year: 2019
Pagerank: 5.5181056e-05
Overall Rank: 7,923 | 45.65%
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
10,653	Soft and Constrained Hypertree Width	2025	PODS	5.093636e-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
382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019546431
673	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00015095061
3,841	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	7.0808098e-05
8,013	Optimizing and Parallelizing Ranked Enumeration	2011	VLDB	5.5073426e-05
9,337	Efficiently Enumerating Minimal Triangulations	2017	PODS	5.2876688e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,759	The Power of Tree Projections: Local Consistency, Greedy Algorithms, and Larger Islands of Tractability	2010	PODS
2	6,412	Ranked Enumeration of Join Queries with Projections	2022	VLDB
3	7,640	Tractable Lineages on Treelike Instances: Limits and Extensions	2016	PODS
4	5,593	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB
5	7,286	Efficient Computation of Quantiles over Joins	2023	PODS
6	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
7	8,035	On Tree-Based Techniques for Query Evaluation	1992	PODS
8	2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
9	2,678	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS
10	9,337	Efficiently Enumerating Minimal Triangulations	2017	PODS