General methods for the analysis of the maximum size of dynamic data structures View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2005-11-29

AUTHORS

Claire M. Kenyon-Mathieu , Jeffrey Scott Vitter

ABSTRACT

We develop two probabilistic methods that allow us to analyze the maximum data structure size encountered during a sequence of insertions and deletions in data structures such as priority queues, dictionaries, linear lists, and symbol tables, and in sweepline structures for geometry and VLSI applications. The notion of the “maximum” is basic to issues of resource preallocation. We apply our methods to combinatorial models of file histories and probabilistic models, as well as to a non-Markovian process (algorithm) for processing sweepline information in an efficient way, called “hashing with lazy deletion” (HwLD). We derive expressions for the expected maximum data structure size that are asymptotically exact, that is, correct up to lower-order terms; in several cases of interest the expected value of the maximum size is asymptotically equal to the maximum expected size. At a high level, our first method isolates the primary contribution to the maximum and bounds the lesser effects. In our second technique we relate the continuous-time probabilistic model to its discrete analog—the maximum slot occupancy in hashing. More... »

PAGES

473-487

References to SciGraph publications

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-51371-1
978-3-540-46201-9

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0035778

DOI

http://dx.doi.org/10.1007/bfb0035778

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Princeton University", 
          "id": "https://www.grid.ac/institutes/grid.16750.35", 
          "name": [
            "Department of Computer Science, Princeton University, 08544, Princeton, NJ"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kenyon-Mathieu", 
        "givenName": "Claire M.", 
        "id": "sg:person.07467577377.92", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07467577377.92"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Computer Science, Brown University, Box 1910, 02912, Providence, R. I."
          ], 
          "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"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1090/s0002-9947-1957-0091566-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019493158"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0734-189x(86)90046-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026343808"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/800135.804397", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034731214"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0196-6774(80)90020-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037909401"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01840434", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045093830", 
          "https://doi.org/10.1007/bf01840434"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01840434", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045093830", 
          "https://doi.org/10.1007/bf01840434"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0216073", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842019"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/dac.1983.1585739", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086248715"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005-11-29", 
    "datePublishedReg": "2005-11-29", 
    "description": "We develop two probabilistic methods that allow us to analyze the maximum data structure size encountered during a sequence of insertions and deletions in data structures such as priority queues, dictionaries, linear lists, and symbol tables, and in sweepline structures for geometry and VLSI applications. The notion of the \u201cmaximum\u201d is basic to issues of resource preallocation. We apply our methods to combinatorial models of file histories and probabilistic models, as well as to a non-Markovian process (algorithm) for processing sweepline information in an efficient way, called \u201chashing with lazy deletion\u201d (HwLD). We derive expressions for the expected maximum data structure size that are asymptotically exact, that is, correct up to lower-order terms; in several cases of interest the expected value of the maximum size is asymptotically equal to the maximum expected size. At a high level, our first method isolates the primary contribution to the maximum and bounds the lesser effects. In our second technique we relate the continuous-time probabilistic model to its discrete analog\u2014the maximum slot occupancy in hashing.", 
    "editor": [
      {
        "familyName": "Ausiello", 
        "givenName": "Giorgio", 
        "type": "Person"
      }, 
      {
        "familyName": "Dezani-Ciancaglini", 
        "givenName": "Mariangiola", 
        "type": "Person"
      }, 
      {
        "familyName": "Della Rocca", 
        "givenName": "Simonetta Ronchi", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0035778", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-51371-1", 
        "978-3-540-46201-9"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "name": "General methods for the analysis of the maximum size of dynamic data structures", 
    "pagination": "473-487", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1046371961"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0035778"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "dce4edd90c00b0805fd19f90c38e3ec739a15dcfba1f3121b72c4fa030bb6e07"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0035778", 
      "https://app.dimensions.ai/details/publication/pub.1046371961"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T09:41", 
    "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/0000000374_0000000374/records_119738_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2FBFb0035778"
  }
]
 

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/bfb0035778'

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/bfb0035778'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0035778'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0035778'


 

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

