An asymptotically optimal multiversion B-tree View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1996-12

AUTHORS

Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer

ABSTRACT

In a variety of applications, we need to keep track of the development of a data set over time. For maintaining and querying these multiversion data efficiently, external storage structures are an absolute necessity. We propose a multiversion B-tree that supports insertions and deletions of data items at the current version and range queries and exact match queries for any version, current or past. Our multiversion B-tree is asymptotically optimal in the sense that the time and space bounds are asymptotically the same as those of the (single-version) B-tree in the worst case. The technique we present for transforming a (single-version) B-tree into a multiversion B-tree is quite general: it applies to a number of hierarchical external access structures with certain properties directly, and it can be modified for others. More... »

PAGES

264-275

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/0406", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Physical Geography and Environmental Geoscience", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/04", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Earth Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "isys software gmbh, Ensisheimer Str. 2a, D\u201379110 Freiburg, Germany, DE"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Becker", 
        "givenName": "Bruno", 
        "id": "sg:person.012602037221.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012602037221.74"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "isys software gmbh, Ensisheimer Str. 2a, D\u201379110 Freiburg, Germany, DE"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gschwind", 
        "givenName": "Stephan", 
        "id": "sg:person.016122374451.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016122374451.25"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "isys software gmbh, Ensisheimer Str. 2a, D\u201379110 Freiburg, Germany, DE"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ohler", 
        "givenName": "Thomas", 
        "id": "sg:person.016460110225.54", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016460110225.54"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Philipp University of Marburg", 
          "id": "https://www.grid.ac/institutes/grid.10253.35", 
          "name": [
            "Philipps-Universit\u00e4t Marburg, Fachbereich Mathematik, Fachgebiet Informatik, Hans-Meerwein-Strasse, D\u201335032 Marburg, Germany, DE"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Seeger", 
        "givenName": "Bernhard", 
        "id": "sg:person.016405114375.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016405114375.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Institut f\u00fcr Theoretische Informatik, ETH Zentrum, CH-8092 Z\u00fcrich,\nSwitzerland\u00b6 Tel. ++41-1-63-27400, Fax ++41-1-63-21172, email: widmayer@inf.ethz.ch, CH"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Widmayer", 
        "givenName": "Peter", 
        "id": "sg:person.0757144477.93", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0757144477.93"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1996-12", 
    "datePublishedReg": "1996-12-01", 
    "description": "In a variety of applications, we need to keep track of the development of a data set over time. For maintaining and querying these multiversion data efficiently, external storage structures are an absolute necessity. We propose a multiversion B-tree that supports insertions and deletions of data items at the current version and range queries and exact match queries for any version, current or past. Our multiversion B-tree is asymptotically optimal in the sense that the time and space bounds are asymptotically the same as those of the (single-version) B-tree in the worst case. The technique we present for transforming a (single-version) B-tree into a multiversion B-tree is quite general: it applies to a number of hierarchical external access structures with certain properties directly, and it can be modified for others.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s007780050028", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1044889", 
        "issn": [
          "1066-8888", 
          "0949-877X"
        ], 
        "name": "The VLDB Journal", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "5"
      }
    ], 
    "name": "An asymptotically optimal multiversion B-tree", 
    "pagination": "264-275", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "52a9209c9f4e03758dd6431d03a4a91d5ddb6a3cc18a6debdd59e4246e5015fe"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s007780050028"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017349674"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s007780050028", 
      "https://app.dimensions.ai/details/publication/pub.1017349674"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T00:09", 
    "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_8695_00000480.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/s007780050028"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

