Please use this identifier to cite or link to this item: https://doi.org/10.1145/1103323.1103324
Title: Ladder queue: An O(1) priority queue structure for large-scale discrete event simulation
Authors: Tang, W.T. 
Goh, R.S.M.
Thng, I.L.-J. 
Keywords: Calendar queue
Pending event set implementations
Priority queue
Issue Date: 2005
Source: Tang, W.T.,Goh, R.S.M.,Thng, I.L.-J. (2005). Ladder queue: An O(1) priority queue structure for large-scale discrete event simulation. ACM Transactions on Modeling and Computer Simulation 15 (3) : 175-204. ScholarBank@NUS Repository. https://doi.org/10.1145/1103323.1103324
Abstract: This article describes a new priority queue implementation for managing the pending event set in discrete event simulation. Extensive empirical results demonstrate that it consistently outperforms other current popular candidates. This new implementation, called Ladder Queue, is also theoretically justified to have O(1) amortized access time complexity, as long as the mean jump parameter of the priority increment distribution is finite and greater than zero, regardless of its variance. Many practical priority increment distributions satisfy this condition including unbounded variance distributions like the Pareto distribution. This renders the LadderQ the ideal discrete event queue structure for stable O(1) performance even under practical queue distributions with infinite variance. Numerical simulations ranging from 100 to 10 million events affirm the O(1) property of LadderQ and that it is a superior structure for large-scale discrete event simulation. © 2005 ACM.
Source Title: ACM Transactions on Modeling and Computer Simulation
URI: http://scholarbank.nus.edu.sg/handle/10635/56449
ISSN: 10493301
DOI: 10.1145/1103323.1103324
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

19
checked on Jan 17, 2018

Page view(s)

75
checked on Jan 21, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.