106 TRIPLES      23 PREDICATES      33 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0035778 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N5dd5225b68f741d8bf2acd5101a701c9
4 schema:citation sg:pub.10.1007/bf01840434
5 https://doi.org/10.1016/0196-6774(80)90020-6
6 https://doi.org/10.1016/0734-189x(86)90046-0
7 https://doi.org/10.1090/s0002-9947-1957-0091566-1
8 https://doi.org/10.1109/dac.1983.1585739
9 https://doi.org/10.1137/0216073
10 https://doi.org/10.1145/800135.804397
11 schema:datePublished 2005-11-29
12 schema:datePublishedReg 2005-11-29
13 schema:description We develop two probabilistic methods that allow us to analyze the maximum data structure size encountered during a sequence of insertions and deletions in data structures such as priority queues, dictionaries, linear lists, and symbol tables, and in sweepline structures for geometry and VLSI applications. The notion of the “maximum” is basic to issues of resource preallocation. We apply our methods to combinatorial models of file histories and probabilistic models, as well as to a non-Markovian process (algorithm) for processing sweepline information in an efficient way, called “hashing with lazy deletion” (HwLD). We derive expressions for the expected maximum data structure size that are asymptotically exact, that is, correct up to lower-order terms; in several cases of interest the expected value of the maximum size is asymptotically equal to the maximum expected size. At a high level, our first method isolates the primary contribution to the maximum and bounds the lesser effects. In our second technique we relate the continuous-time probabilistic model to its discrete analog—the maximum slot occupancy in hashing.
14 schema:editor N9447405f912e472c999d7b1c6c0ec44c
15 schema:genre chapter
16 schema:inLanguage en
17 schema:isAccessibleForFree false
18 schema:isPartOf N36557762d06f478db49a968092290ae4
19 schema:name General methods for the analysis of the maximum size of dynamic data structures
20 schema:pagination 473-487
21 schema:productId N750d06d1911142af8b0d7271f01046a3
22 N7ed94afef5f54bf8a909280a719158b3
23 Nf66e4469dcc843c6915f903aa4dbc8ca
24 schema:publisher Nf0f880fed38c47bd8fa54b8edb405388
25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046371961
26 https://doi.org/10.1007/bfb0035778
27 schema:sdDatePublished 2019-04-16T09:41
28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
29 schema:sdPublisher Nbd4d8b51472a4e9c8702c188d8c2cd7a
30 schema:url https://link.springer.com/10.1007%2FBFb0035778
31 sgo:license sg:explorer/license/
32 sgo:sdDataset chapters
33 rdf:type schema:Chapter
34 N296d591726e04fc8aa959bf8ae0c4ed5 schema:familyName Della Rocca
35 schema:givenName Simonetta Ronchi
36 rdf:type schema:Person
37 N36557762d06f478db49a968092290ae4 schema:isbn 978-3-540-46201-9
38 978-3-540-51371-1
39 schema:name Automata, Languages and Programming
40 rdf:type schema:Book
41 N43918e0da9d5461fb06f6d713bb79d1a schema:name Department of Computer Science, Brown University, Box 1910, 02912, Providence, R. I.
42 rdf:type schema:Organization
43 N5d77d7ee7eaf4aee9ad369aa981df6ec rdf:first N92a3617054844ab8ac1ed0268c12fc66
44 rdf:rest Nce87c71afd6248c2a63cfc875ae011e1
45 N5dd5225b68f741d8bf2acd5101a701c9 rdf:first sg:person.07467577377.92
46 rdf:rest Na112e2509dc2458ba03229354e8c5742
47 N750d06d1911142af8b0d7271f01046a3 schema:name readcube_id
48 schema:value dce4edd90c00b0805fd19f90c38e3ec739a15dcfba1f3121b72c4fa030bb6e07
49 rdf:type schema:PropertyValue
50 N7ed94afef5f54bf8a909280a719158b3 schema:name doi
51 schema:value 10.1007/bfb0035778
52 rdf:type schema:PropertyValue
53 N92a3617054844ab8ac1ed0268c12fc66 schema:familyName Dezani-Ciancaglini
54 schema:givenName Mariangiola
55 rdf:type schema:Person
56 N9447405f912e472c999d7b1c6c0ec44c rdf:first Nac963d75c3314835bfd3f1516adf45e1
57 rdf:rest N5d77d7ee7eaf4aee9ad369aa981df6ec
58 Na112e2509dc2458ba03229354e8c5742 rdf:first sg:person.0613677314.28
59 rdf:rest rdf:nil
60 Nac963d75c3314835bfd3f1516adf45e1 schema:familyName Ausiello
61 schema:givenName Giorgio
62 rdf:type schema:Person
63 Nbd4d8b51472a4e9c8702c188d8c2cd7a schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 Nce87c71afd6248c2a63cfc875ae011e1 rdf:first N296d591726e04fc8aa959bf8ae0c4ed5
66 rdf:rest rdf:nil
67 Nf0f880fed38c47bd8fa54b8edb405388 schema:location Berlin, Heidelberg
68 schema:name Springer Berlin Heidelberg
69 rdf:type schema:Organisation
70 Nf66e4469dcc843c6915f903aa4dbc8ca schema:name dimensions_id
71 schema:value pub.1046371961
72 rdf:type schema:PropertyValue
73 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
74 schema:name Mathematical Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
77 schema:name Pure Mathematics
78 rdf:type schema:DefinedTerm
79 sg:person.0613677314.28 schema:affiliation N43918e0da9d5461fb06f6d713bb79d1a
80 schema:familyName Vitter
81 schema:givenName Jeffrey Scott
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
83 rdf:type schema:Person
84 sg:person.07467577377.92 schema:affiliation https://www.grid.ac/institutes/grid.16750.35
85 schema:familyName Kenyon-Mathieu
86 schema:givenName Claire M.
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07467577377.92
88 rdf:type schema:Person
89 sg:pub.10.1007/bf01840434 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045093830
90 https://doi.org/10.1007/bf01840434
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1016/0196-6774(80)90020-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037909401
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1016/0734-189x(86)90046-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026343808
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1090/s0002-9947-1957-0091566-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019493158
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1109/dac.1983.1585739 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086248715
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1137/0216073 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842019
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1145/800135.804397 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034731214
103 rdf:type schema:CreativeWork
104 https://www.grid.ac/institutes/grid.16750.35 schema:alternateName Princeton University
105 schema:name Department of Computer Science, Princeton University, 08544, Princeton, NJ
106 rdf:type schema:Organization
 




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


...