On random 2–3 trees View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1978-06

AUTHORS

Andrew Chi-Chih Yao

ABSTRACT

It is shown that ¯n (N), the average number of nodes in an N-key random 2–3 tree, satisfies the inequality 0.70 N < ¯n(N) <0.79 N for large N. A similar analysis is done for general B-trees. It is shown that storage utilization is essentially ln 2≈69% for B-tree of high orders. More... »

PAGES

159-170

References to SciGraph publications

Journal

TITLE

Acta Informatica

ISSUE

2

VOLUME

9

Author Affiliations

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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", 
    "author": [
      {
        "affiliation": {
          "alternateName": "Stanford University", 
          "id": "https://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Computer Science Department, Stanford University, 94305, Stanford, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yao", 
        "givenName": "Andrew Chi-Chih", 
        "id": "sg:person.015423051447.06", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015423051447.06"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf00288683", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032694395", 
          "https://doi.org/10.1007/bf00288683"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00288683", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032694395", 
          "https://doi.org/10.1007/bf00288683"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1978-06", 
    "datePublishedReg": "1978-06-01", 
    "description": "It is shown that \u00afn (N), the average number of nodes in an N-key random 2\u20133 tree, satisfies the inequality 0.70 N < \u00afn(N) <0.79 N for large N. A similar analysis is done for general B-trees. It is shown that storage utilization is essentially ln 2\u224869% for B-tree of high orders.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf00289075", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1133515", 
        "issn": [
          "0001-5903", 
          "1432-0525"
        ], 
        "name": "Acta Informatica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "9"
      }
    ], 
    "name": "On random 2\u20133 trees", 
    "pagination": "159-170", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf00289075"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "349f2aec28cace539af8f461134846656b81ea722d718f46550829ed470e623f"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011044660"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf00289075", 
      "https://app.dimensions.ai/details/publication/pub.1011044660"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-15T08:47", 
    "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/0000000374_0000000374/records_119713_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF00289075"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

57 TRIPLES      20 PREDICATES      26 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf00289075 schema:author Nc551141b625f4981b340150f88e3cc02
2 schema:citation sg:pub.10.1007/bf00288683
3 schema:datePublished 1978-06
4 schema:datePublishedReg 1978-06-01
5 schema:description It is shown that ¯n (N), the average number of nodes in an N-key random 2–3 tree, satisfies the inequality 0.70 N < ¯n(N) <0.79 N for large N. A similar analysis is done for general B-trees. It is shown that storage utilization is essentially ln 2≈69% for B-tree of high orders.
6 schema:genre research_article
7 schema:inLanguage en
8 schema:isAccessibleForFree false
9 schema:isPartOf N4bc79498783449c79236e181e504c411
10 Ne4aacfc9ff214cd9a9cfdb382d1ef169
11 sg:journal.1133515
12 schema:name On random 2–3 trees
13 schema:pagination 159-170
14 schema:productId N180eedeb29bd4109899f893c42a15fbb
15 N75ebd92bccc748a9a67072793f806887
16 Nce543bec74a0459ba765e17a163849b2
17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011044660
18 https://doi.org/10.1007/bf00289075
19 schema:sdDatePublished 2019-04-15T08:47
20 schema:sdLicense https://scigraph.springernature.com/explorer/license/
21 schema:sdPublisher N4ba2d56aac3c4f1ca653304e8f3435dc
22 schema:url http://link.springer.com/10.1007/BF00289075
23 sgo:license sg:explorer/license/
24 sgo:sdDataset articles
25 rdf:type schema:ScholarlyArticle
26 N180eedeb29bd4109899f893c42a15fbb schema:name dimensions_id
27 schema:value pub.1011044660
28 rdf:type schema:PropertyValue
29 N4ba2d56aac3c4f1ca653304e8f3435dc schema:name Springer Nature - SN SciGraph project
30 rdf:type schema:Organization
31 N4bc79498783449c79236e181e504c411 schema:issueNumber 2
32 rdf:type schema:PublicationIssue
33 N75ebd92bccc748a9a67072793f806887 schema:name doi
34 schema:value 10.1007/bf00289075
35 rdf:type schema:PropertyValue
36 Nc551141b625f4981b340150f88e3cc02 rdf:first sg:person.015423051447.06
37 rdf:rest rdf:nil
38 Nce543bec74a0459ba765e17a163849b2 schema:name readcube_id
39 schema:value 349f2aec28cace539af8f461134846656b81ea722d718f46550829ed470e623f
40 rdf:type schema:PropertyValue
41 Ne4aacfc9ff214cd9a9cfdb382d1ef169 schema:volumeNumber 9
42 rdf:type schema:PublicationVolume
43 sg:journal.1133515 schema:issn 0001-5903
44 1432-0525
45 schema:name Acta Informatica
46 rdf:type schema:Periodical
47 sg:person.015423051447.06 schema:affiliation https://www.grid.ac/institutes/grid.168010.e
48 schema:familyName Yao
49 schema:givenName Andrew Chi-Chih
50 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015423051447.06
51 rdf:type schema:Person
52 sg:pub.10.1007/bf00288683 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032694395
53 https://doi.org/10.1007/bf00288683
54 rdf:type schema:CreativeWork
55 https://www.grid.ac/institutes/grid.168010.e schema:alternateName Stanford University
56 schema:name Computer Science Department, Stanford University, 94305, Stanford, CA, USA
57 rdf:type schema:Organization
 




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


...