Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/72929
Title: SNOOPy calendar queue
Authors: Tan, Kah Leong
Thng, Li-Jin 
Issue Date: 2000
Source: Tan, Kah Leong,Thng, Li-Jin (2000). SNOOPy calendar queue. Winter Simulation Conference Proceedings 1 : 487-495. ScholarBank@NUS Repository.
Abstract: Discrete event simulations often require a future event list structure to manage events according to their timestamp. The choice of an efficient data structure is vital to the performance of discrete event simulations as 40% of the time may be spent on its management. A Calendar Queue (CQ) or Dynamic Calendar Queue (DCQ) are two data structures that offers O(1) complexity regardless of the future event list size. CQ is known to perform poorly over skewed event distributions or when event distribution changes. DCQ improves on the CQ structure by detecting such scenarios in order to redistribute events. Both CQ and DCQ determine their operating parameters (bucket widths) by sampling events. However, sampling technique will fail if the samples do not accurately reflect the inter-event gap size. This paper presents a novel and alternative approach for determining the optimum operating parameter of a calendar queue based on performance statistics. Stress testing of the new calendar queue, henceforth referred to as the Statistically enhanced with Optimum Operating Parameter Calendar Queue (SNOOPy CQ), with widely varying and severely skewed event arrival scenarios show that SNOOPy CQ offers a consistent O(1) performance and can execute up to 100 times faster than DCQ and CQ in certain scenarios.
Source Title: Winter Simulation Conference Proceedings
URI: http://scholarbank.nus.edu.sg/handle/10635/72929
ISSN: 02750708
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 16, 2017

Google ScholarTM

Check


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