mlsanityData to 7 Oct 2026

Learning-Augmented Priority Queues

arXiv 2406.04793 ↗First posted 7 Jun 2024cs.DS cs.AI cs.LGcited by 7

Not on the map. Why?

Abstract (arXiv)

Priority queues are one of the most fundamental and widely used data structures in computer science. Their primary objective is to efficiently support the insertion of new elements with assigned priorities and the extraction of the highest priority element. In this study, we investigate the design of priority queues within the learning-augmented framework, where algorithms use potentially inaccurate predictions to enhance their worst-case performance. We examine three prediction models spanning different use cases, and show how the predictions can be leveraged to enhance the performance of priority queue operations. Moreover, we demonstrate the optimality of our solution and discuss some possible applications.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Builds on 39 of its 90 references that are in the map. First posted on arXiv 7 Jun 2024.

Builds on

39 of 90 references.

References · 39

  1. 2018Competitive caching with machine learned advicecited by 194
  2. 2017The Case for Learned Index Structurescited by 188
  3. 2020Algorithms with Predictionscited by 152
  4. 2016OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networkscited by 109
  5. 2020The Primal-Dual method for Learning Augmented Algorithmscited by 78
  6. 2020Online metric algorithms with untrusted predictionscited by 74
  7. 2020Secretary and Online Matching Problems with Machine Learned Advicecited by 71
  8. 2015Simple, Robust and Optimal Ranking from Pairwise Comparisonscited by 68
  9. 2021Faster Matchings via Learned Dualscited by 56
  10. 2022Faster Fundamental Graph Algorithms via Learned Predictionscited by 42
  11. 2022Learning Augmented Binary Search Treescited by 31
  12. 2018Approximate Ranking from Pairwise Comparisonscited by 21
27 more
  1. 2022Customizing ML Predictions for Online Algorithmscited by 21
  2. 2021Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Boundscited by 20
  3. 2022Parsimonious Learning-Augmented Cachingcited by 19
  4. 2020Learning-Augmented Weighted Pagingcited by 17
  5. 2023Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysiscited by 16
  6. 2023Sorting with Predictionscited by 14
  7. 2021Robust Learning-Augmented Caching: An Experimental Studycited by 12
  8. 2024Algorithms for Caching and MTS with reduced number of predictionscited by 12
  9. 2021Logarithmic Regret from Sublinear Hintscited by 11
  10. 2022Paging with Succinct Predictionscited by 10
  11. 2018Foundations of Comparison-Based Hierarchical Clusteringcited by 7
  12. 2023Minimalistic Predictions to Schedule Jobs with Online Precedence Constraintscited by 7
  13. 2024Non-clairvoyant Scheduling with Partial Predictionscited by 7
  14. 2017Comparison Based Nearest Neighbor Searchcited by 6
  15. 2022On Preemption and Learning in Stochastic Schedulingcited by 6
  16. 2023Metric Clustering and MST with Strong and Weak Distance Oraclescited by 6
  17. 2024Robust Learning-Augmented Dictionariescited by 6
  18. 2023Online List Labeling with Predictionscited by 5
  19. 2021Learning with Comparison Feedback: Online Estimation of Sample Statisticscited by 4
  20. 2014A Back-to-Basics Empirical Study of Priority Queuescited by 3
  21. 2020Near-Optimal Comparison Based Clusteringcited by 3
  22. 2023Addressing Bias in Online Selection with Limited Budget of Comparisonscited by 3
  23. 2024Accelerating Matroid Optimization through Fast Imprecise Oraclescited by 3
  24. 2018Comparison-Based Random Forestscited by 2
  25. 2017Cost estimation of a fixed network deployment over an urban territorycited by 1
  26. 2022Agent-based modeling and simulation for malware spreading in D2D networkscited by 1
  27. 2023A Comparison of Dijkstra's Algorithm Using Fibonacci Heaps, Binary Heaps, and Self-Balancing Binary Treescited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 3.

7 papers.

  1. 2025On Tradeoffs in Learning-Augmented Algorithmscited by 7
  2. 2025Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Searchcited by 4
  3. 2025Incremental Approximate Single-Source Shortest Paths with Predictionscited by 3
  4. 2025Privacy-Preserving Learning-Augmented Data Structurescited by 0
  5. 2026Incremental Strongly Connected Components with Predictionscited by 0
  6. 2026Resilient Byzantine Agreement with Predictionscited by 0
  7. 2026Augmented Hypothesis Testing with Persona-Based LLM Simulationscited by 0