On-line algorithms for locating checkpoints View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1994-01

AUTHORS

Marshall Bern, Daniel H. Greene, Arvind Raghunathan, Madhu Sudan

ABSTRACT

Motivated by applications in data compression, debugging, and physical simulation, we consider the problem of adaptively choosing locations in a long computation at which to save intermediate results. Such checkpoints allow faster recomputation of arbitrary requested points within the computation. We abstract the problem to a server problem in whichk servers move along a line in a single direction, modeling the fact that most computations are not reversible. Since checkpoints may be arbitrarily copied, we allow a server to jump to any location currently occupied by another server. We present on-line algorithms and analyze their competitiveness. We give lower bounds on the competitiveness of any on-line algorithm and show that our algorithms achieve these bounds within relatively small factors. More... »

PAGES

33-52

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "Xerox PARC, 3333 Coyote Hill Rd., 94304, Palo Alto, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.482243.b", 
          "name": [
            "Xerox PARC, 3333 Coyote Hill Rd., 94304, Palo Alto, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bern", 
        "givenName": "Marshall", 
        "id": "sg:person.0670701164.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0670701164.61"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Xerox PARC, 3333 Coyote Hill Rd., 94304, Palo Alto, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.482243.b", 
          "name": [
            "Xerox PARC, 3333 Coyote Hill Rd., 94304, Palo Alto, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Greene", 
        "givenName": "Daniel H.", 
        "id": "sg:person.013716363105.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013716363105.16"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Division, University of California, 95616, Davis, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, University of California, 95616, Davis, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Raghunathan", 
        "givenName": "Arvind", 
        "id": "sg:person.012752623315.11", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012752623315.11"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Computer Science Division, University of California, 94720, Berkeley, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "Computer Science Division, University of California, 94720, Berkeley, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sudan", 
        "givenName": "Madhu", 
        "id": "sg:person.014663420265.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01762111", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038306247", 
          "https://doi.org/10.1007/bf01762111"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-1098-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021021236", 
          "https://doi.org/10.1007/978-1-4612-1098-6"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1994-01", 
    "datePublishedReg": "1994-01-01", 
    "description": "Motivated by applications in data compression, debugging, and physical simulation, we consider the problem of adaptively choosing locations in a long computation at which to save intermediate results. Such checkpoints allow faster recomputation of arbitrary requested points within the computation. We abstract the problem to a server problem in whichk servers move along a line in a single direction, modeling the fact that most computations are not reversible. Since checkpoints may be arbitrarily copied, we allow a server to jump to any location currently occupied by another server. We present on-line algorithms and analyze their competitiveness. We give lower bounds on the competitiveness of any on-line algorithm and show that our algorithms achieve these bounds within relatively small factors.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01294262", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "11"
      }
    ], 
    "keywords": [
      "line algorithm", 
      "fast recomputation", 
      "data compression", 
      "most computations", 
      "server problem", 
      "server", 
      "intermediate results", 
      "algorithm", 
      "long computations", 
      "physical simulation", 
      "computation", 
      "lower bounds", 
      "debugging", 
      "recomputation", 
      "small factor", 
      "bounds", 
      "applications", 
      "single direction", 
      "compression", 
      "simulations", 
      "location", 
      "competitiveness", 
      "checkpoint", 
      "point", 
      "such checkpoints", 
      "results", 
      "fact", 
      "direction", 
      "lines", 
      "factors", 
      "problem", 
      "whichk servers"
    ], 
    "name": "On-line algorithms for locating checkpoints", 
    "pagination": "33-52", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1019407387"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01294262"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01294262", 
      "https://app.dimensions.ai/details/publication/pub.1019407387"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-01-01T18:06", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_236.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01294262"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

