dc.contributor.author | Matias, Yossi | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.contributor.author | Ni, Wen-Chun | |
dc.date.accessioned | 2011-03-21T20:08:17Z | |
dc.date.available | 2011-03-21T20:08:17Z | |
dc.date.issued | 2003 | |
dc.identifier.citation | Y. Matias, J. S. Vitter and W.-C. Ni. “Dynamic Generation of Discrete Random Variates,” Theory of Computing Systems, 36(4), 2003, 329–358. An extended abstract appears in Proceedings of the 4th Annual SIAM/ACM Symposium on Discrete Algorithms (SODA ’93), Austin, TX, January 1993, 361–370. http://dx.doi.org/10.1007/s00224-003-1078-6 | |
dc.identifier.uri | http://hdl.handle.net/1808/7224 | |
dc.description | The original publication is available at www.springerlink.com | |
dc.description.abstract | We present and analyze efficient new algorithms for generating a random variate distributed according
to a dynamically changing set of N weights. The base version of each algorithm generates the
discrete random variate in O(log N) expected time and updates a weight in O(2log N) expected
time in the worst case. We then show how to reduce the update time to O(log N) amortized
expected time. We nally show how to apply our techniques to a lookup-table technique in order
to obtain expected constant time in the worst case for generation and update. We give parallel
algorithms for parallel generation and update having optimal processor-time product.
Besides the usual application in computer simulation, our method can be used to perform
constant-time prediction in prefetching applications. We also apply our techniques to obtain an
eÆcient dynamic algorithm for maintaining an approximate heap of N elements, in which each query
is required to return an element whose value is within an multiplicative factor of the maximal
element value. For = 1=polylog(N), each query, insertion, or deletion takes O(log log logN) time. | |
dc.language.iso | en_US | |
dc.publisher | Springer Verlag | |
dc.subject | Random-number generator | |
dc.subject | Random variate | |
dc.subject | Alias | |
dc.subject | Bucket | |
dc.subject | Rejection | |
dc.subject | Dynamic data structure | |
dc.subject | Update | |
dc.subject | Approximate priority queue | |
dc.title | Dynamic Generation of Discrete Random Variates | |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffrey Scott | |
kusw.oastatus | fullparticipation | |
dc.identifier.doi | 10.1007/s00224-003-1078-6 | |
kusw.oaversion | Scholarly/refereed, author accepted manuscript | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess | |