External Memory Algorithms View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-03-15

AUTHORS

Jeffrey Scott Vitter

ABSTRACT

Data sets in large applications are often too massive to fit completely inside the computer’s internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. In this tutorial, we survey the state of the art in the design and analysis of external memory algorithms (also known as EM algorithms or out-of-core algorithms or I/O algorithms). External memory algorithms are often designed using the parallel disk model (PDM). The three machine-independent measures of an algorithm’s performance in PDM are the number of I/O operations performed, the CPU time, and the amount of disk space used. PDM allows for multiple disks (or disk arrays) and parallel CPUs, and it can be generalized to handle cache hierarchies, hierarchical memory, and tertiary storage. We discuss a variety of problems and show how to solve them efficiently in external memory. Programming tools and environments are available for simplifying the programming task. Experiments on some newly developed algorithms for spatial databases incorporating these paradigms, implemented using TPIE (Transparent Parallel I/O programming Environment), show significant speedups over popular methods. More... »

PAGES

1-25

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
  • 1994-09. Algorithms for parallel memory, II: Hierarchical multilevel memories in ALGORITHMICA
  • 1994-09. Algorithms for parallel memory, I: Two-level memories in ALGORITHMICA
  • 1989-10. Applications of random sampling in computational geometry, II in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1995. The I/O-complexity of Ordered Binary-Decision Diagram manipulation in ALGORITHMS AND COMPUTATIONS
  • 1995. Topology B-trees and their applications in ALGORITHMS AND DATA STRUCTURES
  • 1991-06. The input/output complexity of transitive closure in ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE
  • 1996-08. Blocking for external graph searching in ALGORITHMICA
  • 1997. Efficient splitting and merging algorithms for order decomposable problems in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1993. A general lower bound on the I/O-complexity of comparison-based algorithms in ALGORITHMS AND DATA STRUCTURES
  • 1996-02. Optimal cooperative search in fractional cascaded data structures in ALGORITHMICA
  • 1995. The buffer tree: A new technique for optimal I/O-algorithms in ALGORITHMS AND DATA STRUCTURES
  • 1997. Spatial data structures: Concepts and design choices in ALGORITHMIC FOUNDATIONS OF GEOGRAPHIC INFORMATION SYSTEMS
  • 1995. Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep in ALGORITHMS AND DATA STRUCTURES
  • 1997. BSP-like external-memory computation in ALGORITHMS AND COMPLEXITY
  • 1972-09. Organization and maintenance of large ordered indexes in ACTA INFORMATICA
  • 1996-12. An asymptotically optimal multiversion B-tree in THE VLDB JOURNAL
  • 1972. Permuting Information in Idealized Two-Level Storage in COMPLEXITY OF COMPUTER COMPUTATIONS
  • Book

    TITLE

    Algorithms — ESA’ 98

    ISBN

    978-3-540-64848-2
    978-3-540-68530-2

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-68530-8_1

    DOI

    http://dx.doi.org/10.1007/3-540-68530-8_1

    DIMENSIONS

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


    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": [
                "Center for Geometric Computing, Department of Computer Science, Duke University, 27708-0129, Durham, NC, USA"
              ], 
              "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/7921.11325", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000895227"
            ], 
            "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/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": "sg:pub.10.1007/bf01185208", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006484027", 
              "https://doi.org/10.1007/bf01185208"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01185208", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006484027", 
              "https://doi.org/10.1007/bf01185208"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-62592-5_75", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007327628", 
              "https://doi.org/10.1007/3-540-62592-5_75"
            ], 
            "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": "https://doi.org/10.1145/48529.48535", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014013712"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/210332.210343", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014625708"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01940646", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016252575", 
              "https://doi.org/10.1007/bf01940646"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01940646", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016252575", 
              "https://doi.org/10.1007/bf01940646"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0019-9958(84)80015-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016709409"
            ], 
            "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": "https://doi.org/10.1016/0022-0000(89)90034-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018960222"
            ], 
            "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/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": "sg:pub.10.1007/bf01941686", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022526168", 
              "https://doi.org/10.1007/bf01941686"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01941686", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022526168", 
              "https://doi.org/10.1007/bf01941686"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0167-8191(97)00015-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023784729"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/93597.98741", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025736774"
            ], 
            "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": "https://doi.org/10.1145/165231.165247", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028273198"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0015411", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029881376", 
              "https://doi.org/10.1007/bfb0015411"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/236017.236029", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030282918"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/10637199608915543", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031164865"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01530929", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031507992", 
              "https://doi.org/10.1007/bf01530929"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-57155-8_238", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031880279", 
              "https://doi.org/10.1007/3-540-57155-8_238"
            ], 
            "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/225058.225287", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034584204"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-0000(93)90043-v", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036852105"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/258492.258503", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039074543"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/277851.277906", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040238186"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4684-2001-2_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040405414", 
              "https://doi.org/10.1007/978-1-4684-2001-2_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187740", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041585569", 
              "https://doi.org/10.1007/bf02187740"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187740", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041585569", 
              "https://doi.org/10.1007/bf02187740"
            ], 
            "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.275501", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047551077"
            ], 
            "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": "sg:pub.10.1007/3-540-60220-8_75", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051465486", 
              "https://doi.org/10.1007/3-540-60220-8_75"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/12.83622", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061089095"
            ], 
            "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/tc.1981.1675790", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061532562"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.1985.5009385", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061533266"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0215021", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841883"
            ], 
            "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.1109/pdis.1991.183115", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086296319"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1993.366817", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086297219"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1993.366816", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086354005"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/spdp.1996.570330", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1093315978"
            ], 
            "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.1109/sfcs.1996.548476", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094987476"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2002-03-15", 
        "datePublishedReg": "2002-03-15", 
        "description": "Data sets in large applications are often too massive to fit completely inside the computer\u2019s internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. In this tutorial, we survey the state of the art in the design and analysis of external memory algorithms (also known as EM algorithms or out-of-core algorithms or I/O algorithms). External memory algorithms are often designed using the parallel disk model (PDM). The three machine-independent measures of an algorithm\u2019s performance in PDM are the number of I/O operations performed, the CPU time, and the amount of disk space used. PDM allows for multiple disks (or disk arrays) and parallel CPUs, and it can be generalized to handle cache hierarchies, hierarchical memory, and tertiary storage. We discuss a variety of problems and show how to solve them efficiently in external memory. Programming tools and environments are available for simplifying the programming task. Experiments on some newly developed algorithms for spatial databases incorporating these paradigms, implemented using TPIE (Transparent Parallel I/O programming Environment), show significant speedups over popular methods.", 
        "editor": [
          {
            "familyName": "Bilardi", 
            "givenName": "Gianfranco", 
            "type": "Person"
          }, 
          {
            "familyName": "Italiano", 
            "givenName": "Giuseppe F.", 
            "type": "Person"
          }, 
          {
            "familyName": "Pietracaprina", 
            "givenName": "Andrea", 
            "type": "Person"
          }, 
          {
            "familyName": "Pucci", 
            "givenName": "Geppino", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-68530-8_1", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-64848-2", 
            "978-3-540-68530-2"
          ], 
          "name": "Algorithms \u2014 ESA\u2019 98", 
          "type": "Book"
        }, 
        "name": "External Memory Algorithms", 
        "pagination": "1-25", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-68530-8_1"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "abdf419746ad7c7e031d56eb3c4e87b7f880b1daef9864d7e3e1ceee53c5090d"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1036080265"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-68530-8_1", 
          "https://app.dimensions.ai/details/publication/pub.1036080265"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:36", 
        "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/0000000346_0000000346/records_99833_00000002.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F3-540-68530-8_1"
      }
    ]
     

    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-68530-8_1'

    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-68530-8_1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-68530-8_1'

    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-68530-8_1'


     

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

    259 TRIPLES      23 PREDICATES      79 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-68530-8_1 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N6ceea652322e43c98e7029ce8cf8bc8d
    4 schema:citation sg:pub.10.1007/3-540-57155-8_238
    5 sg:pub.10.1007/3-540-60220-8_74
    6 sg:pub.10.1007/3-540-60220-8_75
    7 sg:pub.10.1007/3-540-60220-8_78
    8 sg:pub.10.1007/3-540-62592-5_75
    9 sg:pub.10.1007/3-540-63165-8_215
    10 sg:pub.10.1007/3-540-63818-0_6
    11 sg:pub.10.1007/978-1-4684-2001-2_10
    12 sg:pub.10.1007/bf00288683
    13 sg:pub.10.1007/bf01185207
    14 sg:pub.10.1007/bf01185208
    15 sg:pub.10.1007/bf01185210
    16 sg:pub.10.1007/bf01530929
    17 sg:pub.10.1007/bf01940646
    18 sg:pub.10.1007/bf01941686
    19 sg:pub.10.1007/bf02187740
    20 sg:pub.10.1007/bfb0015411
    21 sg:pub.10.1007/bfb0020785
    22 sg:pub.10.1007/s007780050028
    23 sg:pub.10.1007/s007780050042
    24 https://doi.org/10.1016/0022-0000(89)90034-2
    25 https://doi.org/10.1016/0022-0000(93)90043-v
    26 https://doi.org/10.1016/s0019-9958(84)80015-7
    27 https://doi.org/10.1016/s0167-8191(97)00015-x
    28 https://doi.org/10.1080/10637199608915543
    29 https://doi.org/10.1109/12.83622
    30 https://doi.org/10.1109/2.268881
    31 https://doi.org/10.1109/69.599929
    32 https://doi.org/10.1109/icde.1989.47268
    33 https://doi.org/10.1109/pdis.1991.183115
    34 https://doi.org/10.1109/sfcs.1993.366816
    35 https://doi.org/10.1109/sfcs.1993.366817
    36 https://doi.org/10.1109/sfcs.1996.548476
    37 https://doi.org/10.1109/sfcs.1996.548515
    38 https://doi.org/10.1109/spdp.1996.570330
    39 https://doi.org/10.1109/tc.1981.1675790
    40 https://doi.org/10.1109/tc.1985.5009385
    41 https://doi.org/10.1137/0215021
    42 https://doi.org/10.1145/165231.165247
    43 https://doi.org/10.1145/170088.170403
    44 https://doi.org/10.1145/176979.176981
    45 https://doi.org/10.1145/210332.210343
    46 https://doi.org/10.1145/225058.225287
    47 https://doi.org/10.1145/236017.236029
    48 https://doi.org/10.1145/237814.237864
    49 https://doi.org/10.1145/258492.258503
    50 https://doi.org/10.1145/263661.263688
    51 https://doi.org/10.1145/275487.275501
    52 https://doi.org/10.1145/275487.275506
    53 https://doi.org/10.1145/277851.277906
    54 https://doi.org/10.1145/48529.48535
    55 https://doi.org/10.1145/7921.11325
    56 https://doi.org/10.1145/93597.98741
    57 schema:datePublished 2002-03-15
    58 schema:datePublishedReg 2002-03-15
    59 schema:description Data sets in large applications are often too massive to fit completely inside the computer’s internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. In this tutorial, we survey the state of the art in the design and analysis of external memory algorithms (also known as EM algorithms or out-of-core algorithms or I/O algorithms). External memory algorithms are often designed using the parallel disk model (PDM). The three machine-independent measures of an algorithm’s performance in PDM are the number of I/O operations performed, the CPU time, and the amount of disk space used. PDM allows for multiple disks (or disk arrays) and parallel CPUs, and it can be generalized to handle cache hierarchies, hierarchical memory, and tertiary storage. We discuss a variety of problems and show how to solve them efficiently in external memory. Programming tools and environments are available for simplifying the programming task. Experiments on some newly developed algorithms for spatial databases incorporating these paradigms, implemented using TPIE (Transparent Parallel I/O programming Environment), show significant speedups over popular methods.
    60 schema:editor N3dfc55a71f9044f3ad975b720592f0a2
    61 schema:genre chapter
    62 schema:inLanguage en
    63 schema:isAccessibleForFree false
    64 schema:isPartOf N6841db72a8f44899bc27cbc05ce6f8fb
    65 schema:name External Memory Algorithms
    66 schema:pagination 1-25
    67 schema:productId N2a74b40c890d4704a09de60be77053c6
    68 N3115c940e29b4135830763482af2ca64
    69 Na65b6572685d48f9ae221470188ca4c1
    70 schema:publisher N3fd3b4655f8f4634accd909f50472390
    71 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036080265
    72 https://doi.org/10.1007/3-540-68530-8_1
    73 schema:sdDatePublished 2019-04-16T05:36
    74 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    75 schema:sdPublisher N09ac365dccef427096d9b92c78c44a73
    76 schema:url https://link.springer.com/10.1007%2F3-540-68530-8_1
    77 sgo:license sg:explorer/license/
    78 sgo:sdDataset chapters
    79 rdf:type schema:Chapter
    80 N09ac365dccef427096d9b92c78c44a73 schema:name Springer Nature - SN SciGraph project
    81 rdf:type schema:Organization
    82 N1d3fa0a0a2564fd7b0bb592bf96e95cf rdf:first N48577f73493144a6aea8e3202c8811e6
    83 rdf:rest rdf:nil
    84 N2a74b40c890d4704a09de60be77053c6 schema:name doi
    85 schema:value 10.1007/3-540-68530-8_1
    86 rdf:type schema:PropertyValue
    87 N3115c940e29b4135830763482af2ca64 schema:name dimensions_id
    88 schema:value pub.1036080265
    89 rdf:type schema:PropertyValue
    90 N3954f99496cc486584344686552edbe8 rdf:first N8b2f366c879d4ced8ec95e0d19bbcd36
    91 rdf:rest N1d3fa0a0a2564fd7b0bb592bf96e95cf
    92 N3dfc55a71f9044f3ad975b720592f0a2 rdf:first Nd55a43cdeaef49bcb223c07eebc687c4
    93 rdf:rest Nbc6381969aa942bf8728c6d3f68f1d87
    94 N3fd3b4655f8f4634accd909f50472390 schema:location Berlin, Heidelberg
    95 schema:name Springer Berlin Heidelberg
    96 rdf:type schema:Organisation
    97 N48577f73493144a6aea8e3202c8811e6 schema:familyName Pucci
    98 schema:givenName Geppino
    99 rdf:type schema:Person
    100 N6841db72a8f44899bc27cbc05ce6f8fb schema:isbn 978-3-540-64848-2
    101 978-3-540-68530-2
    102 schema:name Algorithms — ESA’ 98
    103 rdf:type schema:Book
    104 N6ceea652322e43c98e7029ce8cf8bc8d rdf:first sg:person.0613677314.28
    105 rdf:rest rdf:nil
    106 N8b2f366c879d4ced8ec95e0d19bbcd36 schema:familyName Pietracaprina
    107 schema:givenName Andrea
    108 rdf:type schema:Person
    109 Na2f6d6962cbb42758a8f133711c15d7a schema:familyName Italiano
    110 schema:givenName Giuseppe F.
    111 rdf:type schema:Person
    112 Na65b6572685d48f9ae221470188ca4c1 schema:name readcube_id
    113 schema:value abdf419746ad7c7e031d56eb3c4e87b7f880b1daef9864d7e3e1ceee53c5090d
    114 rdf:type schema:PropertyValue
    115 Nbc6381969aa942bf8728c6d3f68f1d87 rdf:first Na2f6d6962cbb42758a8f133711c15d7a
    116 rdf:rest N3954f99496cc486584344686552edbe8
    117 Nd55a43cdeaef49bcb223c07eebc687c4 schema:familyName Bilardi
    118 schema:givenName Gianfranco
    119 rdf:type schema:Person
    120 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    121 schema:name Information and Computing Sciences
    122 rdf:type schema:DefinedTerm
    123 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    124 schema:name Computation Theory and Mathematics
    125 rdf:type schema:DefinedTerm
    126 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
    127 schema:familyName Vitter
    128 schema:givenName Jeffrey Scott
    129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
    130 rdf:type schema:Person
    131 sg:pub.10.1007/3-540-57155-8_238 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031880279
    132 https://doi.org/10.1007/3-540-57155-8_238
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/3-540-60220-8_74 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019870666
    135 https://doi.org/10.1007/3-540-60220-8_74
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/3-540-60220-8_75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051465486
    138 https://doi.org/10.1007/3-540-60220-8_75
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/3-540-60220-8_78 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051329312
    141 https://doi.org/10.1007/3-540-60220-8_78
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/3-540-62592-5_75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007327628
    144 https://doi.org/10.1007/3-540-62592-5_75
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/3-540-63165-8_215 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026027828
    147 https://doi.org/10.1007/3-540-63165-8_215
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/3-540-63818-0_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020480392
    150 https://doi.org/10.1007/3-540-63818-0_6
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1007/978-1-4684-2001-2_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040405414
    153 https://doi.org/10.1007/978-1-4684-2001-2_10
    154 rdf:type schema:CreativeWork
    155 sg:pub.10.1007/bf00288683 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032694395
    156 https://doi.org/10.1007/bf00288683
    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/bf01185208 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006484027
    162 https://doi.org/10.1007/bf01185208
    163 rdf:type schema:CreativeWork
    164 sg:pub.10.1007/bf01185210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022046505
    165 https://doi.org/10.1007/bf01185210
    166 rdf:type schema:CreativeWork
    167 sg:pub.10.1007/bf01530929 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031507992
    168 https://doi.org/10.1007/bf01530929
    169 rdf:type schema:CreativeWork
    170 sg:pub.10.1007/bf01940646 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016252575
    171 https://doi.org/10.1007/bf01940646
    172 rdf:type schema:CreativeWork
    173 sg:pub.10.1007/bf01941686 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022526168
    174 https://doi.org/10.1007/bf01941686
    175 rdf:type schema:CreativeWork
    176 sg:pub.10.1007/bf02187740 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041585569
    177 https://doi.org/10.1007/bf02187740
    178 rdf:type schema:CreativeWork
    179 sg:pub.10.1007/bfb0015411 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029881376
    180 https://doi.org/10.1007/bfb0015411
    181 rdf:type schema:CreativeWork
    182 sg:pub.10.1007/bfb0020785 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006333313
    183 https://doi.org/10.1007/bfb0020785
    184 rdf:type schema:CreativeWork
    185 sg:pub.10.1007/s007780050028 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017349674
    186 https://doi.org/10.1007/s007780050028
    187 rdf:type schema:CreativeWork
    188 sg:pub.10.1007/s007780050042 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020058837
    189 https://doi.org/10.1007/s007780050042
    190 rdf:type schema:CreativeWork
    191 https://doi.org/10.1016/0022-0000(89)90034-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018960222
    192 rdf:type schema:CreativeWork
    193 https://doi.org/10.1016/0022-0000(93)90043-v schema:sameAs https://app.dimensions.ai/details/publication/pub.1036852105
    194 rdf:type schema:CreativeWork
    195 https://doi.org/10.1016/s0019-9958(84)80015-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016709409
    196 rdf:type schema:CreativeWork
    197 https://doi.org/10.1016/s0167-8191(97)00015-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1023784729
    198 rdf:type schema:CreativeWork
    199 https://doi.org/10.1080/10637199608915543 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031164865
    200 rdf:type schema:CreativeWork
    201 https://doi.org/10.1109/12.83622 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061089095
    202 rdf:type schema:CreativeWork
    203 https://doi.org/10.1109/2.268881 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061105270
    204 rdf:type schema:CreativeWork
    205 https://doi.org/10.1109/69.599929 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061213593
    206 rdf:type schema:CreativeWork
    207 https://doi.org/10.1109/icde.1989.47268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086180375
    208 rdf:type schema:CreativeWork
    209 https://doi.org/10.1109/pdis.1991.183115 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086296319
    210 rdf:type schema:CreativeWork
    211 https://doi.org/10.1109/sfcs.1993.366816 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086354005
    212 rdf:type schema:CreativeWork
    213 https://doi.org/10.1109/sfcs.1993.366817 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086297219
    214 rdf:type schema:CreativeWork
    215 https://doi.org/10.1109/sfcs.1996.548476 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094987476
    216 rdf:type schema:CreativeWork
    217 https://doi.org/10.1109/sfcs.1996.548515 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094835330
    218 rdf:type schema:CreativeWork
    219 https://doi.org/10.1109/spdp.1996.570330 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093315978
    220 rdf:type schema:CreativeWork
    221 https://doi.org/10.1109/tc.1981.1675790 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061532562
    222 rdf:type schema:CreativeWork
    223 https://doi.org/10.1109/tc.1985.5009385 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061533266
    224 rdf:type schema:CreativeWork
    225 https://doi.org/10.1137/0215021 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841883
    226 rdf:type schema:CreativeWork
    227 https://doi.org/10.1145/165231.165247 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028273198
    228 rdf:type schema:CreativeWork
    229 https://doi.org/10.1145/170088.170403 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003526327
    230 rdf:type schema:CreativeWork
    231 https://doi.org/10.1145/176979.176981 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013288182
    232 rdf:type schema:CreativeWork
    233 https://doi.org/10.1145/210332.210343 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014625708
    234 rdf:type schema:CreativeWork
    235 https://doi.org/10.1145/225058.225287 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034584204
    236 rdf:type schema:CreativeWork
    237 https://doi.org/10.1145/236017.236029 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030282918
    238 rdf:type schema:CreativeWork
    239 https://doi.org/10.1145/237814.237864 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011126443
    240 rdf:type schema:CreativeWork
    241 https://doi.org/10.1145/258492.258503 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039074543
    242 rdf:type schema:CreativeWork
    243 https://doi.org/10.1145/263661.263688 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027864880
    244 rdf:type schema:CreativeWork
    245 https://doi.org/10.1145/275487.275501 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047551077
    246 rdf:type schema:CreativeWork
    247 https://doi.org/10.1145/275487.275506 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020791293
    248 rdf:type schema:CreativeWork
    249 https://doi.org/10.1145/277851.277906 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040238186
    250 rdf:type schema:CreativeWork
    251 https://doi.org/10.1145/48529.48535 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014013712
    252 rdf:type schema:CreativeWork
    253 https://doi.org/10.1145/7921.11325 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000895227
    254 rdf:type schema:CreativeWork
    255 https://doi.org/10.1145/93597.98741 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025736774
    256 rdf:type schema:CreativeWork
    257 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
    258 schema:name Center for Geometric Computing, Department of Computer Science, Duke University, 27708-0129, Durham, NC, USA
    259 rdf:type schema:Organization
     




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


    ...