The data structure that handles the pending event set of a discrete event simulator is a critical component in that its performances have a direct impact on those of the overall simulation engine. Many data structures have been proposed in the literature. Among them, the Ladder Queue (LadderQ) claims O(1) amortized access time. However, empirical results show that the practical achievement of such performances is highly dependent on the distribution of event timestamps and that in many cases are similar or even worse than those of heap-based priority queues. This paper proposes an adaptive extension of the LadderQ which overcomes most of its weaknesses and allows to achieve O(1) amortized access time in practice.

Adaptive Ladder Queue: Achieving O(1) amortized access time in practice

Furfaro, Angelo;
2018

Abstract

The data structure that handles the pending event set of a discrete event simulator is a critical component in that its performances have a direct impact on those of the overall simulation engine. Many data structures have been proposed in the literature. Among them, the Ladder Queue (LadderQ) claims O(1) amortized access time. However, empirical results show that the practical achievement of such performances is highly dependent on the distribution of event timestamps and that in many cases are similar or even worse than those of heap-based priority queues. This paper proposes an adaptive extension of the LadderQ which overcomes most of its weaknesses and allows to achieve O(1) amortized access time in practice.
9781450350921
Calendar queue; Discrete event simulation; Ladder queue; Pending event set; Priority queue; Computer Graphics and Computer-Aided Design; Modeling and Simulation
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/284549
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact