The input/output complexity of transitive closure View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1991-06

AUTHORS

Jeffrey D. Ullman, Mihalis Yannakakis

ABSTRACT

Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holdings “values” is available, and thats lies betweenn, the number of nodes of the graph, ande, the number of arcs. The cost measure we use for algorithms is theI/O complexity of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa. In the dense case, wheree is close ton2, we show that I/O equal toO(n3/√s) is sufficient to compute the transitive closure of ann-node graph, using main memory of sizes. Moreover, it is necessary for any algorithm that is “standard,” in a sense to be defined precisely in the paper. Roughly, “standard” means that paths are constructed only by concatenating arcs and previously discovered paths. For the sparse case, we show that I/O equal toO(n2√e/s) is sufficient, although the algorithm we propose meets our definition of “standard” only if the underlying graph is acyclic. We also show thatΩ(n2√e/s) is necessary for any standard algorithm in the sparse case. That settles the I/O complexity of the sparse/acyclic case, for standard algorithms. It is unknown whether this complexity can be achieved in the sparse, cyclic case, by a standard algorithm, and it is unknown whether the bound can be beaten by nonstandard algorithms. We then consider a special kind of standard algorithm, in which paths are constructed only by concatenating arcs and old paths, never by concatenating two old paths. This restriction seems essential if we are to take advantage of sparseness. Unfortunately, we show that almost another factor ofn I/O is necessary. That is, there is an algorithm in this class using I/OO(n3√e/s) for arbitrary sparse graphs, including cyclic ones. Moreover, every algorithm in the restricted class must useΩ(n3√e/s/log3n) I/O, on some cyclic graphs. More... »

PAGES

331-360

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "Stanford University", 
          "id": "https://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Stanford University, 94305, Stanford, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ullman", 
        "givenName": "Jeffrey D.", 
        "id": "sg:person.012505023635.06", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012505023635.06"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Alcatel-Lucent (United States)", 
          "id": "https://www.grid.ac/institutes/grid.421036.2", 
          "name": [
            "AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yannakakis", 
        "givenName": "Mihalis", 
        "id": "sg:person.014311076616.94", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014311076616.94"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/321105.321107", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006574609"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/362875.362879", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019408505"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/362248.362272", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026240786"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/360715.360746", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051212570"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1991-06", 
    "datePublishedReg": "1991-06-01", 
    "description": "Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holdings \u201cvalues\u201d is available, and thats lies betweenn, the number of nodes of the graph, ande, the number of arcs. The cost measure we use for algorithms is theI/O complexity of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa. In the dense case, wheree is close ton2, we show that I/O equal toO(n3/\u221as) is sufficient to compute the transitive closure of ann-node graph, using main memory of sizes. Moreover, it is necessary for any algorithm that is \u201cstandard,\u201d in a sense to be defined precisely in the paper. Roughly, \u201cstandard\u201d means that paths are constructed only by concatenating arcs and previously discovered paths. For the sparse case, we show that I/O equal toO(n2\u221ae/s) is sufficient, although the algorithm we propose meets our definition of \u201cstandard\u201d only if the underlying graph is acyclic. We also show that\u03a9(n2\u221ae/s) is necessary for any standard algorithm in the sparse case. That settles the I/O complexity of the sparse/acyclic case, for standard algorithms. It is unknown whether this complexity can be achieved in the sparse, cyclic case, by a standard algorithm, and it is unknown whether the bound can be beaten by nonstandard algorithms. We then consider a special kind of standard algorithm, in which paths are constructed only by concatenating arcs and old paths, never by concatenating two old paths. This restriction seems essential if we are to take advantage of sparseness. Unfortunately, we show that almost another factor ofn I/O is necessary. That is, there is an algorithm in this class using I/OO(n3\u221ae/s) for arbitrary sparse graphs, including cyclic ones. Moreover, every algorithm in the restricted class must use\u03a9(n3\u221ae/s/log3n) I/O, on some cyclic graphs.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01530929", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1043955", 
        "issn": [
          "1012-2443", 
          "1573-7470"
        ], 
        "name": "Annals of Mathematics and Artificial Intelligence", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2-4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "3"
      }
    ], 
    "name": "The input/output complexity of transitive closure", 
    "pagination": "331-360", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "96193e0b4048fdc0be826bcb51a1d1dbfc03f71ab75458b0d1101d09307c9f33"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01530929"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031507992"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01530929", 
      "https://app.dimensions.ai/details/publication/pub.1031507992"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T17:29", 
    "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_8672_00000500.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF01530929"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

