Efficient Flow Computation on Massive Grid Terrain Datasets View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2003-12

AUTHORS

Lars Arge, Jeffrey S. Chase, Patrick Halpin, Laura Toma, Jeffrey S. Vitter, Dean Urban, Rajiv Wickremesinghe

ABSTRACT

As detailed terrain data becomes available, GIS terrain applications target larger geographic areas at finer resolutions. Processing the massive datasets involved in such applications presents significant challenges to GIS systems and demands algorithms that are optimized for both data movement and computation. In this paper we present efficient algorithms for flow routing on massive grid terrain datasets, extending our previous work on flow accumulation. Our algorithms are developed in the framework of external memory algorithms and use I/O-techniques to achieve efficiency. We have implemented the algorithms in the Terraflow system, which is the first comprehensive terrain flow software system designed and optimized for massive data. We compare the performance of Terraflow with that of state-of-the-art commercial and open-source GIS systems. On large terrains, Terraflow outperforms existing systems by a factor of 2 to 1,000, and is capable of solving problems no system was previously able to solve. More... »

PAGES

283-313

Identifiers

URI

http://scigraph.springernature.com/pub.10.1023/a:1025526421410

DOI

http://dx.doi.org/10.1023/a:1025526421410

DIMENSIONS

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


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, 27708, Durham, NC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Arge", 
        "givenName": "Lars", 
        "id": "sg:person.010251111315.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010251111315.42"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708, Durham, NC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chase", 
        "givenName": "Jeffrey S.", 
        "id": "sg:person.0701261414.56", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0701261414.56"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Nicholas School of the Environment, Duke University, 27708, Durham, NC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Halpin", 
        "givenName": "Patrick", 
        "id": "sg:person.0770041455.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0770041455.34"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708, Durham, NC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Toma", 
        "givenName": "Laura", 
        "id": "sg:person.016211771373.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016211771373.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708, Durham, NC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "Jeffrey S.", 
        "id": "sg:person.0613677314.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Nicholas School of the Environment, Duke University, 27708, Durham, NC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Urban", 
        "givenName": "Dean", 
        "id": "sg:person.0615624451.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0615624451.46"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708, Durham, NC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wickremesinghe", 
        "givenName": "Rajiv", 
        "id": "sg:person.014145763433.55", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014145763433.55"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0022-1694(92)90206-b", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000748396"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-1694(92)90206-b", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000748396"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1029/96wr03137", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001405336"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0098-3004(91)90048-i", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006809188"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0098-3004(91)90048-i", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006809188"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1029/90wr02658", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009547616"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/hyp.3360050103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011361795"
        ], 
        "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.1016/s0022-1694(96)03138-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024676111"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/hyp.3360050107", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028048264"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0169-555x(88)90011-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032296137"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0169-555x(88)90011-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032296137"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/384192.384193", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040182656"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1029/95wr00471", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049199853"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0098-3004(92)90007-e", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052351910"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0098-3004(92)90007-e", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052351910"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2003-12", 
    "datePublishedReg": "2003-12-01", 
    "description": "As detailed terrain data becomes available, GIS terrain applications target larger geographic areas at finer resolutions. Processing the massive datasets involved in such applications presents significant challenges to GIS systems and demands algorithms that are optimized for both data movement and computation. In this paper we present efficient algorithms for flow routing on massive grid terrain datasets, extending our previous work on flow accumulation. Our algorithms are developed in the framework of external memory algorithms and use I/O-techniques to achieve efficiency. We have implemented the algorithms in the Terraflow system, which is the first comprehensive terrain flow software system designed and optimized for massive data. We compare the performance of Terraflow with that of state-of-the-art commercial and open-source GIS systems. On large terrains, Terraflow outperforms existing systems by a factor of 2 to 1,000, and is capable of solving problems no system was previously able to solve.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1023/a:1025526421410", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1043850", 
        "issn": [
          "1384-6175", 
          "1573-7624"
        ], 
        "name": "GeoInformatica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "7"
      }
    ], 
    "name": "Efficient Flow Computation on Massive Grid Terrain Datasets", 
    "pagination": "283-313", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "36101a94d3dc64e988b85a47ec5c1a8bb96a819578468bf2abddc38c0f02eed3"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1023/a:1025526421410"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011347359"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1023/a:1025526421410", 
      "https://app.dimensions.ai/details/publication/pub.1011347359"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T19:06", 
    "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_8678_00000504.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1023%2FA%3A1025526421410"
  }
]
 

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.1023/a:1025526421410'

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.1023/a:1025526421410'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1025526421410'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1025526421410'


 

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

