Efficient Bulk Operations on Dynamic R-trees View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002-04-19

AUTHORS

Lars Arge , Klaus H. Hinrichs , Jan Vahrenhold , Jeffrey S. Vitter

ABSTRACT

We present a simple lazy buffering technique for performing bulk operations on multidimensional spatial indexes (data structures), and show that it is efficient in theory as well as in practice. We present the technique in terms of the so-called R-tree and its variants, as they have emerged as practically efficient indexing methods for spatial data. More... »

PAGES

322-341

References to SciGraph publications

  • 1997. Spatial data structures: Concepts and design choices in ALGORITHMIC FOUNDATIONS OF GEOGRAPHIC INFORMATION SYSTEMS
  • 1972-09. Organization and maintenance of large ordered indexes in ACTA INFORMATICA
  • 1995. Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep in ALGORITHMS AND DATA STRUCTURES
  • 1996-12. An asymptotically optimal multiversion B-tree in THE VLDB JOURNAL
  • 1995. The buffer tree: A new technique for optimal I/O-algorithms in ALGORITHMS AND DATA STRUCTURES
  • Book

    TITLE

    Algorithm Engineering and Experimentation

    ISBN

    978-3-540-66227-3
    978-3-540-48518-6

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-48518-x_20

    DOI

    http://dx.doi.org/10.1007/3-540-48518-x_20

    DIMENSIONS

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


    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/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "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": [
                "Center for Geometric Computing, Department of Computer Science, Duke University, 27708, Durham, NC, USA"
              ], 
              "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": "University of M\u00fcnster", 
              "id": "https://www.grid.ac/institutes/grid.5949.1", 
              "name": [
                "Institut f\u00fcr Informatik, Westf\u00e4lische Wilhelms-Universit\u00e4t, 48149, M\u00fcnster, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hinrichs", 
            "givenName": "Klaus H.", 
            "id": "sg:person.011723525523.00", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011723525523.00"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of M\u00fcnster", 
              "id": "https://www.grid.ac/institutes/grid.5949.1", 
              "name": [
                "Institut f\u00fcr Informatik, Westf\u00e4lische Wilhelms-Universit\u00e4t, 48149, M\u00fcnster, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Vahrenhold", 
            "givenName": "Jan", 
            "id": "sg:person.014603321763.94", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014603321763.94"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Duke University", 
              "id": "https://www.grid.ac/institutes/grid.26009.3d", 
              "name": [
                "Center for Geometric Computing, Department of Computer Science, Duke University, 27708, Durham, NC, USA"
              ], 
              "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"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/170088.170403", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003526327"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/233269.233338", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013881733"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/48529.48535", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014013712"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s007780050028", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017349674", 
              "https://doi.org/10.1007/s007780050028"
            ], 
            "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-63818-0_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020480392", 
              "https://doi.org/10.1007/3-540-63818-0_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/318898.318900", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024149944"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/93597.98741", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025736774"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/356770.356776", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030753621"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00288683", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032694395", 
              "https://doi.org/10.1007/bf00288683"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00288683", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032694395", 
              "https://doi.org/10.1007/bf00288683"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/253260.253276", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033503190"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/275487.275501", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047551077"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-60220-8_75", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051465486", 
              "https://doi.org/10.1007/3-540-60220-8_75"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/2.268881", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061105270"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icde.1989.47268", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086180375"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icde.1997.582015", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094226347"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2002-04-19", 
        "datePublishedReg": "2002-04-19", 
        "description": "We present a simple lazy buffering technique for performing bulk operations on multidimensional spatial indexes (data structures), and show that it is efficient in theory as well as in practice. We present the technique in terms of the so-called R-tree and its variants, as they have emerged as practically efficient indexing methods for spatial data.", 
        "editor": [
          {
            "familyName": "Goodrich", 
            "givenName": "Michael T.", 
            "type": "Person"
          }, 
          {
            "familyName": "McGeoch", 
            "givenName": "Catherine C.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-48518-x_20", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-66227-3", 
            "978-3-540-48518-6"
          ], 
          "name": "Algorithm Engineering and Experimentation", 
          "type": "Book"
        }, 
        "name": "Efficient Bulk Operations on Dynamic R-trees", 
        "pagination": "322-341", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-48518-x_20"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "898eb913ff62b56bb965195ef5ba93274869667efcc6264889cdbea07cf23ed7"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1028875757"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-48518-x_20", 
          "https://app.dimensions.ai/details/publication/pub.1028875757"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:49", 
        "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/0000000347_0000000347/records_89822_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F3-540-48518-X_20"
      }
    ]
     

    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/3-540-48518-x_20'

    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/3-540-48518-x_20'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48518-x_20'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-48518-x_20'


     

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

    147 TRIPLES      23 PREDICATES      42 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-48518-x_20 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N07d9d4c81ec54780b895ac48837c1a43
    4 schema:citation sg:pub.10.1007/3-540-60220-8_74
    5 sg:pub.10.1007/3-540-60220-8_75
    6 sg:pub.10.1007/3-540-63818-0_6
    7 sg:pub.10.1007/bf00288683
    8 sg:pub.10.1007/s007780050028
    9 https://doi.org/10.1109/2.268881
    10 https://doi.org/10.1109/icde.1989.47268
    11 https://doi.org/10.1109/icde.1997.582015
    12 https://doi.org/10.1145/170088.170403
    13 https://doi.org/10.1145/233269.233338
    14 https://doi.org/10.1145/253260.253276
    15 https://doi.org/10.1145/275487.275501
    16 https://doi.org/10.1145/318898.318900
    17 https://doi.org/10.1145/356770.356776
    18 https://doi.org/10.1145/48529.48535
    19 https://doi.org/10.1145/93597.98741
    20 schema:datePublished 2002-04-19
    21 schema:datePublishedReg 2002-04-19
    22 schema:description We present a simple lazy buffering technique for performing bulk operations on multidimensional spatial indexes (data structures), and show that it is efficient in theory as well as in practice. We present the technique in terms of the so-called R-tree and its variants, as they have emerged as practically efficient indexing methods for spatial data.
    23 schema:editor Na70c73bc0a6d4280997517915b1b07ed
    24 schema:genre chapter
    25 schema:inLanguage en
    26 schema:isAccessibleForFree true
    27 schema:isPartOf N86125adc96184c03b937d430d5474bf1
    28 schema:name Efficient Bulk Operations on Dynamic R-trees
    29 schema:pagination 322-341
    30 schema:productId N59bb3a4500f34b988cc57a6dd36e64f3
    31 Ne9996eabc8e8442abb76d7db3a864e1d
    32 Nf9165a88047b44fc8fbcb8bae37a5e48
    33 schema:publisher N998eb34d62454d44875f30dbe61015a5
    34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028875757
    35 https://doi.org/10.1007/3-540-48518-x_20
    36 schema:sdDatePublished 2019-04-16T05:49
    37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    38 schema:sdPublisher N6163c1c4b39b42caae08f411884aa25b
    39 schema:url https://link.springer.com/10.1007%2F3-540-48518-X_20
    40 sgo:license sg:explorer/license/
    41 sgo:sdDataset chapters
    42 rdf:type schema:Chapter
    43 N07d9d4c81ec54780b895ac48837c1a43 rdf:first sg:person.010251111315.42
    44 rdf:rest N695f85ed8ab74b51b1a694a280c536c5
    45 N17ac40a7acb2491693f879380695fb38 rdf:first sg:person.014603321763.94
    46 rdf:rest N29b7020a416344499b3b1d6f3f4bad69
    47 N29b7020a416344499b3b1d6f3f4bad69 rdf:first sg:person.0613677314.28
    48 rdf:rest rdf:nil
    49 N59bb3a4500f34b988cc57a6dd36e64f3 schema:name doi
    50 schema:value 10.1007/3-540-48518-x_20
    51 rdf:type schema:PropertyValue
    52 N6163c1c4b39b42caae08f411884aa25b schema:name Springer Nature - SN SciGraph project
    53 rdf:type schema:Organization
    54 N695f85ed8ab74b51b1a694a280c536c5 rdf:first sg:person.011723525523.00
    55 rdf:rest N17ac40a7acb2491693f879380695fb38
    56 N86125adc96184c03b937d430d5474bf1 schema:isbn 978-3-540-48518-6
    57 978-3-540-66227-3
    58 schema:name Algorithm Engineering and Experimentation
    59 rdf:type schema:Book
    60 N998eb34d62454d44875f30dbe61015a5 schema:location Berlin, Heidelberg
    61 schema:name Springer Berlin Heidelberg
    62 rdf:type schema:Organisation
    63 Na70c73bc0a6d4280997517915b1b07ed rdf:first Nc5f2e8591e9743cf9c30cc26a2396d96
    64 rdf:rest Naa029eb3497f403b84995262e87ccbf4
    65 Naa029eb3497f403b84995262e87ccbf4 rdf:first Nf69b04c3efdc429a8ff99c861be4f8f1
    66 rdf:rest rdf:nil
    67 Nc5f2e8591e9743cf9c30cc26a2396d96 schema:familyName Goodrich
    68 schema:givenName Michael T.
    69 rdf:type schema:Person
    70 Ne9996eabc8e8442abb76d7db3a864e1d schema:name dimensions_id
    71 schema:value pub.1028875757
    72 rdf:type schema:PropertyValue
    73 Nf69b04c3efdc429a8ff99c861be4f8f1 schema:familyName McGeoch
    74 schema:givenName Catherine C.
    75 rdf:type schema:Person
    76 Nf9165a88047b44fc8fbcb8bae37a5e48 schema:name readcube_id
    77 schema:value 898eb913ff62b56bb965195ef5ba93274869667efcc6264889cdbea07cf23ed7
    78 rdf:type schema:PropertyValue
    79 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    80 schema:name Information and Computing Sciences
    81 rdf:type schema:DefinedTerm
    82 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    83 schema:name Information Systems
    84 rdf:type schema:DefinedTerm
    85 sg:person.010251111315.42 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
    86 schema:familyName Arge
    87 schema:givenName Lars
    88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010251111315.42
    89 rdf:type schema:Person
    90 sg:person.011723525523.00 schema:affiliation https://www.grid.ac/institutes/grid.5949.1
    91 schema:familyName Hinrichs
    92 schema:givenName Klaus H.
    93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011723525523.00
    94 rdf:type schema:Person
    95 sg:person.014603321763.94 schema:affiliation https://www.grid.ac/institutes/grid.5949.1
    96 schema:familyName Vahrenhold
    97 schema:givenName Jan
    98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014603321763.94
    99 rdf:type schema:Person
    100 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
    101 schema:familyName Vitter
    102 schema:givenName Jeffrey S.
    103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
    104 rdf:type schema:Person
    105 sg:pub.10.1007/3-540-60220-8_74 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019870666
    106 https://doi.org/10.1007/3-540-60220-8_74
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/3-540-60220-8_75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051465486
    109 https://doi.org/10.1007/3-540-60220-8_75
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/3-540-63818-0_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020480392
    112 https://doi.org/10.1007/3-540-63818-0_6
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/bf00288683 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032694395
    115 https://doi.org/10.1007/bf00288683
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/s007780050028 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017349674
    118 https://doi.org/10.1007/s007780050028
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1109/2.268881 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061105270
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1109/icde.1989.47268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086180375
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1109/icde.1997.582015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094226347
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1145/170088.170403 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003526327
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1145/233269.233338 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013881733
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1145/253260.253276 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033503190
    131 rdf:type schema:CreativeWork
    132 https://doi.org/10.1145/275487.275501 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047551077
    133 rdf:type schema:CreativeWork
    134 https://doi.org/10.1145/318898.318900 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024149944
    135 rdf:type schema:CreativeWork
    136 https://doi.org/10.1145/356770.356776 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030753621
    137 rdf:type schema:CreativeWork
    138 https://doi.org/10.1145/48529.48535 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014013712
    139 rdf:type schema:CreativeWork
    140 https://doi.org/10.1145/93597.98741 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025736774
    141 rdf:type schema:CreativeWork
    142 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
    143 schema:name Center for Geometric Computing, Department of Computer Science, Duke University, 27708, Durham, NC, USA
    144 rdf:type schema:Organization
    145 https://www.grid.ac/institutes/grid.5949.1 schema:alternateName University of Münster
    146 schema:name Institut für Informatik, Westfälische Wilhelms-Universität, 48149, Münster, Germany
    147 rdf:type schema:Organization
     




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


    ...