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 Nc98ad568737e4916957eb2f34d85f72d
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 N15469798f0544df897be2417384ea56b
11 N2ef5dea3428e4d128da6d24300a37131
12 sg:journal.1044889
13 schema:name An asymptotically optimal multiversion B-tree
14 schema:pagination 264-275
15 schema:productId N481d57f22b384811a11f90337e4833e1
16 N8738d7b6ba0e4620bea128629f9392bd
17 N8ee3ce3757104686967f64f7a3a4cebe
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 N922cd95dab7243ab99cfa221c757041a
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 N15469798f0544df897be2417384ea56b schema:volumeNumber 5
28 rdf:type schema:PublicationVolume
29 N2ef5dea3428e4d128da6d24300a37131 schema:issueNumber 4
30 rdf:type schema:PublicationIssue
31 N481d57f22b384811a11f90337e4833e1 schema:name readcube_id
32 schema:value 52a9209c9f4e03758dd6431d03a4a91d5ddb6a3cc18a6debdd59e4246e5015fe
33 rdf:type schema:PropertyValue
34 N4df28239a7cf4ea58fe3441db2b58445 rdf:first sg:person.016122374451.25
35 rdf:rest Nc469358c81184b338287023182b3f7ca
36 N601a2b745b544fc79611f8a90d4d3b31 schema:name isys software gmbh, Ensisheimer Str. 2a, D–79110 Freiburg, Germany, DE
37 rdf:type schema:Organization
38 N7a23dfaa7b364fb3872326c360d03d6d schema:name isys software gmbh, Ensisheimer Str. 2a, D–79110 Freiburg, Germany, DE
39 rdf:type schema:Organization
40 N8738d7b6ba0e4620bea128629f9392bd schema:name doi
41 schema:value 10.1007/s007780050028
42 rdf:type schema:PropertyValue
43 N8ee3ce3757104686967f64f7a3a4cebe schema:name dimensions_id
44 schema:value pub.1017349674
45 rdf:type schema:PropertyValue
46 N922cd95dab7243ab99cfa221c757041a schema:name Springer Nature - SN SciGraph project
47 rdf:type schema:Organization
48 Na3e41dfa94f747659899386a1ea63d42 rdf:first sg:person.0757144477.93
49 rdf:rest rdf:nil
50 Nb4fe3dfadff9434c82d6551c94bee449 rdf:first sg:person.016405114375.48
51 rdf:rest Na3e41dfa94f747659899386a1ea63d42
52 Nc469358c81184b338287023182b3f7ca rdf:first sg:person.016460110225.54
53 rdf:rest Nb4fe3dfadff9434c82d6551c94bee449
54 Nc98ad568737e4916957eb2f34d85f72d rdf:first sg:person.012602037221.74
55 rdf:rest N4df28239a7cf4ea58fe3441db2b58445
56 Nf8bbbec714964433950cf07a2c61870b 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 N601a2b745b544fc79611f8a90d4d3b31
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 Nf8bbbec714964433950cf07a2c61870b
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 N7a23dfaa7b364fb3872326c360d03d6d
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)


...