140 TRIPLES      21 PREDICATES      39 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1023/a:1025526421410 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N94878751ba574e1fae1c84e072bc2f8e
4 schema:citation https://doi.org/10.1002/hyp.3360050103
5 https://doi.org/10.1002/hyp.3360050107
6 https://doi.org/10.1016/0022-1694(92)90206-b
7 https://doi.org/10.1016/0098-3004(91)90048-i
8 https://doi.org/10.1016/0098-3004(92)90007-e
9 https://doi.org/10.1016/0169-555x(88)90011-6
10 https://doi.org/10.1016/s0022-1694(96)03138-1
11 https://doi.org/10.1029/90wr02658
12 https://doi.org/10.1029/95wr00471
13 https://doi.org/10.1029/96wr03137
14 https://doi.org/10.1145/384192.384193
15 https://doi.org/10.1145/48529.48535
16 schema:datePublished 2003-12
17 schema:datePublishedReg 2003-12-01
18 schema:description As detailed terrain data becomes available, GIS terrain applications target larger geographic areas at finer resolutions. Processing the massive datasets involved in such applications presents significant challenges to GIS systems and demands algorithms that are optimized for both data movement and computation. In this paper we present efficient algorithms for flow routing on massive grid terrain datasets, extending our previous work on flow accumulation. Our algorithms are developed in the framework of external memory algorithms and use I/O-techniques to achieve efficiency. We have implemented the algorithms in the Terraflow system, which is the first comprehensive terrain flow software system designed and optimized for massive data. We compare the performance of Terraflow with that of state-of-the-art commercial and open-source GIS systems. On large terrains, Terraflow outperforms existing systems by a factor of 2 to 1,000, and is capable of solving problems no system was previously able to solve.
19 schema:genre research_article
20 schema:inLanguage en
21 schema:isAccessibleForFree true
22 schema:isPartOf Nc7bd584919054f18946bc67e2f10802f
23 Nd1c9b1b37c7d41e58a13a303215c013d
24 sg:journal.1043850
25 schema:name Efficient Flow Computation on Massive Grid Terrain Datasets
26 schema:pagination 283-313
27 schema:productId Nd01ed6cc976d49d59265603cca840c09
28 Ne70118d6a1124326a254656801121de3
29 Nf4e1832a961043878d9a3916785f87ce
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011347359
31 https://doi.org/10.1023/a:1025526421410
32 schema:sdDatePublished 2019-04-10T19:06
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher N5e846864453545b6b6edd9038e67c669
35 schema:url http://link.springer.com/10.1023%2FA%3A1025526421410
36 sgo:license sg:explorer/license/
37 sgo:sdDataset articles
38 rdf:type schema:ScholarlyArticle
39 N07e8a58eecdb4ead9ae65bc5e3958358 rdf:first sg:person.016211771373.00
40 rdf:rest Nad4ea3c6e5544ac5848e0d483746fd73
41 N4cb86e811d72498e8bf84e373ab420d6 rdf:first sg:person.014145763433.55
42 rdf:rest rdf:nil
43 N5c4bbdad79ea45898bfa073717c63caa rdf:first sg:person.0701261414.56
44 rdf:rest Nac4eb280f4ee480fb22487a921c6234f
45 N5e846864453545b6b6edd9038e67c669 schema:name Springer Nature - SN SciGraph project
46 rdf:type schema:Organization
47 N94878751ba574e1fae1c84e072bc2f8e rdf:first sg:person.010251111315.42
48 rdf:rest N5c4bbdad79ea45898bfa073717c63caa
49 Nac4eb280f4ee480fb22487a921c6234f rdf:first sg:person.0770041455.34
50 rdf:rest N07e8a58eecdb4ead9ae65bc5e3958358
51 Nad4ea3c6e5544ac5848e0d483746fd73 rdf:first sg:person.0613677314.28
52 rdf:rest Nfc77f352247a4b3591a45bef8e81105b
53 Nc7bd584919054f18946bc67e2f10802f schema:volumeNumber 7
54 rdf:type schema:PublicationVolume
55 Nd01ed6cc976d49d59265603cca840c09 schema:name readcube_id
56 schema:value 36101a94d3dc64e988b85a47ec5c1a8bb96a819578468bf2abddc38c0f02eed3
57 rdf:type schema:PropertyValue
58 Nd1c9b1b37c7d41e58a13a303215c013d schema:issueNumber 4
59 rdf:type schema:PublicationIssue
60 Ne70118d6a1124326a254656801121de3 schema:name doi
61 schema:value 10.1023/a:1025526421410
62 rdf:type schema:PropertyValue
63 Nf4e1832a961043878d9a3916785f87ce schema:name dimensions_id
64 schema:value pub.1011347359
65 rdf:type schema:PropertyValue
66 Nfc77f352247a4b3591a45bef8e81105b rdf:first sg:person.0615624451.46
67 rdf:rest N4cb86e811d72498e8bf84e373ab420d6
68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
69 schema:name Information and Computing Sciences
70 rdf:type schema:DefinedTerm
71 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
72 schema:name Computation Theory and Mathematics
73 rdf:type schema:DefinedTerm
74 sg:journal.1043850 schema:issn 1384-6175
75 1573-7624
76 schema:name GeoInformatica
77 rdf:type schema:Periodical
78 sg:person.010251111315.42 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
79 schema:familyName Arge
80 schema:givenName Lars
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010251111315.42
82 rdf:type schema:Person
83 sg:person.014145763433.55 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
84 schema:familyName Wickremesinghe
85 schema:givenName Rajiv
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014145763433.55
87 rdf:type schema:Person
88 sg:person.016211771373.00 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
89 schema:familyName Toma
90 schema:givenName Laura
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016211771373.00
92 rdf:type schema:Person
93 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
94 schema:familyName Vitter
95 schema:givenName Jeffrey S.
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
97 rdf:type schema:Person
98 sg:person.0615624451.46 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
99 schema:familyName Urban
100 schema:givenName Dean
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0615624451.46
102 rdf:type schema:Person
103 sg:person.0701261414.56 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
104 schema:familyName Chase
105 schema:givenName Jeffrey S.
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0701261414.56
107 rdf:type schema:Person
108 sg:person.0770041455.34 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
109 schema:familyName Halpin
110 schema:givenName Patrick
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0770041455.34
112 rdf:type schema:Person
113 https://doi.org/10.1002/hyp.3360050103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011361795
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1002/hyp.3360050107 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028048264
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1016/0022-1694(92)90206-b schema:sameAs https://app.dimensions.ai/details/publication/pub.1000748396
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1016/0098-3004(91)90048-i schema:sameAs https://app.dimensions.ai/details/publication/pub.1006809188
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1016/0098-3004(92)90007-e schema:sameAs https://app.dimensions.ai/details/publication/pub.1052351910
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1016/0169-555x(88)90011-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032296137
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1016/s0022-1694(96)03138-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024676111
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1029/90wr02658 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009547616
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1029/95wr00471 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049199853
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1029/96wr03137 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001405336
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1145/384192.384193 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040182656
134 rdf:type schema:CreativeWork
135 https://doi.org/10.1145/48529.48535 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014013712
136 rdf:type schema:CreativeWork
137 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
138 schema:name Department of Computer Science, Duke University, 27708, Durham, NC
139 Nicholas School of the Environment, Duke University, 27708, Durham, NC
140 rdf:type schema:Organization
 




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


...