Any-k: Ranked enumeration for Dynamic Programming

on YouTube ↗32m

" summary

Presents a concrete algorithmic framework that turns dynamic programs into DAG shortest‑path problems so ranked enumeration returns the k‑th best solution with preprocessing linear in the DP state space and per‑answer overhead polylogarithmic; relies on semirings with a selective plus operator (tropical, Viterbi, Boolean) and introduces Any‑k Part+ which lowers the log k factor to log n under strong subset monotonicity. Maps conjunctive queries to these DAGs, extends to tree‑DP, and an implementation yields the first answer ~500× faster and often beats join‑then‑sort even for full enumeration.

AI-written summary · about

" chapters (9)

1. 0:00Introduction to ranked enum
2. 2:00Dynamic programming as a DAG
3. 4:38Semirings and monotonicity
4. 8:51Algorithmic strategies
5. 12:39Improving performance
6. 17:01History and evolution
7. 19:40Application to query plans
8. 24:30Experimental results
9. 29:25Discussion and conclusion

" related talks

• 44mEfficient Enumeration Algorithms via CircuitsAntoine Amarili · Probabilistic Circuits and Logic 2023
• 33mLinear and sublinear algorithms for graphlet samplingMarco Bressan · Extroverted Sublinear Algorithms 2024
• 01h 09mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: INofar Carmeli · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 01h 06mSampling in Query Evaluation 1Marcelo Arenas · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 03mQuery Optimization and Evaluation 3: Variable Elimination and Tensor DecompositionHung Ngo · Logic and Algorithms in Database Theory and AI Boot Camp
• 39mMassively Parallel Evaluation of Relational Queries IIXiao Hu, Paris Koutris · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 41mOptimizing Relational Programs IRemy Wang · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 43mResizable SketchesRasmus Pagh · Sketching and Algorithm Design 2023