83 TRIPLES      21 PREDICATES      31 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01530929 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N36471944ae2f4a958ce59b47a5263f36
4 schema:citation https://doi.org/10.1145/321105.321107
5 https://doi.org/10.1145/360715.360746
6 https://doi.org/10.1145/362248.362272
7 https://doi.org/10.1145/362875.362879
8 schema:datePublished 1991-06
9 schema:datePublishedReg 1991-06-01
10 schema:description Suppose a directed graph has its arcs stored in secondary memory, and we wish to compute its transitive closure, also storing the result in secondary memory. We assume that an amount of main memory capable of holdings “values” is available, and thats lies betweenn, the number of nodes of the graph, ande, the number of arcs. The cost measure we use for algorithms is theI/O complexity of Kung and Hong, where we count 1 every time a value is moved into main memory from secondary memory, or vice versa. In the dense case, wheree is close ton2, we show that I/O equal toO(n3/√s) is sufficient to compute the transitive closure of ann-node graph, using main memory of sizes. Moreover, it is necessary for any algorithm that is “standard,” in a sense to be defined precisely in the paper. Roughly, “standard” means that paths are constructed only by concatenating arcs and previously discovered paths. For the sparse case, we show that I/O equal toO(n2√e/s) is sufficient, although the algorithm we propose meets our definition of “standard” only if the underlying graph is acyclic. We also show thatΩ(n2√e/s) is necessary for any standard algorithm in the sparse case. That settles the I/O complexity of the sparse/acyclic case, for standard algorithms. It is unknown whether this complexity can be achieved in the sparse, cyclic case, by a standard algorithm, and it is unknown whether the bound can be beaten by nonstandard algorithms. We then consider a special kind of standard algorithm, in which paths are constructed only by concatenating arcs and old paths, never by concatenating two old paths. This restriction seems essential if we are to take advantage of sparseness. Unfortunately, we show that almost another factor ofn I/O is necessary. That is, there is an algorithm in this class using I/OO(n3√e/s) for arbitrary sparse graphs, including cyclic ones. Moreover, every algorithm in the restricted class must useΩ(n3√e/s/log3n) I/O, on some cyclic graphs.
11 schema:genre research_article
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N1aac318422eb4ba09442f23dbf970944
15 N43e83aba9a294e088aca13b499054afa
16 sg:journal.1043955
17 schema:name The input/output complexity of transitive closure
18 schema:pagination 331-360
19 schema:productId N6485cd22b30c47ed887a4d156b06c629
20 N987eabee88fc49e69b5314cd6341da0d
21 Na3893bc4f0b242139eeca4b9e4f62d28
22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031507992
23 https://doi.org/10.1007/bf01530929
24 schema:sdDatePublished 2019-04-10T17:29
25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
26 schema:sdPublisher N2ac68e4a9c1f49e684b20acdb677927c
27 schema:url http://link.springer.com/10.1007/BF01530929
28 sgo:license sg:explorer/license/
29 sgo:sdDataset articles
30 rdf:type schema:ScholarlyArticle
31 N1aac318422eb4ba09442f23dbf970944 schema:issueNumber 2-4
32 rdf:type schema:PublicationIssue
33 N2ac68e4a9c1f49e684b20acdb677927c schema:name Springer Nature - SN SciGraph project
34 rdf:type schema:Organization
35 N36471944ae2f4a958ce59b47a5263f36 rdf:first sg:person.012505023635.06
36 rdf:rest N60751f20debe49f0b528a9579cee31f9
37 N43e83aba9a294e088aca13b499054afa schema:volumeNumber 3
38 rdf:type schema:PublicationVolume
39 N60751f20debe49f0b528a9579cee31f9 rdf:first sg:person.014311076616.94
40 rdf:rest rdf:nil
41 N6485cd22b30c47ed887a4d156b06c629 schema:name readcube_id
42 schema:value 96193e0b4048fdc0be826bcb51a1d1dbfc03f71ab75458b0d1101d09307c9f33
43 rdf:type schema:PropertyValue
44 N987eabee88fc49e69b5314cd6341da0d schema:name doi
45 schema:value 10.1007/bf01530929
46 rdf:type schema:PropertyValue
47 Na3893bc4f0b242139eeca4b9e4f62d28 schema:name dimensions_id
48 schema:value pub.1031507992
49 rdf:type schema:PropertyValue
50 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
51 schema:name Information and Computing Sciences
52 rdf:type schema:DefinedTerm
53 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
54 schema:name Computation Theory and Mathematics
55 rdf:type schema:DefinedTerm
56 sg:journal.1043955 schema:issn 1012-2443
57 1573-7470
58 schema:name Annals of Mathematics and Artificial Intelligence
59 rdf:type schema:Periodical
60 sg:person.012505023635.06 schema:affiliation https://www.grid.ac/institutes/grid.168010.e
61 schema:familyName Ullman
62 schema:givenName Jeffrey D.
63 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012505023635.06
64 rdf:type schema:Person
65 sg:person.014311076616.94 schema:affiliation https://www.grid.ac/institutes/grid.421036.2
66 schema:familyName Yannakakis
67 schema:givenName Mihalis
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014311076616.94
69 rdf:type schema:Person
70 https://doi.org/10.1145/321105.321107 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006574609
71 rdf:type schema:CreativeWork
72 https://doi.org/10.1145/360715.360746 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051212570
73 rdf:type schema:CreativeWork
74 https://doi.org/10.1145/362248.362272 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026240786
75 rdf:type schema:CreativeWork
76 https://doi.org/10.1145/362875.362879 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019408505
77 rdf:type schema:CreativeWork
78 https://www.grid.ac/institutes/grid.168010.e schema:alternateName Stanford University
79 schema:name Stanford University, 94305, Stanford, CA, USA
80 rdf:type schema:Organization
81 https://www.grid.ac/institutes/grid.421036.2 schema:alternateName Alcatel-Lucent (United States)
82 schema:name AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA
83 rdf:type schema:Organization
 




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


...