Blocking for external graph searching View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1996-08

AUTHORS

M. H. Nodine, M. T. Goodrich, J. S. Vitter

ABSTRACT

In this paper we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy. We give matching upper and lower bounds for completed-ary trees andd-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking have a close to uniform number of neighbors around each vertex. We also show that, for the special case of grid graphs blocked with isothetic hypercubes, there is a provably better speed-up if even a small amount of redundancy is permitted. More... »

PAGES

181-214

References to SciGraph publications

  • 1990. Beyond Steiner's problem: A VLSI oriented generalization in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • 1991-06. The input/output complexity of transitive closure in ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE
  • 1978-09. Data encodings and their costs in ACTA INFORMATICA
  • 1978-12. Bounds on the costs of data encodings in MATHEMATICAL SYSTEMS THEORY
  • 1991. Bounds on the quality of approximate solutions to the group Steiner problem in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "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": "Motorola (United States)", 
              "id": "https://www.grid.ac/institutes/grid.467466.1", 
              "name": [
                "Motorola Inc., 5918 W. Courtyard Dr., Suite 200, 78746, Austin, TX, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Nodine", 
            "givenName": "M. H.", 
            "id": "sg:person.013623713611.95", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013623713611.95"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Johns Hopkins University", 
              "id": "https://www.grid.ac/institutes/grid.21107.35", 
              "name": [
                "Department of Computer Science, The Johns Hopkins University, 21218, Baltimore, MD, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Goodrich", 
            "givenName": "M. T.", 
            "id": "sg:person.010415570120.83", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010415570120.83"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Duke University", 
              "id": "https://www.grid.ac/institutes/grid.26009.3d", 
              "name": [
                "Department of Computer Science, Duke University, 27708-0129, Durham, NC, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Vitter", 
            "givenName": "J. S.", 
            "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/3-540-52292-1_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006840501", 
              "https://doi.org/10.1007/3-540-52292-1_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01776564", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007329874", 
              "https://doi.org/10.1007/bf01776564"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01776564", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007329874", 
              "https://doi.org/10.1007/bf01776564"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-53832-1_36", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010603713", 
              "https://doi.org/10.1007/3-540-53832-1_36"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321978.321990", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010900268"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00288886", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030458850", 
              "https://doi.org/10.1007/bf00288886"
            ], 
            "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.1145/359361.359447", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031690441"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/103418.103422", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033563163"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/322154.322160", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033824984"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.1982.1676109", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061532812"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0204038", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841278"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0604055", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062848840"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1988.21966", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086228996"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1996-08", 
        "datePublishedReg": "1996-08-01", 
        "description": "In this paper we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy. We give matching upper and lower bounds for completed-ary trees andd-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking have a close to uniform number of neighbors around each vertex. We also show that, for the special case of grid graphs blocked with isothetic hypercubes, there is a provably better speed-up if even a small amount of redundancy is permitted.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf01940646", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1047644", 
            "issn": [
              "0178-4617", 
              "1432-0541"
            ], 
            "name": "Algorithmica", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "16"
          }
        ], 
        "name": "Blocking for external graph searching", 
        "pagination": "181-214", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "4d7095da70d7145061512f3399d7780488997757105b1ab3ef89c223f299a779"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01940646"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1016252575"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01940646", 
          "https://app.dimensions.ai/details/publication/pub.1016252575"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T11:27", 
        "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/0000000356_0000000356/records_57902_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF01940646"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    125 TRIPLES      21 PREDICATES      40 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01940646 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Nd1dd2fd142cb4016b91aa3d14a8336c4
    4 schema:citation sg:pub.10.1007/3-540-52292-1_14
    5 sg:pub.10.1007/3-540-53832-1_36
    6 sg:pub.10.1007/bf00288886
    7 sg:pub.10.1007/bf01530929
    8 sg:pub.10.1007/bf01776564
    9 https://doi.org/10.1109/sfcs.1988.21966
    10 https://doi.org/10.1109/tc.1982.1676109
    11 https://doi.org/10.1137/0204038
    12 https://doi.org/10.1137/0604055
    13 https://doi.org/10.1145/103418.103422
    14 https://doi.org/10.1145/321978.321990
    15 https://doi.org/10.1145/322154.322160
    16 https://doi.org/10.1145/359361.359447
    17 schema:datePublished 1996-08
    18 schema:datePublishedReg 1996-08-01
    19 schema:description In this paper we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy. We give matching upper and lower bounds for completed-ary trees andd-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking have a close to uniform number of neighbors around each vertex. We also show that, for the special case of grid graphs blocked with isothetic hypercubes, there is a provably better speed-up if even a small amount of redundancy is permitted.
    20 schema:genre research_article
    21 schema:inLanguage en
    22 schema:isAccessibleForFree true
    23 schema:isPartOf Nb1060c74768a444ba513b2f022564637
    24 Ne773d24f80e64d918698dbad3d74767b
    25 sg:journal.1047644
    26 schema:name Blocking for external graph searching
    27 schema:pagination 181-214
    28 schema:productId N8f6dd1ce570c4de8917795960408c7b3
    29 Na9880502ab0a43f69a4e0f939033531f
    30 Nd83850f3828e466db74c52c39c4c8dba
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016252575
    32 https://doi.org/10.1007/bf01940646
    33 schema:sdDatePublished 2019-04-11T11:27
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher Nb1d36528ba47402cba4d117a8f53f499
    36 schema:url http://link.springer.com/10.1007/BF01940646
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset articles
    39 rdf:type schema:ScholarlyArticle
    40 N8f6dd1ce570c4de8917795960408c7b3 schema:name dimensions_id
    41 schema:value pub.1016252575
    42 rdf:type schema:PropertyValue
    43 N9b9dd903df2d4aaf88097b9c8f838196 rdf:first sg:person.010415570120.83
    44 rdf:rest Nfa8536e7c71b487d99e6500a28cef421
    45 Na9880502ab0a43f69a4e0f939033531f schema:name doi
    46 schema:value 10.1007/bf01940646
    47 rdf:type schema:PropertyValue
    48 Nb1060c74768a444ba513b2f022564637 schema:volumeNumber 16
    49 rdf:type schema:PublicationVolume
    50 Nb1d36528ba47402cba4d117a8f53f499 schema:name Springer Nature - SN SciGraph project
    51 rdf:type schema:Organization
    52 Nd1dd2fd142cb4016b91aa3d14a8336c4 rdf:first sg:person.013623713611.95
    53 rdf:rest N9b9dd903df2d4aaf88097b9c8f838196
    54 Nd83850f3828e466db74c52c39c4c8dba schema:name readcube_id
    55 schema:value 4d7095da70d7145061512f3399d7780488997757105b1ab3ef89c223f299a779
    56 rdf:type schema:PropertyValue
    57 Ne773d24f80e64d918698dbad3d74767b schema:issueNumber 2
    58 rdf:type schema:PublicationIssue
    59 Nfa8536e7c71b487d99e6500a28cef421 rdf:first sg:person.0613677314.28
    60 rdf:rest rdf:nil
    61 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Information and Computing Sciences
    63 rdf:type schema:DefinedTerm
    64 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Artificial Intelligence and Image Processing
    66 rdf:type schema:DefinedTerm
    67 sg:journal.1047644 schema:issn 0178-4617
    68 1432-0541
    69 schema:name Algorithmica
    70 rdf:type schema:Periodical
    71 sg:person.010415570120.83 schema:affiliation https://www.grid.ac/institutes/grid.21107.35
    72 schema:familyName Goodrich
    73 schema:givenName M. T.
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010415570120.83
    75 rdf:type schema:Person
    76 sg:person.013623713611.95 schema:affiliation https://www.grid.ac/institutes/grid.467466.1
    77 schema:familyName Nodine
    78 schema:givenName M. H.
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013623713611.95
    80 rdf:type schema:Person
    81 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
    82 schema:familyName Vitter
    83 schema:givenName J. S.
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
    85 rdf:type schema:Person
    86 sg:pub.10.1007/3-540-52292-1_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006840501
    87 https://doi.org/10.1007/3-540-52292-1_14
    88 rdf:type schema:CreativeWork
    89 sg:pub.10.1007/3-540-53832-1_36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010603713
    90 https://doi.org/10.1007/3-540-53832-1_36
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1007/bf00288886 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030458850
    93 https://doi.org/10.1007/bf00288886
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/bf01530929 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031507992
    96 https://doi.org/10.1007/bf01530929
    97 rdf:type schema:CreativeWork
    98 sg:pub.10.1007/bf01776564 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007329874
    99 https://doi.org/10.1007/bf01776564
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1109/sfcs.1988.21966 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086228996
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1109/tc.1982.1676109 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061532812
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1137/0204038 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841278
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1137/0604055 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062848840
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1145/103418.103422 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033563163
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1145/321978.321990 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010900268
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1145/322154.322160 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033824984
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1145/359361.359447 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031690441
    116 rdf:type schema:CreativeWork
    117 https://www.grid.ac/institutes/grid.21107.35 schema:alternateName Johns Hopkins University
    118 schema:name Department of Computer Science, The Johns Hopkins University, 21218, Baltimore, MD, USA
    119 rdf:type schema:Organization
    120 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
    121 schema:name Department of Computer Science, Duke University, 27708-0129, Durham, NC, USA
    122 rdf:type schema:Organization
    123 https://www.grid.ac/institutes/grid.467466.1 schema:alternateName Motorola (United States)
    124 schema:name Motorola Inc., 5918 W. Courtyard Dr., Suite 200, 78746, Austin, TX, USA
    125 rdf:type schema:Organization
     




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


    ...