On Online Labeling with Polynomially Many Labels View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2012

AUTHORS

Martin Babka , Jan Bulánek , Vladimír Čunát , Michal Koucký , Michael Saks

ABSTRACT

In the online labeling problem with parameters n and m we are presented with a sequence of nkeys from a totally ordered universe U and must assign each arriving key a label from the label set {1,2,…,m} so that the order of labels (strictly) respects the ordering on U. As new keys arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items, instead of being labeled, are maintained in sorted order in an array of length m, and we pay unit cost for moving an item.For the case m = cn for constant c > 1, there are known algorithms that use at most O(n log(n)2) relabelings in total [9], and it was shown recently that this is asymptotically optimal [1]. For the case of m = θ(nC) for C > 1, algorithms are known that use O(n logn) relabelings. A matching lower bound was claimed in [7]. That proof involved two distinct steps: a lower bound for a problem they call prefix bucketing and a reduction from prefix bucketing to online labeling. The reduction seems to be incorrect, leaving a (seemingly significant) gap in the proof. In this paper we close the gap by presenting a correct reduction to prefix bucketing. Furthermore we give a simplified and improved analysis of the prefix bucketing lower bound. This improvement allows us to extend the lower bounds for online labeling to the case where the number m of labels is superpolynomial in n. In particular, for superpolynomial m we get an asymptotically optimal lower bound Ω((n logn) / (loglogm − loglogn)). More... »

PAGES

121-132

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-33090-2_12

DOI

http://dx.doi.org/10.1007/978-3-642-33090-2_12

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.4491.8", 
          "name": [
            "Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Babka", 
        "givenName": "Martin", 
        "id": "sg:person.014366523363.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014366523363.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Mathematics, Academy of Sciences, Prague, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.425493.d", 
          "name": [
            "Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic", 
            "Institute of Mathematics, Academy of Sciences, Prague, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bul\u00e1nek", 
        "givenName": "Jan", 
        "id": "sg:person.011527105643.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011527105643.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic", 
          "id": "http://www.grid.ac/institutes/grid.4491.8", 
          "name": [
            "Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic"
          ], 
          "type": "Organization"
        }, 
        "familyName": "\u010cun\u00e1t", 
        "givenName": "Vladim\u00edr", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Aarhus University, Denmark", 
          "id": "http://www.grid.ac/institutes/grid.7048.b", 
          "name": [
            "Institute of Mathematics, Academy of Sciences, Prague, Czech Republic", 
            "Department of Computer Science, Aarhus University, Denmark"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kouck\u00fd", 
        "givenName": "Michal", 
        "id": "sg:person.014077576120.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014077576120.58"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Rutgers University, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "Michael", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "In the online labeling problem with parameters n and m we are presented with a sequence of nkeys from a totally ordered universe U and must assign each arriving key a label from the label set {1,2,\u2026,m} so that the order of labels (strictly) respects the ordering on U. As new keys arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items, instead of being labeled, are maintained in sorted order in an array of length m, and we pay unit cost for moving an item.For the case m\u2009=\u2009cn for constant c\u2009>\u20091, there are known algorithms that use at most O(n log(n)2) relabelings in total [9], and it was shown recently that this is asymptotically optimal [1]. For the case of m\u2009=\u2009\u03b8(nC) for C\u2009>\u20091, algorithms are known that use O(n logn) relabelings. A matching lower bound was claimed in [7]. That proof involved two distinct steps: a lower bound for a problem they call prefix bucketing and a reduction from prefix bucketing to online labeling. The reduction seems to be incorrect, leaving a (seemingly significant) gap in the proof. In this paper we close the gap by presenting a correct reduction to prefix bucketing. Furthermore we give a simplified and improved analysis of the prefix bucketing lower bound. This improvement allows us to extend the lower bounds for online labeling to the case where the number m of labels is superpolynomial in n. In particular, for superpolynomial m we get an asymptotically optimal lower bound \u03a9((n logn) / (loglogm\u2009\u2212\u2009loglogn)).", 
    "editor": [
      {
        "familyName": "Epstein", 
        "givenName": "Leah", 
        "type": "Person"
      }, 
      {
        "familyName": "Ferragina", 
        "givenName": "Paolo", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-33090-2_12", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-33089-6", 
        "978-3-642-33090-2"
      ], 
      "name": "Algorithms \u2013 ESA 2012", 
      "type": "Book"
    }, 
    "keywords": [
      "lower bounds", 
      "universe U", 
      "parameter n", 
      "alternative formulation", 
      "unit cost", 
      "labeling problem", 
      "problem", 
      "online labeling", 
      "improved analysis", 
      "algorithm", 
      "maintenance problems", 
      "bucketing", 
      "proof", 
      "bounds", 
      "correct reduction", 
      "relabeling", 
      "sorted order", 
      "label set", 
      "order of labels", 
      "ordering", 
      "file maintenance problem", 
      "array of length", 
      "online labeling problem", 
      "cost", 
      "total cost", 
      "formulation", 
      "order", 
      "set", 
      "reduction", 
      "array", 
      "cases", 
      "new key", 
      "labels", 
      "gap", 
      "key", 
      "number", 
      "step", 
      "length", 
      "improvement", 
      "time", 
      "sequence", 
      "items", 
      "analysis", 
      "changes", 
      "distinct steps", 
      "goal", 
      "labeling", 
      "CN", 
      "such changes", 
      "paper"
    ], 
    "name": "On Online Labeling with Polynomially Many Labels", 
    "pagination": "121-132", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1034883678"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-33090-2_12"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-33090-2_12", 
      "https://app.dimensions.ai/details/publication/pub.1034883678"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:56", 
    "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_311.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-33090-2_12"
  }
]
 

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-642-33090-2_12'

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-642-33090-2_12'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-33090-2_12'

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-642-33090-2_12'


 

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

