External Memory Algorithms View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002

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 paper we survey the state of the art in the design and analysis of external memory (or EM) algorithms, where the goal is to exploit locality in order to reduce the I/O costs. For sorting and related problems like permuting and fast Fourier transform, the key paradigms include distribution and merging. The paradigm of disk striping offers an elegant way to use multiple disks in parallel. For sorting, however, disk striping can be nonoptimal with respect to I/O, so to gain further improvements we discuss distribution and merging techniques for using the disks independently. We consider EM paradigms for computations involving matrixes, geometric data, and graphs, and we look at problems caused by dynamic memory allocation. We report on some experiments in the domain of spatial databases using the TPIE system (Transparent Parallel I/O programming Environment). The newly developed EM algorithms and data structures that incorporate the paradigms we discuss in this chapter are significantly faster than methods currently used in practice. More... »

PAGES

359-416

References to SciGraph publications

  • 1994-09. Coding techniques for handling failures in large disk arrays in ALGORITHMICA
  • 1995. External-memory algorithms for processing line segments in geographic information systems in ALGORITHMS — ESA '95
  • 1996-08. Blocking for external graph searching in ALGORITHMICA
  • 1994-09. Algorithms for parallel memory, II: Hierarchical multilevel memories in ALGORITHMICA
  • 1994-09. Algorithms for parallel memory, I: Two-level memories in ALGORITHMICA
  • 1994-09. The uniform memory hierarchy model of computation in ALGORITHMICA
  • 1989-10. Applications of random sampling in computational geometry, II in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1991-06. The input/output complexity of transitive closure in ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE
  • 1996-06. Multidimensional array I/O in Panda 1.0 in THE JOURNAL OF SUPERCOMPUTING
  • 2002-01-18. Online Data Structures in External Memory in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1995. The buffer tree: A new technique for optimal I/O-algorithms in ALGORITHMS AND DATA STRUCTURES
  • 1996. An Introduction to Parallel I/O Models and Algorithms in INPUT/OUTPUT IN PARALLEL AND DISTRIBUTED COMPUTER SYSTEMS
  • 1997. BSP-like external-memory computation in ALGORITHMS AND COMPLEXITY
  • 1996-02. Optimal cooperative search in fractional cascaded data structures in ALGORITHMICA
  • Book

    TITLE

    Handbook of Massive Data Sets

    ISBN

    978-1-4613-4882-5
    978-1-4615-0005-6

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-1-4615-0005-6_10

    DOI

    http://dx.doi.org/10.1007/978-1-4615-0005-6_10

    DIMENSIONS

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


    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, Durham, NC\u00a027708-0129, 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": "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": "sg:pub.10.1007/bf01185206", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008924223", 
              "https://doi.org/10.1007/bf01185206"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01185206", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008924223", 
              "https://doi.org/10.1007/bf01185206"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/244804.244807", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012309022"
            ], 
            "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/978-1-4613-1401-1_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015154632", 
              "https://doi.org/10.1007/978-1-4613-1401-1_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4613-1401-1_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015154632", 
              "https://doi.org/10.1007/978-1-4613-1401-1_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00130709", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015964934", 
              "https://doi.org/10.1007/bf00130709"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00130709", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015964934", 
              "https://doi.org/10.1007/bf00130709"
            ], 
            "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": "sg:pub.10.1007/3-540-60313-1_151", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017873255", 
              "https://doi.org/10.1007/3-540-60313-1_151"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/342009.335449", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018599688"
            ], 
            "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": "https://doi.org/10.1145/233557.233558", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019151050"
            ], 
            "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/3-540-48523-6_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020471390", 
              "https://doi.org/10.1007/3-540-48523-6_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48523-6_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020471390", 
              "https://doi.org/10.1007/3-540-48523-6_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0925-7721(97)00020-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021087721"
            ], 
            "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.1006/jpdc.1993.1008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029035640"
            ], 
            "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.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": "https://doi.org/10.1006/jpdc.1996.0130", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036233290"
            ], 
            "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.1016/s0167-8191(97)00114-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039182730"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/384192.384193", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040182656"
            ], 
            "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/291006.291026", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045577533"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/170035.170051", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046445831"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/275487.275501", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047551077"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0167-8191(97)00013-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050077070"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/265910.265914", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053241906"
            ], 
            "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/12.83622", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061089095"
            ], 
            "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.1109/tc.1986.1676699", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061533356"
            ], 
            "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.1137/s0097539795283681", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062880024"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/773473.178260", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063173086"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1147/rd.443.0323", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063182508"
            ], 
            "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/mass.1995.528214", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095555025"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2002", 
        "datePublishedReg": "2002-01-01", 
        "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 paper we survey the state of the art in the design and analysis of external memory (or EM) algorithms, where the goal is to exploit locality in order to reduce the I/O costs. For sorting and related problems like permuting and fast Fourier transform, the key paradigms include distribution and merging. The paradigm of disk striping offers an elegant way to use multiple disks in parallel. For sorting, however, disk striping can be nonoptimal with respect to I/O, so to gain further improvements we discuss distribution and merging techniques for using the disks independently. We consider EM paradigms for computations involving matrixes, geometric data, and graphs, and we look at problems caused by dynamic memory allocation. We report on some experiments in the domain of spatial databases using the TPIE system (Transparent Parallel I/O programming Environment). The newly developed EM algorithms and data structures that incorporate the paradigms we discuss in this chapter are significantly faster than methods currently used in practice.", 
        "editor": [
          {
            "familyName": "Abello", 
            "givenName": "James", 
            "type": "Person"
          }, 
          {
            "familyName": "Pardalos", 
            "givenName": "Panos M.", 
            "type": "Person"
          }, 
          {
            "familyName": "Resende", 
            "givenName": "Mauricio G. C.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-1-4615-0005-6_10", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.3435989", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.3469763", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": {
          "isbn": [
            "978-1-4613-4882-5", 
            "978-1-4615-0005-6"
          ], 
          "name": "Handbook of Massive Data Sets", 
          "type": "Book"
        }, 
        "name": "External Memory Algorithms", 
        "pagination": "359-416", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-1-4615-0005-6_10"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "54590d0978ee94c12635d189f5579ed7dd43b5b4781777b739b94ce8a8cfe682"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1017702884"
            ]
          }
        ], 
        "publisher": {
          "location": "Boston, MA", 
          "name": "Springer US", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-1-4615-0005-6_10", 
          "https://app.dimensions.ai/details/publication/pub.1017702884"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T14:24", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8669_00000254.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-1-4615-0005-6_10"
      }
    ]
     

    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/978-1-4615-0005-6_10'

    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/978-1-4615-0005-6_10'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4615-0005-6_10'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4615-0005-6_10'


     

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

    231 TRIPLES      23 PREDICATES      73 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-1-4615-0005-6_10 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N1fdba8db809d49cbb6c4630b9d090cad
    4 schema:citation sg:pub.10.1007/3-540-48523-6_10
    5 sg:pub.10.1007/3-540-60220-8_74
    6 sg:pub.10.1007/3-540-60313-1_151
    7 sg:pub.10.1007/3-540-62592-5_75
    8 sg:pub.10.1007/978-1-4613-1401-1_2
    9 sg:pub.10.1007/bf00130709
    10 sg:pub.10.1007/bf01185206
    11 sg:pub.10.1007/bf01185207
    12 sg:pub.10.1007/bf01185208
    13 sg:pub.10.1007/bf01185210
    14 sg:pub.10.1007/bf01530929
    15 sg:pub.10.1007/bf01940646
    16 sg:pub.10.1007/bf01941686
    17 sg:pub.10.1007/bf02187740
    18 https://doi.org/10.1006/jcss.1996.0043
    19 https://doi.org/10.1006/jpdc.1993.1008
    20 https://doi.org/10.1006/jpdc.1996.0130
    21 https://doi.org/10.1016/0022-0000(89)90034-2
    22 https://doi.org/10.1016/0022-0000(93)90043-v
    23 https://doi.org/10.1016/s0167-8191(97)00013-6
    24 https://doi.org/10.1016/s0167-8191(97)00015-x
    25 https://doi.org/10.1016/s0167-8191(97)00114-2
    26 https://doi.org/10.1016/s0925-7721(97)00020-5
    27 https://doi.org/10.1080/10637199608915543
    28 https://doi.org/10.1109/12.83622
    29 https://doi.org/10.1109/mass.1995.528214
    30 https://doi.org/10.1109/pdis.1991.183115
    31 https://doi.org/10.1109/tc.1981.1675790
    32 https://doi.org/10.1109/tc.1985.5009385
    33 https://doi.org/10.1109/tc.1986.1676699
    34 https://doi.org/10.1137/0215021
    35 https://doi.org/10.1137/s0097539795283681
    36 https://doi.org/10.1145/170035.170051
    37 https://doi.org/10.1145/176979.176981
    38 https://doi.org/10.1145/210332.210343
    39 https://doi.org/10.1145/233557.233558
    40 https://doi.org/10.1145/242223.242300
    41 https://doi.org/10.1145/244804.244807
    42 https://doi.org/10.1145/265910.265914
    43 https://doi.org/10.1145/275487.275501
    44 https://doi.org/10.1145/291006.291026
    45 https://doi.org/10.1145/342009.335449
    46 https://doi.org/10.1145/384192.384193
    47 https://doi.org/10.1145/48529.48535
    48 https://doi.org/10.1145/773473.178260
    49 https://doi.org/10.1147/rd.443.0323
    50 schema:datePublished 2002
    51 schema:datePublishedReg 2002-01-01
    52 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 paper we survey the state of the art in the design and analysis of external memory (or EM) algorithms, where the goal is to exploit locality in order to reduce the I/O costs. For sorting and related problems like permuting and fast Fourier transform, the key paradigms include distribution and merging. The paradigm of disk striping offers an elegant way to use multiple disks in parallel. For sorting, however, disk striping can be nonoptimal with respect to I/O, so to gain further improvements we discuss distribution and merging techniques for using the disks independently. We consider EM paradigms for computations involving matrixes, geometric data, and graphs, and we look at problems caused by dynamic memory allocation. We report on some experiments in the domain of spatial databases using the TPIE system (Transparent Parallel I/O programming Environment). The newly developed EM algorithms and data structures that incorporate the paradigms we discuss in this chapter are significantly faster than methods currently used in practice.
    53 schema:editor N6485bbc5b5584ba58973b619aa907702
    54 schema:genre chapter
    55 schema:inLanguage en
    56 schema:isAccessibleForFree false
    57 schema:isPartOf N7464ca57c82f40ddbd5bb0f5a518c669
    58 schema:name External Memory Algorithms
    59 schema:pagination 359-416
    60 schema:productId N777dbdc71fda49459d74c6de63361018
    61 N7eae9f5f517842a1b58321ecc999d02d
    62 N8edb0604cf76403bb3d74ce774c55f7a
    63 schema:publisher Nb87a570af41f4fde96828f068f77ffe7
    64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017702884
    65 https://doi.org/10.1007/978-1-4615-0005-6_10
    66 schema:sdDatePublished 2019-04-15T14:24
    67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    68 schema:sdPublisher Nb4029334af0043da8f2484656a806503
    69 schema:url http://link.springer.com/10.1007/978-1-4615-0005-6_10
    70 sgo:license sg:explorer/license/
    71 sgo:sdDataset chapters
    72 rdf:type schema:Chapter
    73 N1fdba8db809d49cbb6c4630b9d090cad rdf:first sg:person.0613677314.28
    74 rdf:rest rdf:nil
    75 N5bc076d3d4084b869b5115432664b2db schema:familyName Resende
    76 schema:givenName Mauricio G. C.
    77 rdf:type schema:Person
    78 N6485bbc5b5584ba58973b619aa907702 rdf:first Nac99da0733164b08b105e5ed523ff05b
    79 rdf:rest Nb89b9c57f0604e0fa3952ee0439701c6
    80 N7464ca57c82f40ddbd5bb0f5a518c669 schema:isbn 978-1-4613-4882-5
    81 978-1-4615-0005-6
    82 schema:name Handbook of Massive Data Sets
    83 rdf:type schema:Book
    84 N777dbdc71fda49459d74c6de63361018 schema:name doi
    85 schema:value 10.1007/978-1-4615-0005-6_10
    86 rdf:type schema:PropertyValue
    87 N7eae9f5f517842a1b58321ecc999d02d schema:name readcube_id
    88 schema:value 54590d0978ee94c12635d189f5579ed7dd43b5b4781777b739b94ce8a8cfe682
    89 rdf:type schema:PropertyValue
    90 N8edb0604cf76403bb3d74ce774c55f7a schema:name dimensions_id
    91 schema:value pub.1017702884
    92 rdf:type schema:PropertyValue
    93 Nac99da0733164b08b105e5ed523ff05b schema:familyName Abello
    94 schema:givenName James
    95 rdf:type schema:Person
    96 Nb4029334af0043da8f2484656a806503 schema:name Springer Nature - SN SciGraph project
    97 rdf:type schema:Organization
    98 Nb87a570af41f4fde96828f068f77ffe7 schema:location Boston, MA
    99 schema:name Springer US
    100 rdf:type schema:Organisation
    101 Nb89b9c57f0604e0fa3952ee0439701c6 rdf:first Nd6dd22f6cd554b50bc8c04bfa312c46c
    102 rdf:rest Ncbd16d278e124964aba76155249a3a97
    103 Ncbd16d278e124964aba76155249a3a97 rdf:first N5bc076d3d4084b869b5115432664b2db
    104 rdf:rest rdf:nil
    105 Nd6dd22f6cd554b50bc8c04bfa312c46c schema:familyName Pardalos
    106 schema:givenName Panos M.
    107 rdf:type schema:Person
    108 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    109 schema:name Information and Computing Sciences
    110 rdf:type schema:DefinedTerm
    111 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    112 schema:name Computation Theory and Mathematics
    113 rdf:type schema:DefinedTerm
    114 sg:grant.3435989 http://pending.schema.org/fundedItem sg:pub.10.1007/978-1-4615-0005-6_10
    115 rdf:type schema:MonetaryGrant
    116 sg:grant.3469763 http://pending.schema.org/fundedItem sg:pub.10.1007/978-1-4615-0005-6_10
    117 rdf:type schema:MonetaryGrant
    118 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
    119 schema:familyName Vitter
    120 schema:givenName Jeffrey Scott
    121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
    122 rdf:type schema:Person
    123 sg:pub.10.1007/3-540-48523-6_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020471390
    124 https://doi.org/10.1007/3-540-48523-6_10
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/3-540-60220-8_74 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019870666
    127 https://doi.org/10.1007/3-540-60220-8_74
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/3-540-60313-1_151 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017873255
    130 https://doi.org/10.1007/3-540-60313-1_151
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/3-540-62592-5_75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007327628
    133 https://doi.org/10.1007/3-540-62592-5_75
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/978-1-4613-1401-1_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015154632
    136 https://doi.org/10.1007/978-1-4613-1401-1_2
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/bf00130709 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015964934
    139 https://doi.org/10.1007/bf00130709
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/bf01185206 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008924223
    142 https://doi.org/10.1007/bf01185206
    143 rdf:type schema:CreativeWork
    144 sg:pub.10.1007/bf01185207 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045195394
    145 https://doi.org/10.1007/bf01185207
    146 rdf:type schema:CreativeWork
    147 sg:pub.10.1007/bf01185208 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006484027
    148 https://doi.org/10.1007/bf01185208
    149 rdf:type schema:CreativeWork
    150 sg:pub.10.1007/bf01185210 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022046505
    151 https://doi.org/10.1007/bf01185210
    152 rdf:type schema:CreativeWork
    153 sg:pub.10.1007/bf01530929 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031507992
    154 https://doi.org/10.1007/bf01530929
    155 rdf:type schema:CreativeWork
    156 sg:pub.10.1007/bf01940646 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016252575
    157 https://doi.org/10.1007/bf01940646
    158 rdf:type schema:CreativeWork
    159 sg:pub.10.1007/bf01941686 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022526168
    160 https://doi.org/10.1007/bf01941686
    161 rdf:type schema:CreativeWork
    162 sg:pub.10.1007/bf02187740 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041585569
    163 https://doi.org/10.1007/bf02187740
    164 rdf:type schema:CreativeWork
    165 https://doi.org/10.1006/jcss.1996.0043 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053243165
    166 rdf:type schema:CreativeWork
    167 https://doi.org/10.1006/jpdc.1993.1008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029035640
    168 rdf:type schema:CreativeWork
    169 https://doi.org/10.1006/jpdc.1996.0130 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036233290
    170 rdf:type schema:CreativeWork
    171 https://doi.org/10.1016/0022-0000(89)90034-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018960222
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1016/0022-0000(93)90043-v schema:sameAs https://app.dimensions.ai/details/publication/pub.1036852105
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1016/s0167-8191(97)00013-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050077070
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1016/s0167-8191(97)00015-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1023784729
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1016/s0167-8191(97)00114-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039182730
    180 rdf:type schema:CreativeWork
    181 https://doi.org/10.1016/s0925-7721(97)00020-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021087721
    182 rdf:type schema:CreativeWork
    183 https://doi.org/10.1080/10637199608915543 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031164865
    184 rdf:type schema:CreativeWork
    185 https://doi.org/10.1109/12.83622 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061089095
    186 rdf:type schema:CreativeWork
    187 https://doi.org/10.1109/mass.1995.528214 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095555025
    188 rdf:type schema:CreativeWork
    189 https://doi.org/10.1109/pdis.1991.183115 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086296319
    190 rdf:type schema:CreativeWork
    191 https://doi.org/10.1109/tc.1981.1675790 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061532562
    192 rdf:type schema:CreativeWork
    193 https://doi.org/10.1109/tc.1985.5009385 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061533266
    194 rdf:type schema:CreativeWork
    195 https://doi.org/10.1109/tc.1986.1676699 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061533356
    196 rdf:type schema:CreativeWork
    197 https://doi.org/10.1137/0215021 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841883
    198 rdf:type schema:CreativeWork
    199 https://doi.org/10.1137/s0097539795283681 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880024
    200 rdf:type schema:CreativeWork
    201 https://doi.org/10.1145/170035.170051 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046445831
    202 rdf:type schema:CreativeWork
    203 https://doi.org/10.1145/176979.176981 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013288182
    204 rdf:type schema:CreativeWork
    205 https://doi.org/10.1145/210332.210343 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014625708
    206 rdf:type schema:CreativeWork
    207 https://doi.org/10.1145/233557.233558 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019151050
    208 rdf:type schema:CreativeWork
    209 https://doi.org/10.1145/242223.242300 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030410788
    210 rdf:type schema:CreativeWork
    211 https://doi.org/10.1145/244804.244807 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012309022
    212 rdf:type schema:CreativeWork
    213 https://doi.org/10.1145/265910.265914 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053241906
    214 rdf:type schema:CreativeWork
    215 https://doi.org/10.1145/275487.275501 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047551077
    216 rdf:type schema:CreativeWork
    217 https://doi.org/10.1145/291006.291026 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045577533
    218 rdf:type schema:CreativeWork
    219 https://doi.org/10.1145/342009.335449 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018599688
    220 rdf:type schema:CreativeWork
    221 https://doi.org/10.1145/384192.384193 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040182656
    222 rdf:type schema:CreativeWork
    223 https://doi.org/10.1145/48529.48535 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014013712
    224 rdf:type schema:CreativeWork
    225 https://doi.org/10.1145/773473.178260 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063173086
    226 rdf:type schema:CreativeWork
    227 https://doi.org/10.1147/rd.443.0323 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063182508
    228 rdf:type schema:CreativeWork
    229 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
    230 schema:name Department of Computer Science, Duke University, Durham, NC 27708-0129, USA
    231 rdf:type schema:Organization
     




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


    ...