124 TRIPLES      22 PREDICATES      60 URIs      50 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01294262 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Nc16a08b8c5ec4cdb8ef1626f1809abf3
4 schema:citation sg:pub.10.1007/978-1-4612-1098-6
5 sg:pub.10.1007/bf01762111
6 schema:datePublished 1994-01
7 schema:datePublishedReg 1994-01-01
8 schema:description Motivated by applications in data compression, debugging, and physical simulation, we consider the problem of adaptively choosing locations in a long computation at which to save intermediate results. Such checkpoints allow faster recomputation of arbitrary requested points within the computation. We abstract the problem to a server problem in whichk servers move along a line in a single direction, modeling the fact that most computations are not reversible. Since checkpoints may be arbitrarily copied, we allow a server to jump to any location currently occupied by another server. We present on-line algorithms and analyze their competitiveness. We give lower bounds on the competitiveness of any on-line algorithm and show that our algorithms achieve these bounds within relatively small factors.
9 schema:genre article
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf N2c3047dd5a15449d9d5680a2f73cb684
13 N86f1d44165d54c67bcf6cde63bae6ed2
14 sg:journal.1047644
15 schema:keywords algorithm
16 applications
17 bounds
18 checkpoint
19 competitiveness
20 compression
21 computation
22 data compression
23 debugging
24 direction
25 fact
26 factors
27 fast recomputation
28 intermediate results
29 line algorithm
30 lines
31 location
32 long computations
33 lower bounds
34 most computations
35 physical simulation
36 point
37 problem
38 recomputation
39 results
40 server
41 server problem
42 simulations
43 single direction
44 small factor
45 such checkpoints
46 whichk servers
47 schema:name On-line algorithms for locating checkpoints
48 schema:pagination 33-52
49 schema:productId N3b702c1937bd459a83fbc918df91b16f
50 Nbb7b6a7a1e934d73bef089d3d80cac7a
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019407387
52 https://doi.org/10.1007/bf01294262
53 schema:sdDatePublished 2022-01-01T18:06
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher N839885574102405892aa4227e7056528
56 schema:url https://doi.org/10.1007/bf01294262
57 sgo:license sg:explorer/license/
58 sgo:sdDataset articles
59 rdf:type schema:ScholarlyArticle
60 N1fcd18a03a8b452e8c2f4be95b1441cf rdf:first sg:person.014663420265.17
61 rdf:rest rdf:nil
62 N2c3047dd5a15449d9d5680a2f73cb684 schema:issueNumber 1
63 rdf:type schema:PublicationIssue
64 N3b702c1937bd459a83fbc918df91b16f schema:name doi
65 schema:value 10.1007/bf01294262
66 rdf:type schema:PropertyValue
67 N460de63481ba4b71bd28c18a182872bc rdf:first sg:person.013716363105.16
68 rdf:rest Ndc699ca9e6e94aceb877b49168160e50
69 N839885574102405892aa4227e7056528 schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 N86f1d44165d54c67bcf6cde63bae6ed2 schema:volumeNumber 11
72 rdf:type schema:PublicationVolume
73 Nbb7b6a7a1e934d73bef089d3d80cac7a schema:name dimensions_id
74 schema:value pub.1019407387
75 rdf:type schema:PropertyValue
76 Nc16a08b8c5ec4cdb8ef1626f1809abf3 rdf:first sg:person.0670701164.61
77 rdf:rest N460de63481ba4b71bd28c18a182872bc
78 Ndc699ca9e6e94aceb877b49168160e50 rdf:first sg:person.012752623315.11
79 rdf:rest N1fcd18a03a8b452e8c2f4be95b1441cf
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
84 schema:name Artificial Intelligence and Image Processing
85 rdf:type schema:DefinedTerm
86 sg:journal.1047644 schema:issn 0178-4617
87 1432-0541
88 schema:name Algorithmica
89 schema:publisher Springer Nature
90 rdf:type schema:Periodical
91 sg:person.012752623315.11 schema:affiliation grid-institutes:grid.47840.3f
92 schema:familyName Raghunathan
93 schema:givenName Arvind
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012752623315.11
95 rdf:type schema:Person
96 sg:person.013716363105.16 schema:affiliation grid-institutes:grid.482243.b
97 schema:familyName Greene
98 schema:givenName Daniel H.
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013716363105.16
100 rdf:type schema:Person
101 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.47840.3f
102 schema:familyName Sudan
103 schema:givenName Madhu
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
105 rdf:type schema:Person
106 sg:person.0670701164.61 schema:affiliation grid-institutes:grid.482243.b
107 schema:familyName Bern
108 schema:givenName Marshall
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0670701164.61
110 rdf:type schema:Person
111 sg:pub.10.1007/978-1-4612-1098-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021021236
112 https://doi.org/10.1007/978-1-4612-1098-6
113 rdf:type schema:CreativeWork
114 sg:pub.10.1007/bf01762111 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038306247
115 https://doi.org/10.1007/bf01762111
116 rdf:type schema:CreativeWork
117 grid-institutes:grid.47840.3f schema:alternateName Computer Science Division, University of California, 94720, Berkeley, CA, USA
118 Computer Science Division, University of California, 95616, Davis, CA, USA
119 schema:name Computer Science Division, University of California, 94720, Berkeley, CA, USA
120 Computer Science Division, University of California, 95616, Davis, CA, USA
121 rdf:type schema:Organization
122 grid-institutes:grid.482243.b schema:alternateName Xerox PARC, 3333 Coyote Hill Rd., 94304, Palo Alto, CA, USA
123 schema:name Xerox PARC, 3333 Coyote Hill Rd., 94304, Palo Alto, CA, USA
124 rdf:type schema:Organization
 




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


...