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 N79a877a514a74f9499aa200c6d40468a
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 N61621bc58f9445ca87b4b850e815fb33
15 Ndb27af7ebf15466abedec676a4d89a5e
16 sg:journal.1043955
17 schema:name The input/output complexity of transitive closure
18 schema:pagination 331-360
19 schema:productId N2ec7af3cc9da4539b9a31505026ad687
20 N6581fa75c96c49f388732deba02fa74f
21 N659940c19aec4751b38b53fffd106cea
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 N1c404562d1764190b876da70693e8cd5
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 N0c88390057db4a2590900e854a528019 rdf:first sg:person.014311076616.94
32 rdf:rest rdf:nil
33 N1c404562d1764190b876da70693e8cd5 schema:name Springer Nature - SN SciGraph project
34 rdf:type schema:Organization
35 N2ec7af3cc9da4539b9a31505026ad687 schema:name dimensions_id
36 schema:value pub.1031507992
37 rdf:type schema:PropertyValue
38 N61621bc58f9445ca87b4b850e815fb33 schema:volumeNumber 3
39 rdf:type schema:PublicationVolume
40 N6581fa75c96c49f388732deba02fa74f schema:name readcube_id
41 schema:value 96193e0b4048fdc0be826bcb51a1d1dbfc03f71ab75458b0d1101d09307c9f33
42 rdf:type schema:PropertyValue
43 N659940c19aec4751b38b53fffd106cea schema:name doi
44 schema:value 10.1007/bf01530929
45 rdf:type schema:PropertyValue
46 N79a877a514a74f9499aa200c6d40468a rdf:first sg:person.012505023635.06
47 rdf:rest N0c88390057db4a2590900e854a528019
48 Ndb27af7ebf15466abedec676a4d89a5e schema:issueNumber 2-4
49 rdf:type schema:PublicationIssue
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)


...