Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/70036
Title: Dynamic cost-based multi-tier linked list
Authors: Goh, R.S.M.
Thng, I.L.-.J. 
Keywords: Discrete event simulation
Priority queue
Simulation methodology
Issue Date: 2004
Source: Goh, R.S.M.,Thng, I.L.-.J. (2004). Dynamic cost-based multi-tier linked list. Proceedings of the IASTED International Conference on Applied Simulation and Modelling : 287-289. ScholarBank@NUS Repository.
Abstract: Priority queues are widely employed in numerous applications such as discrete event simulations (DESs). The priority queue structure plays a paramount role of managing the pending event set of a DES. The priority queue contains events where the minimum timestamp event has the highest priority and the maximum timestamp event has the lowest priority. A Calendar Queue (CQ) is a useful structure often employed in DESs. Its popularity is due to its expected O(1) access time for many simulation scenarios, provided the events are evenly distributed in the CQ structure. However, for skewed distributions, it is likely that many events fall into some few buckets in the CQ structure. This may cause the performance of the CQ to deteriorate to O(n). Furthermore, the CQ's resize operation necessary to handle fluctuating queue sizes is costly as it copies all the already sorted events from the old CQ structure to a newly-created one. This article introduces a novel priority queue implementation known as the Dynamic Cost-based Multi-Tier Linked List (DynamicList) structure which does not require the resize operation to obtain near O(1) performance. The DynamicList is empirically shown to be on the average at least 100% faster than all the current priority queues. In some scenarios, the DynamicList is more than one magnitude faster. These evidence suggest strongly that it is an excellent candidate to be widely employed in DESs.
Source Title: Proceedings of the IASTED International Conference on Applied Simulation and Modelling
URI: http://scholarbank.nus.edu.sg/handle/10635/70036
ISBN: 0889864012
Appears in Collections:Staff Publications

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

Page view(s)

24
checked on Dec 9, 2017

Google ScholarTM

Check


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