Online Data Structures in External Memory View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002-07-18

AUTHORS

Jeffrey Scott Vitter

ABSTRACT

The data sets for many of today’s computer applications are too large to fit within the computer’s internal memory and must instead be stored on external storage devices such as disks. A major performance bottleneck can be the input/output communication (or I/O) between the external and internal memories. In this paper we discuss a variety of on-line data structures for external memory—some very old and some very new—such as hashing (for dictionaries), B-trees (for dictionaries and 1-D range search), buffer trees (for batched dynamic problems), interval trees with weight-balanced B-trees (for stabbing queries), priority search trees (for 3-sided 2-D range search), and R-trees and other spatial structures. We also discuss several open problems along the way. More... »

PAGES

352-366

References to SciGraph publications

  • 1994-09. Coding techniques for handling failures in large disk arrays in ALGORITHMICA
  • 1997-08. Concurrency and recovery for index trees in THE VLDB JOURNAL
  • 2005-06-14. Efficient memory access in large-scale computation in STACS 91
  • 1983-12. On the performance evaluation of extendible hashing and trie searching in ACTA INFORMATICA
  • 1994-09. Algorithms for parallel memory, I: Two-level memories in ALGORITHMICA
  • 1978-06. On random 2–3 trees in ACTA INFORMATICA
  • 1989-03. Expected behaviour of B+-trees under random insertions in ACTA INFORMATICA
  • 1998. Worst-case efficient external-memory priority queues in ALGORITHM THEORY — SWAT'98
  • 1996-12. An asymptotically optimal multiversion B-tree in THE VLDB JOURNAL
  • 2002-04-19. Efficient Bulk Operations on Dynamic R-trees in ALGORITHM ENGINEERING AND EXPERIMENTATION
  • 1972-09. Organization and maintenance of large ordered indexes in ACTA INFORMATICA
  • 1997. Efficient splitting and merging algorithms for order decomposable problems in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1987-06. Linear space data structures for two types of range search in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1995. The buffer tree: A new technique for optimal I/O-algorithms in ALGORITHMS AND DATA STRUCTURES
  • 1995. Topology B-trees and their applications in ALGORITHMS AND DATA STRUCTURES
  • 1997. Spatial data structures: Concepts and design choices in ALGORITHMIC FOUNDATIONS OF GEOGRAPHIC INFORMATION SYSTEMS
  • 1983-04. Storage utilization in B*-trees with a generalized overflow technique in ACTA INFORMATICA
  • 1997-02. The hB\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $^\Pi$\end{document}-tree: a multi-attribute index supporting concurrency, recovery and node consolidation in THE VLDB JOURNAL
  • Book

    TITLE

    Algorithms and Data Structures

    ISBN

    978-3-540-66279-2
    978-3-540-48447-9

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-48447-7_35

    DOI

    http://dx.doi.org/10.1007/3-540-48447-7_35

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Duke University", 
              "id": "https://www.grid.ac/institutes/grid.26009.3d", 
              "name": [
                "Department of Computer Science, Duke University, Center for Geometric Computing, 27708-0129, Durham, NC, USA", 
                "I.N.R.I.A. Sophia Antipolis, B.P. 93, 2004 route des Lucioles, 06902, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Vitter", 
            "givenName": "Jeffrey Scott", 
            "id": "sg:person.0613677314.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/46157.330532", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000336556"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/170088.170403", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003526327"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00264279", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004131693", 
              "https://doi.org/10.1007/bf00264279"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00264279", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004131693", 
              "https://doi.org/10.1007/bf00264279"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0020785", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006333313", 
              "https://doi.org/10.1007/bfb0020785"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0020785", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006333313", 
              "https://doi.org/10.1007/bfb0020785"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/77600.77614", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007189276"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187875", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007885308", 
              "https://doi.org/10.1007/bf02187875"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187875", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007885308", 
              "https://doi.org/10.1007/bf02187875"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/00207168308803365", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008948418"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00289146", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009471442", 
              "https://doi.org/10.1007/bf00289146"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00289146", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009471442", 
              "https://doi.org/10.1007/bf00289146"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00289075", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011044660", 
              "https://doi.org/10.1007/bf00289075"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00289075", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011044660", 
              "https://doi.org/10.1007/bf00289075"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/237814.237864", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011126443"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/176979.176981", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013288182"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s007780050028", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017349674", 
              "https://doi.org/10.1007/s007780050028"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-60220-8_74", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019870666", 
              "https://doi.org/10.1007/3-540-60220-8_74"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s007780050042", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020058837", 
              "https://doi.org/10.1007/s007780050042"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-63818-0_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020480392", 
              "https://doi.org/10.1007/3-540-63818-0_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/275487.275506", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020791293"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00263927", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021075875", 
              "https://doi.org/10.1007/bf00263927"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00263927", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021075875", 
              "https://doi.org/10.1007/bf00263927"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/275487.275493", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021383255"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01185210", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022046505", 
              "https://doi.org/10.1007/bf01185210"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01185210", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022046505", 
              "https://doi.org/10.1007/bf01185210"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/00207168308803364", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023137716"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s007780050030", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025046019", 
              "https://doi.org/10.1007/s007780050030"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-63165-8_215", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026027828", 
              "https://doi.org/10.1007/3-540-63165-8_215"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/263661.263688", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027864880"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48518-x_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028875757", 
              "https://doi.org/10.1007/3-540-48518-x_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48518-x_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028875757", 
              "https://doi.org/10.1007/3-540-48518-x_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/242223.242300", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030410788"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/3828.3839", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030549658"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/356770.356776", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030753621"
            ], 
            "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"
          }, 
          {
            "id": "sg:pub.10.1007/bf00288683", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032694395", 
              "https://doi.org/10.1007/bf00288683"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/320083.320092", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032759545"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0054359", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038889755", 
              "https://doi.org/10.1007/bfb0054359"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/277851.277906", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040238186"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/358841.358850", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040442112"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/303976.304010", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043153209"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/582318.582321", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044720644"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01185207", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045195394", 
              "https://doi.org/10.1007/bf01185207"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01185207", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045195394", 
              "https://doi.org/10.1007/bf01185207"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/275487.275494", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045851470"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/99935.99949", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047328192"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/348.318586", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049066804"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/280277.280279", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050640610"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-60220-8_78", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051329312", 
              "https://doi.org/10.1007/3-540-60220-8_78"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jcss.1996.0043", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053243165"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/2.268881", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061105270"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/69.599929", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061213593"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tse.1982.236022", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061787547"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0214021", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841810"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0215051", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841913"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icde.1989.47268", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086180375"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/conm/223/03131", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1089203810"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1996.548515", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094835330"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/dimacs/050", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1097022689"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2002-07-18", 
        "datePublishedReg": "2002-07-18", 
        "description": "The data sets for many of today\u2019s computer applications are too large to fit within the computer\u2019s internal memory and must instead be stored on external storage devices such as disks. A major performance bottleneck can be the input/output communication (or I/O) between the external and internal memories. In this paper we discuss a variety of on-line data structures for external memory\u2014some very old and some very new\u2014such as hashing (for dictionaries), B-trees (for dictionaries and 1-D range search), buffer trees (for batched dynamic problems), interval trees with weight-balanced B-trees (for stabbing queries), priority search trees (for 3-sided 2-D range search), and R-trees and other spatial structures. We also discuss several open problems along the way.", 
        "editor": [
          {
            "familyName": "Dehne", 
            "givenName": "Frank", 
            "type": "Person"
          }, 
          {
            "familyName": "Sack", 
            "givenName": "J\u00f6rg-R\u00fcdiger", 
            "type": "Person"
          }, 
          {
            "familyName": "Gupta", 
            "givenName": "Arvind", 
            "type": "Person"
          }, 
          {
            "familyName": "Tamassia", 
            "givenName": "Roberto", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-48447-7_35", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-66279-2", 
            "978-3-540-48447-9"
          ], 
          "name": "Algorithms and Data Structures", 
          "type": "Book"
        }, 
        "name": "Online Data Structures in External Memory", 
        "pagination": "352-366", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-48447-7_35"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "61b2425b49d0623d46095cde9c1968d41834436439d65d38b9b651b9dccecc76"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1020503512"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-48447-7_35", 
          "https://app.dimensions.ai/details/publication/pub.1020503512"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:42", 
        "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/0000000347_0000000347/records_89789_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F3-540-48447-7_35"
      }
    ]
     

    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/3-540-48447-7_35'

    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/3-540-48447-7_35'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48447-7_35'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-48447-7_35'


     

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

    249 TRIPLES      23 PREDICATES      76 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-48447-7_35 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nd663348b9f304d2087a264ff1ac7ffaa
    4 schema:citation sg:pub.10.1007/3-540-48518-x_20
    5 sg:pub.10.1007/3-540-60220-8_74
    6 sg:pub.10.1007/3-540-60220-8_78
    7 sg:pub.10.1007/3-540-63165-8_215
    8 sg:pub.10.1007/3-540-63818-0_6
    9 sg:pub.10.1007/bf00263927
    10 sg:pub.10.1007/bf00264279
    11 sg:pub.10.1007/bf00288683
    12 sg:pub.10.1007/bf00289075
    13 sg:pub.10.1007/bf00289146
    14 sg:pub.10.1007/bf01185207
    15 sg:pub.10.1007/bf01185210
    16 sg:pub.10.1007/bf02187875
    17 sg:pub.10.1007/bfb0020785
    18 sg:pub.10.1007/bfb0054359
    19 sg:pub.10.1007/s007780050028
    20 sg:pub.10.1007/s007780050030
    21 sg:pub.10.1007/s007780050042
    22 https://doi.org/10.1006/jcss.1996.0043
    23 https://doi.org/10.1080/00207168308803364
    24 https://doi.org/10.1080/00207168308803365
    25 https://doi.org/10.1090/conm/223/03131
    26 https://doi.org/10.1090/dimacs/050
    27 https://doi.org/10.1109/2.268881
    28 https://doi.org/10.1109/69.599929
    29 https://doi.org/10.1109/icde.1989.47268
    30 https://doi.org/10.1109/sfcs.1996.548515
    31 https://doi.org/10.1109/tse.1982.236022
    32 https://doi.org/10.1137/0214021
    33 https://doi.org/10.1137/0215051
    34 https://doi.org/10.1145/170088.170403
    35 https://doi.org/10.1145/176979.176981
    36 https://doi.org/10.1145/237814.237864
    37 https://doi.org/10.1145/242223.242300
    38 https://doi.org/10.1145/263661.263688
    39 https://doi.org/10.1145/275487.275493
    40 https://doi.org/10.1145/275487.275494
    41 https://doi.org/10.1145/275487.275506
    42 https://doi.org/10.1145/277851.277906
    43 https://doi.org/10.1145/280277.280279
    44 https://doi.org/10.1145/303976.304010
    45 https://doi.org/10.1145/320083.320092
    46 https://doi.org/10.1145/348.318586
    47 https://doi.org/10.1145/356770.356776
    48 https://doi.org/10.1145/358841.358850
    49 https://doi.org/10.1145/3828.3839
    50 https://doi.org/10.1145/46157.330532
    51 https://doi.org/10.1145/582318.582321
    52 https://doi.org/10.1145/77600.77614
    53 https://doi.org/10.1145/99935.99949
    54 schema:datePublished 2002-07-18
    55 schema:datePublishedReg 2002-07-18
    56 schema:description The data sets for many of today’s computer applications are too large to fit within the computer’s internal memory and must instead be stored on external storage devices such as disks. A major performance bottleneck can be the input/output communication (or I/O) between the external and internal memories. In this paper we discuss a variety of on-line data structures for external memory—some very old and some very new—such as hashing (for dictionaries), B-trees (for dictionaries and 1-D range search), buffer trees (for batched dynamic problems), interval trees with weight-balanced B-trees (for stabbing queries), priority search trees (for 3-sided 2-D range search), and R-trees and other spatial structures. We also discuss several open problems along the way.
    57 schema:editor N59340f28b89f44ce8de240ee60ca668d
    58 schema:genre chapter
    59 schema:inLanguage en
    60 schema:isAccessibleForFree true
    61 schema:isPartOf Nce68ea2e4e2c4d38a74c9548019661d4
    62 schema:name Online Data Structures in External Memory
    63 schema:pagination 352-366
    64 schema:productId N1600d11e93a74a28a1f95c509c3e5c81
    65 N34c006fccb834d8ba41583e877da65ed
    66 N5459b283bbd14324a1662246875e18de
    67 schema:publisher Ne9caf25b8f1541d5862711d6cfaf19cc
    68 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020503512
    69 https://doi.org/10.1007/3-540-48447-7_35
    70 schema:sdDatePublished 2019-04-16T05:42
    71 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    72 schema:sdPublisher N71dff25475004d61a53a9c75d32f9cd0
    73 schema:url https://link.springer.com/10.1007%2F3-540-48447-7_35
    74 sgo:license sg:explorer/license/
    75 sgo:sdDataset chapters
    76 rdf:type schema:Chapter
    77 N1600d11e93a74a28a1f95c509c3e5c81 schema:name dimensions_id
    78 schema:value pub.1020503512
    79 rdf:type schema:PropertyValue
    80 N18476a9aedfe41b8a9018d51bfd91203 schema:familyName Gupta
    81 schema:givenName Arvind
    82 rdf:type schema:Person
    83 N34c006fccb834d8ba41583e877da65ed schema:name doi
    84 schema:value 10.1007/3-540-48447-7_35
    85 rdf:type schema:PropertyValue
    86 N39138fb376274a73a7ae67368abcdc2d rdf:first Na342713cfab943b5bcb58aa713ed4066
    87 rdf:rest rdf:nil
    88 N5459b283bbd14324a1662246875e18de schema:name readcube_id
    89 schema:value 61b2425b49d0623d46095cde9c1968d41834436439d65d38b9b651b9dccecc76
    90 rdf:type schema:PropertyValue
    91 N59340f28b89f44ce8de240ee60ca668d rdf:first Nc842d42e76864451be9a52ea764b4ddd
    92 rdf:rest Ne73d58697aa34294b45daf2d2d79c480
    93 N71dff25475004d61a53a9c75d32f9cd0 schema:name Springer Nature - SN SciGraph project
    94 rdf:type schema:Organization
    95 N8d25925ad58d4ddc8a097a9f6ccf3dfa schema:familyName Sack
    96 schema:givenName Jörg-Rüdiger
    97 rdf:type schema:Person
    98 Na342713cfab943b5bcb58aa713ed4066 schema:familyName Tamassia
    99 schema:givenName Roberto
    100 rdf:type schema:Person
    101 Nae07fcac87ed4e4882e7df60e88a59b8 rdf:first N18476a9aedfe41b8a9018d51bfd91203
    102 rdf:rest N39138fb376274a73a7ae67368abcdc2d
    103 Nc842d42e76864451be9a52ea764b4ddd schema:familyName Dehne
    104 schema:givenName Frank
    105 rdf:type schema:Person
    106 Nce68ea2e4e2c4d38a74c9548019661d4 schema:isbn 978-3-540-48447-9
    107 978-3-540-66279-2
    108 schema:name Algorithms and Data Structures
    109 rdf:type schema:Book
    110 Nd663348b9f304d2087a264ff1ac7ffaa rdf:first sg:person.0613677314.28
    111 rdf:rest rdf:nil
    112 Ne73d58697aa34294b45daf2d2d79c480 rdf:first N8d25925ad58d4ddc8a097a9f6ccf3dfa
    113 rdf:rest Nae07fcac87ed4e4882e7df60e88a59b8
    114 Ne9caf25b8f1541d5862711d6cfaf19cc schema:location Berlin, Heidelberg
    115 schema:name Springer Berlin Heidelberg
    116 rdf:type schema:Organisation
    117 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    118 schema:name Information and Computing Sciences
    119 rdf:type schema:DefinedTerm
    120 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    121 schema:name Computation Theory and Mathematics
    122 rdf:type schema:DefinedTerm
    123 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
    124 schema:familyName Vitter
    125 schema:givenName Jeffrey Scott
    126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
    127 rdf:type schema:Person
    128 sg:pub.10.1007/3-540-48518-x_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028875757
    129 https://doi.org/10.1007/3-540-48518-x_20
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/3-540-60220-8_74 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019870666
    132 https://doi.org/10.1007/3-540-60220-8_74
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/3-540-60220-8_78 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051329312
    135 https://doi.org/10.1007/3-540-60220-8_78
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/3-540-63165-8_215 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026027828
    138 https://doi.org/10.1007/3-540-63165-8_215
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/3-540-63818-0_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020480392
    141 https://doi.org/10.1007/3-540-63818-0_6
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/bf00263927 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021075875
    144 https://doi.org/10.1007/bf00263927
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/bf00264279 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004131693
    147 https://doi.org/10.1007/bf00264279
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/bf00288683 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032694395
    150 https://doi.org/10.1007/bf00288683
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1007/bf00289075 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011044660
    153 https://doi.org/10.1007/bf00289075
    154 rdf:type schema:CreativeWork
    155 sg:pub.10.1007/bf00289146 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009471442
    156 https://doi.org/10.1007/bf00289146
    157 rdf:type schema:CreativeWork
    158 sg:pub.10.1007/bf01185207 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045195394
    159 https://doi.org/10.1007/bf01185207
    160 rdf:type schema:CreativeWork
    161 sg:pub.10.1007/bf01185210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022046505
    162 https://doi.org/10.1007/bf01185210
    163 rdf:type schema:CreativeWork
    164 sg:pub.10.1007/bf02187875 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007885308
    165 https://doi.org/10.1007/bf02187875
    166 rdf:type schema:CreativeWork
    167 sg:pub.10.1007/bfb0020785 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006333313
    168 https://doi.org/10.1007/bfb0020785
    169 rdf:type schema:CreativeWork
    170 sg:pub.10.1007/bfb0054359 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038889755
    171 https://doi.org/10.1007/bfb0054359
    172 rdf:type schema:CreativeWork
    173 sg:pub.10.1007/s007780050028 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017349674
    174 https://doi.org/10.1007/s007780050028
    175 rdf:type schema:CreativeWork
    176 sg:pub.10.1007/s007780050030 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025046019
    177 https://doi.org/10.1007/s007780050030
    178 rdf:type schema:CreativeWork
    179 sg:pub.10.1007/s007780050042 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020058837
    180 https://doi.org/10.1007/s007780050042
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1006/jcss.1996.0043 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053243165
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.1080/00207168308803364 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023137716
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.1080/00207168308803365 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008948418
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.1090/conm/223/03131 schema:sameAs https://app.dimensions.ai/details/publication/pub.1089203810
    189 rdf:type schema:CreativeWork
    190 https://doi.org/10.1090/dimacs/050 schema:sameAs https://app.dimensions.ai/details/publication/pub.1097022689
    191 rdf:type schema:CreativeWork
    192 https://doi.org/10.1109/2.268881 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061105270
    193 rdf:type schema:CreativeWork
    194 https://doi.org/10.1109/69.599929 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061213593
    195 rdf:type schema:CreativeWork
    196 https://doi.org/10.1109/icde.1989.47268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086180375
    197 rdf:type schema:CreativeWork
    198 https://doi.org/10.1109/sfcs.1996.548515 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094835330
    199 rdf:type schema:CreativeWork
    200 https://doi.org/10.1109/tse.1982.236022 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061787547
    201 rdf:type schema:CreativeWork
    202 https://doi.org/10.1137/0214021 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841810
    203 rdf:type schema:CreativeWork
    204 https://doi.org/10.1137/0215051 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841913
    205 rdf:type schema:CreativeWork
    206 https://doi.org/10.1145/170088.170403 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003526327
    207 rdf:type schema:CreativeWork
    208 https://doi.org/10.1145/176979.176981 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013288182
    209 rdf:type schema:CreativeWork
    210 https://doi.org/10.1145/237814.237864 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011126443
    211 rdf:type schema:CreativeWork
    212 https://doi.org/10.1145/242223.242300 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030410788
    213 rdf:type schema:CreativeWork
    214 https://doi.org/10.1145/263661.263688 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027864880
    215 rdf:type schema:CreativeWork
    216 https://doi.org/10.1145/275487.275493 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021383255
    217 rdf:type schema:CreativeWork
    218 https://doi.org/10.1145/275487.275494 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045851470
    219 rdf:type schema:CreativeWork
    220 https://doi.org/10.1145/275487.275506 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020791293
    221 rdf:type schema:CreativeWork
    222 https://doi.org/10.1145/277851.277906 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040238186
    223 rdf:type schema:CreativeWork
    224 https://doi.org/10.1145/280277.280279 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050640610
    225 rdf:type schema:CreativeWork
    226 https://doi.org/10.1145/303976.304010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043153209
    227 rdf:type schema:CreativeWork
    228 https://doi.org/10.1145/320083.320092 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032759545
    229 rdf:type schema:CreativeWork
    230 https://doi.org/10.1145/348.318586 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049066804
    231 rdf:type schema:CreativeWork
    232 https://doi.org/10.1145/356770.356776 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030753621
    233 rdf:type schema:CreativeWork
    234 https://doi.org/10.1145/358841.358850 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040442112
    235 rdf:type schema:CreativeWork
    236 https://doi.org/10.1145/3828.3839 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030549658
    237 rdf:type schema:CreativeWork
    238 https://doi.org/10.1145/46157.330532 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000336556
    239 rdf:type schema:CreativeWork
    240 https://doi.org/10.1145/582318.582321 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044720644
    241 rdf:type schema:CreativeWork
    242 https://doi.org/10.1145/77600.77614 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007189276
    243 rdf:type schema:CreativeWork
    244 https://doi.org/10.1145/99935.99949 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047328192
    245 rdf:type schema:CreativeWork
    246 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
    247 schema:name Department of Computer Science, Duke University, Center for Geometric Computing, 27708-0129, Durham, NC, USA
    248 I.N.R.I.A. Sophia Antipolis, B.P. 93, 2004 route des Lucioles, 06902, France
    249 rdf:type schema:Organization
     




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


    ...