152 TRIPLES      22 PREDICATES      75 URIs      68 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-33090-2_12 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nf186f7bfb005499f8577732838180595
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description In the online labeling problem with parameters n and m we are presented with a sequence of nkeys from a totally ordered universe U and must assign each arriving key a label from the label set {1,2,…,m} so that the order of labels (strictly) respects the ordering on U. As new keys arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items, instead of being labeled, are maintained in sorted order in an array of length m, and we pay unit cost for moving an item.For the case m = cn for constant c > 1, there are known algorithms that use at most O(n log(n)2) relabelings in total [9], and it was shown recently that this is asymptotically optimal [1]. For the case of m = θ(nC) for C > 1, algorithms are known that use O(n logn) relabelings. A matching lower bound was claimed in [7]. That proof involved two distinct steps: a lower bound for a problem they call prefix bucketing and a reduction from prefix bucketing to online labeling. The reduction seems to be incorrect, leaving a (seemingly significant) gap in the proof. In this paper we close the gap by presenting a correct reduction to prefix bucketing. Furthermore we give a simplified and improved analysis of the prefix bucketing lower bound. This improvement allows us to extend the lower bounds for online labeling to the case where the number m of labels is superpolynomial in n. In particular, for superpolynomial m we get an asymptotically optimal lower bound Ω((n logn) / (loglogm − loglogn)).
7 schema:editor Nd58f85b3b69847a2bf6fb055343e34e3
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N11d3d28e07a94f949a6adcb8ad17765c
11 schema:keywords CN
12 algorithm
13 alternative formulation
14 analysis
15 array
16 array of length
17 bounds
18 bucketing
19 cases
20 changes
21 correct reduction
22 cost
23 distinct steps
24 file maintenance problem
25 formulation
26 gap
27 goal
28 improved analysis
29 improvement
30 items
31 key
32 label set
33 labeling
34 labeling problem
35 labels
36 length
37 lower bounds
38 maintenance problems
39 new key
40 number
41 online labeling
42 online labeling problem
43 order
44 order of labels
45 ordering
46 paper
47 parameter n
48 problem
49 proof
50 reduction
51 relabeling
52 sequence
53 set
54 sorted order
55 step
56 such changes
57 time
58 total cost
59 unit cost
60 universe U
61 schema:name On Online Labeling with Polynomially Many Labels
62 schema:pagination 121-132
63 schema:productId N03e5b7acda374061b3398acdff993e1d
64 Nda3032e23e4048f6bc5e7a18d3997b01
65 schema:publisher Nef49d79be7454409b477eb7042f86340
66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034883678
67 https://doi.org/10.1007/978-3-642-33090-2_12
68 schema:sdDatePublished 2022-10-01T06:56
69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
70 schema:sdPublisher N752fc9e6f4774f428c056322618daa04
71 schema:url https://doi.org/10.1007/978-3-642-33090-2_12
72 sgo:license sg:explorer/license/
73 sgo:sdDataset chapters
74 rdf:type schema:Chapter
75 N03e5b7acda374061b3398acdff993e1d schema:name doi
76 schema:value 10.1007/978-3-642-33090-2_12
77 rdf:type schema:PropertyValue
78 N11d3d28e07a94f949a6adcb8ad17765c schema:isbn 978-3-642-33089-6
79 978-3-642-33090-2
80 schema:name Algorithms – ESA 2012
81 rdf:type schema:Book
82 N1940b0c2a4dd4d1b89dcf6fb2cb181ed rdf:first N6bb20222f85149adbde7c746cf40df20
83 rdf:rest N1d97ce654b8b46aabce6b9646c417568
84 N1d97ce654b8b46aabce6b9646c417568 rdf:first sg:person.014077576120.58
85 rdf:rest Nfbba12d377d842e8b6faadf7a0c922ae
86 N20c775f1089a417b911c4fe204abf8c0 rdf:first Nb4444e5a07d14a4d987dc0100de08f7b
87 rdf:rest rdf:nil
88 N6bb20222f85149adbde7c746cf40df20 schema:affiliation grid-institutes:grid.4491.8
89 schema:familyName Čunát
90 schema:givenName Vladimír
91 rdf:type schema:Person
92 N752fc9e6f4774f428c056322618daa04 schema:name Springer Nature - SN SciGraph project
93 rdf:type schema:Organization
94 Nb4444e5a07d14a4d987dc0100de08f7b schema:familyName Ferragina
95 schema:givenName Paolo
96 rdf:type schema:Person
97 Nd58f85b3b69847a2bf6fb055343e34e3 rdf:first Ne257bf95b85540cab6a3a360711a4a70
98 rdf:rest N20c775f1089a417b911c4fe204abf8c0
99 Nda3032e23e4048f6bc5e7a18d3997b01 schema:name dimensions_id
100 schema:value pub.1034883678
101 rdf:type schema:PropertyValue
102 Nde1db70f38574977b5bdd65a60296361 rdf:first sg:person.011527105643.50
103 rdf:rest N1940b0c2a4dd4d1b89dcf6fb2cb181ed
104 Ne257bf95b85540cab6a3a360711a4a70 schema:familyName Epstein
105 schema:givenName Leah
106 rdf:type schema:Person
107 Nef49d79be7454409b477eb7042f86340 schema:name Springer Nature
108 rdf:type schema:Organisation
109 Nf186f7bfb005499f8577732838180595 rdf:first sg:person.014366523363.19
110 rdf:rest Nde1db70f38574977b5bdd65a60296361
111 Nfbba12d377d842e8b6faadf7a0c922ae rdf:first sg:person.011520224512.05
112 rdf:rest rdf:nil
113 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
114 schema:name Information and Computing Sciences
115 rdf:type schema:DefinedTerm
116 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
117 schema:name Artificial Intelligence and Image Processing
118 rdf:type schema:DefinedTerm
119 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
120 schema:familyName Saks
121 schema:givenName Michael
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
123 rdf:type schema:Person
124 sg:person.011527105643.50 schema:affiliation grid-institutes:grid.425493.d
125 schema:familyName Bulánek
126 schema:givenName Jan
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011527105643.50
128 rdf:type schema:Person
129 sg:person.014077576120.58 schema:affiliation grid-institutes:grid.7048.b
130 schema:familyName Koucký
131 schema:givenName Michal
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014077576120.58
133 rdf:type schema:Person
134 sg:person.014366523363.19 schema:affiliation grid-institutes:grid.4491.8
135 schema:familyName Babka
136 schema:givenName Martin
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014366523363.19
138 rdf:type schema:Person
139 grid-institutes:grid.425493.d schema:alternateName Institute of Mathematics, Academy of Sciences, Prague, Czech Republic
140 schema:name Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
141 Institute of Mathematics, Academy of Sciences, Prague, Czech Republic
142 rdf:type schema:Organization
143 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, USA
144 schema:name Department of Mathematics, Rutgers University, USA
145 rdf:type schema:Organization
146 grid-institutes:grid.4491.8 schema:alternateName Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
147 schema:name Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
148 rdf:type schema:Organization
149 grid-institutes:grid.7048.b schema:alternateName Department of Computer Science, Aarhus University, Denmark
150 schema:name Department of Computer Science, Aarhus University, Denmark
151 Institute of Mathematics, Academy of Sciences, Prague, Czech Republic
152 rdf:type schema:Organization
 




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


...