Document Open Access Logo

Algorithm Engineering for Sorting and Searching, and All That (Invited Talk)

Author Stefan Edelkamp

PDF
Thumbnail PDF

File

LIPIcs.SEA.2020.2.pdf
  • Filesize: 268 kB
  • 3 pages

Document Identifiers

Author Details

Stefan Edelkamp
  • University of Koblenz, Postfach 201 602, 56016 Koblenz, Germany

Acknowledgements

I want to thank all co-authors of my papers.

Cite As Get BibTex

Stefan Edelkamp. Algorithm Engineering for Sorting and Searching, and All That (Invited Talk). In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 2:1-2:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SEA.2020.2

Abstract

We look at several proposals to engineer the set of fundamental searching and sorting algorithms. Aspects are improving locality of disk access and cache access, the efficiency tuning by reducing the number of branch mispredictions, and reducing at leading factors hidden in the Big-Oh notation. These studies in algorithm engineering, in turn, lead to exiting new algorithm designs. On the practical side, we will establish that efficient sorting and searching algorithms are in tight collaboration, as sorting is used for finding duplicates in disk-based search, and heap structures designed for efficient graph search can be exploited in classical and adaptive sorting. We indicate the effects of engineered sorting and searching for combined task and motion planning.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Sorting
  • Searching
  • Algorithm Engineering

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Stefan Edelkamp. External-memory state space search. In Lasse Kliemann and Peter Sanders, editors, Algorithm Engineering - Selected Results and Surveys, volume 9220 of LNCS, pages 185-225. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-49487-6_6.
  2. Stefan Edelkamp. Improving the cache-efficiency of shortest path search. In Gabriele Kern-Isberner, Johannes Fürnkranz, and Matthias Thimm, editors, KI 2017, volume 10505 of LNCS, pages 99-113. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-67190-1_8.
  3. Stefan Edelkamp and Tristan Cazenave. Improved diversity in nested rollout policy adaptation. In Gerhard Friedrich, Malte Helmert, and Franz Wotawa, editors, KI 2016, volume 9904 of LNCS, pages 43-55. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-46073-4_4.
  4. Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen. Two constant-factor-optimal realizations of adaptive heapsort. In Costas S. Iliopoulos and William F. Smyth, editors, IWOCA 2011, volume 7056 of LNCS, pages 195-208. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-25011-8_16.
  5. Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen. The weak-heap data structure: Variants and applications. J. Discrete Algorithms, 16:187-205, 2012. URL: https://doi.org/10.1016/j.jda.2012.04.010.
  6. Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen. Weak heaps engineered. J. Discrete Algorithms, 23:83-97, 2013. URL: https://doi.org/10.1016/j.jda.2013.07.002.
  7. Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen. An in-place priority queue with o(1) time for push and lg n + O(1) comparisons for pop. In Lev D. Beklemishev and Daniil V. Musatov, editors, CSR 2015, volume 9139 of LNCS, pages 204-218. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-20297-6_14.
  8. Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen. Heap construction - 50 years later. Comput. J., 60(5):657-674, 2017. URL: https://doi.org/10.1093/comjnl/bxw085.
  9. Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen. Optimizing binary heaps. Theory Comput. Syst., 61(2):606-636, 2017. URL: https://doi.org/10.1007/s00224-017-9760-2.
  10. Stefan Edelkamp, Max Gath, Tristan Cazenave, and Fabien Teytaud. Algorithm and knowledge engineering for the TSPTW problem. In CISched 2013, pages 44-51. IEEE, 2013. URL: https://doi.org/10.1109/SCIS.2013.6613251.
  11. Stefan Edelkamp, Peter Kissmann, and Martha Rohte. Symbolic and explicit search hybrid through perfect hash functions - A case study in connect four. In Steve A. Chien, Minh Binh Do, Alan Fern, and Wheeler Ruml, editors, ICAPS 2014. AAAI, 2014. URL: http://www.aaai.org/ocs/index.php/ICAPS/ICAPS14/paper/view/7921.
  12. Stefan Edelkamp, Morteza Lahijanian, Daniele Magazzeni, and Erion Plaku. Integrating temporal reasoning and sampling-based motion planning for multigoal problems with dynamics and time windows. Rob. Autom. Lett., 3(4):3473-3480, 2018. URL: https://doi.org/10.1109/LRA.2018.2853642.
  13. Stefan Edelkamp, Erion Plaku, and Yassin Warsame. Monte-carlo search for prize-collecting robot motion planning with time windows, capacities, pickups, and deliveries. In Christoph Benzmüller and Heiner Stuckenschmidt, editors, KI 2019, volume 11793 of LNCS, pages 154-167. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-30179-8_13.
  14. Stefan Edelkamp and Armin Weiß. Blockquicksort: Avoiding branch mispredictions in quicksort. ACM Journal of Experimental Algorithmics, 24(1):1.4:1-1.4:22, 2019. URL: https://doi.org/10.1145/3274660.
  15. Stefan Edelkamp and Armin Weiß. Worst-case efficient sorting with quickmergesort. In Stephen G. Kobourov and Henning Meyerhenke, editors, ALENEX 2019, pages 1-14, 2019. URL: https://doi.org/10.1137/1.9781611975499.1.
  16. Stefan Edelkamp, Armin Weiß, and Sebastian Wild. Quickxsort: A fast sorting scheme in theory and practice. Algorithmica, 82(3):509-588, 2020. URL: https://doi.org/10.1007/s00453-019-00634-0.
  17. Erion Plaku, Sara Rashidian, and Stefan Edelkamp. Multi-group motion planning in virtual environments. J. of Visualization and Comp. Animation, 29(6), 2018. URL: https://doi.org/10.1002/cav.1688.
  18. Álvaro Torralba, Vidal Alcázar, Peter Kissmann, and Stefan Edelkamp. Efficient symbolic search for cost-optimal planning. Artif. Intell., 242:52-79, 2017. URL: https://doi.org/10.1016/j.artint.2016.10.001.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact