Dynamic Generation of Discrete Random Variates View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2003-08

AUTHORS

Yossi Matias, Jeffrey Scott Vitter, Wen-Chun Ni

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(2^{log^* N}) expected time in the worst case. We then show how to reduce the update time to O(log* N) amortized expected time. We finally 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 efficient 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 log N) time. More... »

PAGES

329-358

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00224-003-1078-6

DOI

http://dx.doi.org/10.1007/s00224-003-1078-6

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1013960088


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Tel Aviv University", 
          "id": "https://www.grid.ac/institutes/grid.12136.37", 
          "name": [
            "Department of Computer Science, Tel Aviv University, matias@math.tau.ac.il, Tel Aviv 69978, Israel, IL"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Matias", 
        "givenName": "Yossi", 
        "id": "sg:person.015101125750.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015101125750.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Purdue University", 
          "id": "https://www.grid.ac/institutes/grid.169077.e", 
          "name": [
            "Department of Computer Sciences, Purdue University, jsv@purdue.edu, West Lafayette, IN 49707-2066, USA, US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "Jeffrey Scott", 
        "id": "sg:person.0613677314.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "TBCommerce Network Corporation, 3191 Temple Ave, #210, wcn@tbcommerce.com, Pomona, CA 91768, USA, US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ni", 
        "givenName": "Wen-Chun", 
        "type": "Person"
      }
    ], 
    "datePublished": "2003-08", 
    "datePublishedReg": "2003-08-01", 
    "description": "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(2^{log^* N}) expected time in the worst case. We then show how to reduce the update time to O(log* N) amortized expected time. We finally 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\u2014time 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 efficient 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 \u025b multiplicative factor of the maximal element value. For \u025b= 1/polylog (N), each query, insertion, or deletion takes O(log log log N) time.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00224-003-1078-6", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "36"
      }
    ], 
    "name": "Dynamic Generation of Discrete Random Variates", 
    "pagination": "329-358", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "4280a62976e27eebd016999f23493ed539e3bc067031ff25efdd6c373679f016"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00224-003-1078-6"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1013960088"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00224-003-1078-6", 
      "https://app.dimensions.ai/details/publication/pub.1013960088"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T17:26", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8672_00000487.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/s00224-003-1078-6"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00224-003-1078-6'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00224-003-1078-6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-003-1078-6'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-003-1078-6'


 

This table displays all metadata directly associated to this object as RDF triples.

79 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00224-003-1078-6 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nb47993ccda5941358462c1f6f59ec028
4 schema:datePublished 2003-08
5 schema:datePublishedReg 2003-08-01
6 schema:description 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(2^{log^* N}) expected time in the worst case. We then show how to reduce the update time to O(log* N) amortized expected time. We finally 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 efficient 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 log N) time.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf N7d112900a93f45d1bf5679ba007e746f
11 Nc083454cd38642db97090c20214b4370
12 sg:journal.1052098
13 schema:name Dynamic Generation of Discrete Random Variates
14 schema:pagination 329-358
15 schema:productId N24d74457764e42b9816fc7651e24a4cb
16 N5ed7d71f4b894003b3d7c251893026ac
17 Ndebab62c10c74b0a8e76f0135b15ae8e
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013960088
19 https://doi.org/10.1007/s00224-003-1078-6
20 schema:sdDatePublished 2019-04-10T17:26
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nd1ae6ac9085746c18dc4258505b9ccf1
23 schema:url http://link.springer.com/10.1007/s00224-003-1078-6
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N24d74457764e42b9816fc7651e24a4cb schema:name doi
28 schema:value 10.1007/s00224-003-1078-6
29 rdf:type schema:PropertyValue
30 N5ed7d71f4b894003b3d7c251893026ac schema:name readcube_id
31 schema:value 4280a62976e27eebd016999f23493ed539e3bc067031ff25efdd6c373679f016
32 rdf:type schema:PropertyValue
33 N7226545cf5314cbbb7bda824dcbc2655 schema:affiliation Nc54c35bb00cc4aeea474110d9b038b09
34 schema:familyName Ni
35 schema:givenName Wen-Chun
36 rdf:type schema:Person
37 N7d112900a93f45d1bf5679ba007e746f schema:volumeNumber 36
38 rdf:type schema:PublicationVolume
39 N9368e5cfb997488cb0d3b0e463ff4281 rdf:first sg:person.0613677314.28
40 rdf:rest Nb0abd03cfa564645877cb91a0ca2fada
41 Nb0abd03cfa564645877cb91a0ca2fada rdf:first N7226545cf5314cbbb7bda824dcbc2655
42 rdf:rest rdf:nil
43 Nb47993ccda5941358462c1f6f59ec028 rdf:first sg:person.015101125750.45
44 rdf:rest N9368e5cfb997488cb0d3b0e463ff4281
45 Nc083454cd38642db97090c20214b4370 schema:issueNumber 4
46 rdf:type schema:PublicationIssue
47 Nc54c35bb00cc4aeea474110d9b038b09 schema:name TBCommerce Network Corporation, 3191 Temple Ave, #210, wcn@tbcommerce.com, Pomona, CA 91768, USA, US
48 rdf:type schema:Organization
49 Nd1ae6ac9085746c18dc4258505b9ccf1 schema:name Springer Nature - SN SciGraph project
50 rdf:type schema:Organization
51 Ndebab62c10c74b0a8e76f0135b15ae8e schema:name dimensions_id
52 schema:value pub.1013960088
53 rdf:type schema:PropertyValue
54 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
55 schema:name Information and Computing Sciences
56 rdf:type schema:DefinedTerm
57 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
58 schema:name Computation Theory and Mathematics
59 rdf:type schema:DefinedTerm
60 sg:journal.1052098 schema:issn 1432-4350
61 1433-0490
62 schema:name Theory of Computing Systems
63 rdf:type schema:Periodical
64 sg:person.015101125750.45 schema:affiliation https://www.grid.ac/institutes/grid.12136.37
65 schema:familyName Matias
66 schema:givenName Yossi
67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015101125750.45
68 rdf:type schema:Person
69 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.169077.e
70 schema:familyName Vitter
71 schema:givenName Jeffrey Scott
72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
73 rdf:type schema:Person
74 https://www.grid.ac/institutes/grid.12136.37 schema:alternateName Tel Aviv University
75 schema:name Department of Computer Science, Tel Aviv University, matias@math.tau.ac.il, Tel Aviv 69978, Israel, IL
76 rdf:type schema:Organization
77 https://www.grid.ac/institutes/grid.169077.e schema:alternateName Purdue University
78 schema:name Department of Computer Sciences, Purdue University, jsv@purdue.edu, West Lafayette, IN 49707-2066, USA, US
79 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...