Greedy Is an Almost Optimal Deque View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015-07-28

AUTHORS

Parinya Chalermsook , Mayank Goswami , László Kozma , Kurt Mehlhorn , Thatchaphol Saranurak

ABSTRACT

In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and Pǎtraşcu (DHIKP) to accommodate for insertions and deletions. Within this extended model, we study the online Greedy BST algorithm introduced by DHIKP. Greedy BST is known to be equivalent to a maximally greedy (but inherently offline) algorithm introduced independently by Lucas in 1988 and Munro in 2000, conjectured to be dynamically optimal.With the application of forbidden-submatrix theory, we prove a quasilinear upper bound on the performance of Greedy BST on deque sequences. It has been conjectured (Tarjan, 1985) that splay trees (Sleator and Tarjan, 1983) can serve such sequences in linear time. Currently neither splay trees, nor other general-purpose BST algorithms are known to fulfill this requirement. As a special case, we show that Greedy BST can serve output-restricted deque sequences in linear time. A similar result is known for splay trees (Tarjan, 1985; Elmasry, 2004).As a further application of the insert-delete model, we give a simple proof that, given a set U of permutations of [n], the access cost of any BST algorithm is Ω(log|U|+n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega ( \log \vert U \vert + n)$$\end{document} on “most” of the permutations from U. In particular, this implies that the access cost for a random permutation of [n] is Ω(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega {(n\log {n})}$$\end{document} with high probability.Besides the splay tree noted before, Greedy BST has recently emerged as a plausible candidate for dynamic optimality. Compared to splay trees, much less effort has gone into analyzing Greedy BST. Our work is intended as a step towards a full understanding of Greedy BST, and we remark that forbidden-submatrix arguments seem particularly well suited for carrying out this program. More... »

PAGES

152-165

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-21840-3_13

DOI

http://dx.doi.org/10.1007/978-3-319-21840-3_13

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Max-Planck Institute for Informatics, 66123, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck Institute for Informatics, 66123, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chalermsook", 
        "givenName": "Parinya", 
        "id": "sg:person.011252741475.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011252741475.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck Institute for Informatics, 66123, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck Institute for Informatics, 66123, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Goswami", 
        "givenName": "Mayank", 
        "id": "sg:person.01357776101.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01357776101.38"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Saarland University, 66123, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.11749.3a", 
          "name": [
            "Department of Computer Science, Saarland University, 66123, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kozma", 
        "givenName": "L\u00e1szl\u00f3", 
        "id": "sg:person.010247136227.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010247136227.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck Institute for Informatics, 66123, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max-Planck Institute for Informatics, 66123, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "KTH Royal Institute of Technology, 11428, Stockholm, Sweden", 
          "id": "http://www.grid.ac/institutes/grid.5037.1", 
          "name": [
            "KTH Royal Institute of Technology, 11428, Stockholm, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saranurak", 
        "givenName": "Thatchaphol", 
        "id": "sg:person.012421743515.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012421743515.16"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-07-28", 
    "datePublishedReg": "2015-07-28", 
    "description": "In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and P\u01cetra\u015fcu (DHIKP) to accommodate for insertions and deletions. Within this extended model, we study the online Greedy\u00a0BST algorithm introduced by DHIKP. Greedy\u00a0BST is known to be equivalent to a maximally greedy (but inherently offline) algorithm introduced independently by Lucas in 1988 and Munro in 2000, conjectured to be dynamically optimal.With the application of forbidden-submatrix theory, we prove a quasilinear upper bound on the performance of Greedy\u00a0BST on deque sequences. It has been conjectured (Tarjan, 1985) that splay trees (Sleator and Tarjan, 1983) can serve such sequences in linear time. Currently neither splay trees, nor other general-purpose BST algorithms are known to fulfill this requirement. As a special case, we show that Greedy\u00a0BST can serve output-restricted deque sequences in linear time. A similar result is known for splay trees (Tarjan, 1985; Elmasry, 2004).As a further application of the insert-delete model, we give a simple proof that, given a set U of permutations of [n], the access cost of any BST algorithm is \u03a9(log|U|+n)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\Omega ( \\log \\vert U \\vert + n)$$\\end{document} on \u201cmost\u201d of the permutations from U. In particular, this implies that the access cost for a random permutation of [n] is \u03a9(nlogn)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\Omega {(n\\log {n})}$$\\end{document} with high probability.Besides the splay tree noted before, Greedy\u00a0BST has recently emerged as a plausible candidate for dynamic optimality. Compared to splay trees, much less effort has gone into analyzing Greedy\u00a0BST. Our work is intended as a step towards a full understanding of Greedy\u00a0BST, and we remark that forbidden-submatrix arguments seem particularly well suited for carrying out this program.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }, 
      {
        "familyName": "Stege", 
        "givenName": "Ulrike", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-21840-3_13", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-21839-7", 
        "978-3-319-21840-3"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "linear time", 
      "simple proof", 
      "special case", 
      "random permutation", 
      "BST algorithm", 
      "greedy algorithm", 
      "extended model", 
      "dynamic optimality", 
      "algorithm", 
      "Greedy", 
      "permutations", 
      "such sequences", 
      "quasilinear", 
      "optimality", 
      "high probability", 
      "further application", 
      "tree model", 
      "model", 
      "Demaine", 
      "theory", 
      "access cost", 
      "splay trees", 
      "applications", 
      "probability", 
      "less effort", 
      "proof", 
      "Kane", 
      "deque", 
      "plausible candidate", 
      "similar results", 
      "Iacono", 
      "cost", 
      "sequence", 
      "trees", 
      "Lucas", 
      "performance", 
      "full understanding", 
      "argument", 
      "time", 
      "cases", 
      "work", 
      "step", 
      "results", 
      "BST", 
      "requirements", 
      "candidates", 
      "efforts", 
      "Harmon", 
      "understanding", 
      "program", 
      "Munro", 
      "insertion", 
      "deletion", 
      "paper"
    ], 
    "name": "Greedy Is an Almost Optimal Deque", 
    "pagination": "152-165", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1040909857"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-21840-3_13"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-21840-3_13", 
      "https://app.dimensions.ai/details/publication/pub.1040909857"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_361.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-21840-3_13"
  }
]
 

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/978-3-319-21840-3_13'

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/978-3-319-21840-3_13'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-21840-3_13'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-21840-3_13'


 

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

157 TRIPLES      22 PREDICATES      78 URIs      71 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-21840-3_13 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N86aa24af48e442ef9da8c7153db80d1b
4 schema:datePublished 2015-07-28
5 schema:datePublishedReg 2015-07-28
6 schema:description In this paper we extend the geometric binary search tree (BST) model of Demaine, Harmon, Iacono, Kane, and Pǎtraşcu (DHIKP) to accommodate for insertions and deletions. Within this extended model, we study the online Greedy BST algorithm introduced by DHIKP. Greedy BST is known to be equivalent to a maximally greedy (but inherently offline) algorithm introduced independently by Lucas in 1988 and Munro in 2000, conjectured to be dynamically optimal.With the application of forbidden-submatrix theory, we prove a quasilinear upper bound on the performance of Greedy BST on deque sequences. It has been conjectured (Tarjan, 1985) that splay trees (Sleator and Tarjan, 1983) can serve such sequences in linear time. Currently neither splay trees, nor other general-purpose BST algorithms are known to fulfill this requirement. As a special case, we show that Greedy BST can serve output-restricted deque sequences in linear time. A similar result is known for splay trees (Tarjan, 1985; Elmasry, 2004).As a further application of the insert-delete model, we give a simple proof that, given a set U of permutations of [n], the access cost of any BST algorithm is Ω(log|U|+n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega ( \log \vert U \vert + n)$$\end{document} on “most” of the permutations from U. In particular, this implies that the access cost for a random permutation of [n] is Ω(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega {(n\log {n})}$$\end{document} with high probability.Besides the splay tree noted before, Greedy BST has recently emerged as a plausible candidate for dynamic optimality. Compared to splay trees, much less effort has gone into analyzing Greedy BST. Our work is intended as a step towards a full understanding of Greedy BST, and we remark that forbidden-submatrix arguments seem particularly well suited for carrying out this program.
7 schema:editor N21e8184998194e528a88ddb121488293
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Nbf8a12ae42db4f0f8144900485333afc
11 schema:keywords BST
12 BST algorithm
13 Demaine
14 Greedy
15 Harmon
16 Iacono
17 Kane
18 Lucas
19 Munro
20 access cost
21 algorithm
22 applications
23 argument
24 candidates
25 cases
26 cost
27 deletion
28 deque
29 dynamic optimality
30 efforts
31 extended model
32 full understanding
33 further application
34 greedy algorithm
35 high probability
36 insertion
37 less effort
38 linear time
39 model
40 optimality
41 paper
42 performance
43 permutations
44 plausible candidate
45 probability
46 program
47 proof
48 quasilinear
49 random permutation
50 requirements
51 results
52 sequence
53 similar results
54 simple proof
55 special case
56 splay trees
57 step
58 such sequences
59 theory
60 time
61 tree model
62 trees
63 understanding
64 work
65 schema:name Greedy Is an Almost Optimal Deque
66 schema:pagination 152-165
67 schema:productId N1b244a5394cf4ab5a8d0e391590702cf
68 N9df64d8627c34e5a914daf68ca9d073b
69 schema:publisher Nda8c5f41111144acad53fb191fdc2ef3
70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040909857
71 https://doi.org/10.1007/978-3-319-21840-3_13
72 schema:sdDatePublished 2022-10-01T06:57
73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
74 schema:sdPublisher Nbd9cd6ad235a44268983fdf423191003
75 schema:url https://doi.org/10.1007/978-3-319-21840-3_13
76 sgo:license sg:explorer/license/
77 sgo:sdDataset chapters
78 rdf:type schema:Chapter
79 N0e4dcd147f344e76ba45d67410c5556a rdf:first sg:person.01357776101.38
80 rdf:rest N5ecc53d199834263963d3244b15f2bce
81 N1366b0c6f56a44c6b8c5014855c3ce03 schema:familyName Stege
82 schema:givenName Ulrike
83 rdf:type schema:Person
84 N1b244a5394cf4ab5a8d0e391590702cf schema:name dimensions_id
85 schema:value pub.1040909857
86 rdf:type schema:PropertyValue
87 N21e8184998194e528a88ddb121488293 rdf:first Ned2b55f6126b4ac6b25facd41b1a4d2c
88 rdf:rest Nf7566013edde40f791229945f858163e
89 N5ecc53d199834263963d3244b15f2bce rdf:first sg:person.010247136227.30
90 rdf:rest Nfb4cecce2a964eec92b42941c8fbeda1
91 N617bc8e4d64f444f8b347d5e4acc919e rdf:first N1366b0c6f56a44c6b8c5014855c3ce03
92 rdf:rest rdf:nil
93 N6b7db0376f204ea082b140d7bd5ef67e rdf:first sg:person.012421743515.16
94 rdf:rest rdf:nil
95 N86aa24af48e442ef9da8c7153db80d1b rdf:first sg:person.011252741475.62
96 rdf:rest N0e4dcd147f344e76ba45d67410c5556a
97 N9df64d8627c34e5a914daf68ca9d073b schema:name doi
98 schema:value 10.1007/978-3-319-21840-3_13
99 rdf:type schema:PropertyValue
100 Nbd9cd6ad235a44268983fdf423191003 schema:name Springer Nature - SN SciGraph project
101 rdf:type schema:Organization
102 Nbf8a12ae42db4f0f8144900485333afc schema:isbn 978-3-319-21839-7
103 978-3-319-21840-3
104 schema:name Algorithms and Data Structures
105 rdf:type schema:Book
106 Nda8c5f41111144acad53fb191fdc2ef3 schema:name Springer Nature
107 rdf:type schema:Organisation
108 Nea4fd815bfc842c9add8e431036ca08e schema:familyName Sack
109 schema:givenName Jörg-Rüdiger
110 rdf:type schema:Person
111 Ned2b55f6126b4ac6b25facd41b1a4d2c schema:familyName Dehne
112 schema:givenName Frank
113 rdf:type schema:Person
114 Nf7566013edde40f791229945f858163e rdf:first Nea4fd815bfc842c9add8e431036ca08e
115 rdf:rest N617bc8e4d64f444f8b347d5e4acc919e
116 Nfb4cecce2a964eec92b42941c8fbeda1 rdf:first sg:person.011757371347.43
117 rdf:rest N6b7db0376f204ea082b140d7bd5ef67e
118 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
119 schema:name Information and Computing Sciences
120 rdf:type schema:DefinedTerm
121 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
122 schema:name Computation Theory and Mathematics
123 rdf:type schema:DefinedTerm
124 sg:person.010247136227.30 schema:affiliation grid-institutes:grid.11749.3a
125 schema:familyName Kozma
126 schema:givenName László
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010247136227.30
128 rdf:type schema:Person
129 sg:person.011252741475.62 schema:affiliation grid-institutes:grid.419528.3
130 schema:familyName Chalermsook
131 schema:givenName Parinya
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011252741475.62
133 rdf:type schema:Person
134 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
135 schema:familyName Mehlhorn
136 schema:givenName Kurt
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
138 rdf:type schema:Person
139 sg:person.012421743515.16 schema:affiliation grid-institutes:grid.5037.1
140 schema:familyName Saranurak
141 schema:givenName Thatchaphol
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012421743515.16
143 rdf:type schema:Person
144 sg:person.01357776101.38 schema:affiliation grid-institutes:grid.419528.3
145 schema:familyName Goswami
146 schema:givenName Mayank
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01357776101.38
148 rdf:type schema:Person
149 grid-institutes:grid.11749.3a schema:alternateName Department of Computer Science, Saarland University, 66123, Saarbrücken, Germany
150 schema:name Department of Computer Science, Saarland University, 66123, Saarbrücken, Germany
151 rdf:type schema:Organization
152 grid-institutes:grid.419528.3 schema:alternateName Max-Planck Institute for Informatics, 66123, Saarbrücken, Germany
153 schema:name Max-Planck Institute for Informatics, 66123, Saarbrücken, Germany
154 rdf:type schema:Organization
155 grid-institutes:grid.5037.1 schema:alternateName KTH Royal Institute of Technology, 11428, Stockholm, Sweden
156 schema:name KTH Royal Institute of Technology, 11428, Stockholm, Sweden
157 rdf:type schema:Organization
 




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


...