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 Nc9542ab7edad40a0ad9268c6f1ec1b6c
    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 Na765e27b66394398acb8653d3819c0b5
    61 schema:genre chapter
    62 schema:inLanguage en
    63 schema:isAccessibleForFree false
    64 schema:isPartOf N4a3a7f6d2c84488294fd94faae024963
    65 schema:name External Memory Algorithms
    66 schema:pagination 1-25
    67 schema:productId N015cfa0e11ed41aab0e6ffd864f29f11
    68 N3a42f98615754ce789c41b0b5793d225
    69 N5d84dd4b09784958860f7d953ab7353a
    70 schema:publisher Nb1d5f7ce02c6492f96f1583aa9802d21
    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 N4187c7240fb34a788cca62018eadaf84
    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 N015cfa0e11ed41aab0e6ffd864f29f11 schema:name doi
    81 schema:value 10.1007/3-540-68530-8_1
    82 rdf:type schema:PropertyValue
    83 N0488b6980e9c40329342e0ffeb542836 rdf:first Nb20b4ddfac414710af2fe693ebc7e532
    84 rdf:rest N65ff6e9b696a42b081296fceba2c3eaa
    85 N3a42f98615754ce789c41b0b5793d225 schema:name readcube_id
    86 schema:value abdf419746ad7c7e031d56eb3c4e87b7f880b1daef9864d7e3e1ceee53c5090d
    87 rdf:type schema:PropertyValue
    88 N4187c7240fb34a788cca62018eadaf84 schema:name Springer Nature - SN SciGraph project
    89 rdf:type schema:Organization
    90 N4a3a7f6d2c84488294fd94faae024963 schema:isbn 978-3-540-64848-2
    91 978-3-540-68530-2
    92 schema:name Algorithms — ESA’ 98
    93 rdf:type schema:Book
    94 N557cc7e1d9ef4ec287ccf35e3ca40a92 schema:familyName Pietracaprina
    95 schema:givenName Andrea
    96 rdf:type schema:Person
    97 N5d84dd4b09784958860f7d953ab7353a schema:name dimensions_id
    98 schema:value pub.1036080265
    99 rdf:type schema:PropertyValue
    100 N62c03ceb47974f07820b4d2aa1f8975a rdf:first Nd81400634031422dadcf804c143fadd1
    101 rdf:rest rdf:nil
    102 N65ff6e9b696a42b081296fceba2c3eaa rdf:first N557cc7e1d9ef4ec287ccf35e3ca40a92
    103 rdf:rest N62c03ceb47974f07820b4d2aa1f8975a
    104 Na765e27b66394398acb8653d3819c0b5 rdf:first Nfee46e34fff543f5bd038cf944d09275
    105 rdf:rest N0488b6980e9c40329342e0ffeb542836
    106 Nb1d5f7ce02c6492f96f1583aa9802d21 schema:location Berlin, Heidelberg
    107 schema:name Springer Berlin Heidelberg
    108 rdf:type schema:Organisation
    109 Nb20b4ddfac414710af2fe693ebc7e532 schema:familyName Italiano
    110 schema:givenName Giuseppe F.
    111 rdf:type schema:Person
    112 Nc9542ab7edad40a0ad9268c6f1ec1b6c rdf:first sg:person.0613677314.28
    113 rdf:rest rdf:nil
    114 Nd81400634031422dadcf804c143fadd1 schema:familyName Pucci
    115 schema:givenName Geppino
    116 rdf:type schema:Person
    117 Nfee46e34fff543f5bd038cf944d09275 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)


    ...