98 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s007780050028 schema:about anzsrc-for:04
2 anzsrc-for:0406
3 schema:author N09ad403cec4444c09a00484532863b72
4 schema:datePublished 1996-12
5 schema:datePublishedReg 1996-12-01
6 schema:description In a variety of applications, we need to keep track of the development of a data set over time. For maintaining and querying these multiversion data efficiently, external storage structures are an absolute necessity. We propose a multiversion B-tree that supports insertions and deletions of data items at the current version and range queries and exact match queries for any version, current or past. Our multiversion B-tree is asymptotically optimal in the sense that the time and space bounds are asymptotically the same as those of the (single-version) B-tree in the worst case. The technique we present for transforming a (single-version) B-tree into a multiversion B-tree is quite general: it applies to a number of hierarchical external access structures with certain properties directly, and it can be modified for others.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf Nba888941b7f346d694c83b89d36ff0d5
11 Ne3c1a2fb75f246e8bdc5280f793a9341
12 sg:journal.1044889
13 schema:name An asymptotically optimal multiversion B-tree
14 schema:pagination 264-275
15 schema:productId N896c3fa6a45741e2b64ad7cb384c680a
16 Ne454d937b6214cde8ec301715de2b179
17 Nf6352bc459104bdfa567ecca33f865a8
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017349674
19 https://doi.org/10.1007/s007780050028
20 schema:sdDatePublished 2019-04-11T00:09
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N9d263199ec5946c697db621b2c7bdba8
23 schema:url http://link.springer.com/10.1007/s007780050028
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N046d433e0ffb4078821c0573421fe43b rdf:first sg:person.016460110225.54
28 rdf:rest N4d41e7d2c72540c09eeece5b38779b13
29 N095eb62b62134d93913bed25b3b2209f rdf:first sg:person.0757144477.93
30 rdf:rest rdf:nil
31 N09ad403cec4444c09a00484532863b72 rdf:first sg:person.012602037221.74
32 rdf:rest N305b97fcc3304b2ca31b3d9737399984
33 N0f1bee1d90c042a6ab646d8a53e202bf schema:name isys software gmbh, Ensisheimer Str. 2a, D–79110 Freiburg, Germany, DE
34 rdf:type schema:Organization
35 N304282e388104099a94114ff87e75ba1 schema:name isys software gmbh, Ensisheimer Str. 2a, D–79110 Freiburg, Germany, DE
36 rdf:type schema:Organization
37 N305b97fcc3304b2ca31b3d9737399984 rdf:first sg:person.016122374451.25
38 rdf:rest N046d433e0ffb4078821c0573421fe43b
39 N4d41e7d2c72540c09eeece5b38779b13 rdf:first sg:person.016405114375.48
40 rdf:rest N095eb62b62134d93913bed25b3b2209f
41 N896c3fa6a45741e2b64ad7cb384c680a schema:name readcube_id
42 schema:value 52a9209c9f4e03758dd6431d03a4a91d5ddb6a3cc18a6debdd59e4246e5015fe
43 rdf:type schema:PropertyValue
44 N9d263199ec5946c697db621b2c7bdba8 schema:name Springer Nature - SN SciGraph project
45 rdf:type schema:Organization
46 Nba888941b7f346d694c83b89d36ff0d5 schema:issueNumber 4
47 rdf:type schema:PublicationIssue
48 Ne3c1a2fb75f246e8bdc5280f793a9341 schema:volumeNumber 5
49 rdf:type schema:PublicationVolume
50 Ne454d937b6214cde8ec301715de2b179 schema:name doi
51 schema:value 10.1007/s007780050028
52 rdf:type schema:PropertyValue
53 Nf6352bc459104bdfa567ecca33f865a8 schema:name dimensions_id
54 schema:value pub.1017349674
55 rdf:type schema:PropertyValue
56 Nf8fa94f6acd44def8e940656f441573b schema:name isys software gmbh, Ensisheimer Str. 2a, D–79110 Freiburg, Germany, DE
57 rdf:type schema:Organization
58 anzsrc-for:04 schema:inDefinedTermSet anzsrc-for:
59 schema:name Earth Sciences
60 rdf:type schema:DefinedTerm
61 anzsrc-for:0406 schema:inDefinedTermSet anzsrc-for:
62 schema:name Physical Geography and Environmental Geoscience
63 rdf:type schema:DefinedTerm
64 sg:journal.1044889 schema:issn 0949-877X
65 1066-8888
66 schema:name The VLDB Journal
67 rdf:type schema:Periodical
68 sg:person.012602037221.74 schema:affiliation N304282e388104099a94114ff87e75ba1
69 schema:familyName Becker
70 schema:givenName Bruno
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012602037221.74
72 rdf:type schema:Person
73 sg:person.016122374451.25 schema:affiliation N0f1bee1d90c042a6ab646d8a53e202bf
74 schema:familyName Gschwind
75 schema:givenName Stephan
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016122374451.25
77 rdf:type schema:Person
78 sg:person.016405114375.48 schema:affiliation https://www.grid.ac/institutes/grid.10253.35
79 schema:familyName Seeger
80 schema:givenName Bernhard
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016405114375.48
82 rdf:type schema:Person
83 sg:person.016460110225.54 schema:affiliation Nf8fa94f6acd44def8e940656f441573b
84 schema:familyName Ohler
85 schema:givenName Thomas
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016460110225.54
87 rdf:type schema:Person
88 sg:person.0757144477.93 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
89 schema:familyName Widmayer
90 schema:givenName Peter
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0757144477.93
92 rdf:type schema:Person
93 https://www.grid.ac/institutes/grid.10253.35 schema:alternateName Philipp University of Marburg
94 schema:name Philipps-Universität Marburg, Fachbereich Mathematik, Fachgebiet Informatik, Hans-Meerwein-Strasse, D–35032 Marburg, Germany, DE
95 rdf:type schema:Organization
96 https://www.grid.ac/institutes/grid.5801.c schema:alternateName Swiss Federal Institute of Technology in Zurich
97 schema:name Institut für Theoretische Informatik, ETH Zentrum, CH-8092 Zürich, Switzerland¶ Tel. ++41-1-63-27400, Fax ++41-1-63-21172, email: widmayer@inf.ethz.ch, CH
98 rdf:type schema:Organization
 




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


...