Efficient Bulk Operations on Dynamic R-Trees View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2002-05

AUTHORS

L. Arge, K. H. Hinrichs, J. Vahrenhold, J. S. Vitter

ABSTRACT

In recent years there has been an upsurge of interest in spatial databases. A major issue is how to manipulate efficiently massive amounts of spatial data stored on disk in multidimensional spatial indexes (data structures). Construction of spatial indexes (bulk loading ) has been studied intensively in the database community. The continuous arrival of massive amounts of new data makes it important to update existing indexes (bulk updating ) efficiently. In this paper we present a simple, yet efficient, technique for performing bulk update and query operations on multidimensional indexes. We present our technique in terms of the so-called R-tree and its variants, as they have emerged as practically efficient indexing methods for spatial data. Our method uses ideas from the buffer tree lazy buffering technique and fully utilizes the available internal memory and the page size of the operating system. We give a theoretical analysis of our technique, showing that it is efficient both in terms of I/ O communication, disk storage, and internal computation time. We also present the results of an extensive set of experiments showing that in practice our approach performs better than the previously best known bulk update methods with respect to update time, and that it produces a better quality index in terms of query performance. One important novel feature of our technique is that in most cases it allows us to perform a batch of updates and queries simultaneously. To be able to do so is essential in environments where queries have to be answered even while the index is being updated and reorganized. More... »

PAGES

104-128

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-001-0107-6

DOI

http://dx.doi.org/10.1007/s00453-001-0107-6

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "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, Durham, NC 27708, USA. \\{large,jsv\\}@duke.edu., US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Arge", 
        "givenName": "L.", 
        "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.  \\{khh,jan\\}@math.uni-muenster.de., DE"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hinrichs", 
        "givenName": "K. 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.  \\{khh,jan\\}@math.uni-muenster.de., DE"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vahrenhold", 
        "givenName": "J.", 
        "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, Durham, NC 27708, USA. \\{large,jsv\\}@duke.edu., US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "J. S.", 
        "id": "sg:person.011604033325.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011604033325.33"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002-05", 
    "datePublishedReg": "2002-05-01", 
    "description": "In recent years there has been an upsurge of interest in spatial databases. A major issue is how to manipulate efficiently massive amounts of spatial data stored on disk in multidimensional spatial indexes (data structures). Construction of spatial indexes (bulk loading ) has been studied intensively in the database community. The continuous arrival of massive amounts of new data makes it important to update existing indexes (bulk updating ) efficiently. In this paper we present a simple, yet efficient, technique for performing bulk update and query operations on multidimensional indexes. We present our technique in terms of the so-called R-tree and its variants, as they have emerged as practically efficient indexing methods for spatial data. Our method uses ideas from the buffer tree lazy buffering technique and fully utilizes the available internal memory and the page size of the operating system. We give a theoretical analysis of our technique, showing that it is efficient both in terms of I/ O communication, disk storage, and internal computation time. We also present the results of an extensive set of experiments showing that in practice our approach performs better than the previously best known bulk update methods with respect to update time, and that it produces a better quality index in terms of query performance. One important novel feature of our technique is that in most cases it allows us to perform a batch of updates and queries simultaneously. To be able to do so is essential in environments where queries have to be answered even while the index is being updated and reorganized.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00453-001-0107-6", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "33"
      }
    ], 
    "name": "Efficient Bulk Operations on Dynamic R-Trees", 
    "pagination": "104-128", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "7494fd1f237401f827fa7cfe42b6a50678c7c991acf73bec822d61bbaed928c6"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-001-0107-6"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024471235"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-001-0107-6", 
      "https://app.dimensions.ai/details/publication/pub.1024471235"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T19:08", 
    "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_00000512.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs00453-001-0107-6"
  }
]
 

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/s00453-001-0107-6'

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/s00453-001-0107-6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-001-0107-6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-001-0107-6'


 

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

85 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-001-0107-6 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N1e342f1bc056466b81b629a5678e5267
4 schema:datePublished 2002-05
5 schema:datePublishedReg 2002-05-01
6 schema:description In recent years there has been an upsurge of interest in spatial databases. A major issue is how to manipulate efficiently massive amounts of spatial data stored on disk in multidimensional spatial indexes (data structures). Construction of spatial indexes (bulk loading ) has been studied intensively in the database community. The continuous arrival of massive amounts of new data makes it important to update existing indexes (bulk updating ) efficiently. In this paper we present a simple, yet efficient, technique for performing bulk update and query operations on multidimensional indexes. We present our technique in terms of the so-called R-tree and its variants, as they have emerged as practically efficient indexing methods for spatial data. Our method uses ideas from the buffer tree lazy buffering technique and fully utilizes the available internal memory and the page size of the operating system. We give a theoretical analysis of our technique, showing that it is efficient both in terms of I/ O communication, disk storage, and internal computation time. We also present the results of an extensive set of experiments showing that in practice our approach performs better than the previously best known bulk update methods with respect to update time, and that it produces a better quality index in terms of query performance. One important novel feature of our technique is that in most cases it allows us to perform a batch of updates and queries simultaneously. To be able to do so is essential in environments where queries have to be answered even while the index is being updated and reorganized.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf N148005b21eeb40d3926b5c230e12195c
11 Nb8548680ee6243f5a18d5a87ec6a28ae
12 sg:journal.1047644
13 schema:name Efficient Bulk Operations on Dynamic R-Trees
14 schema:pagination 104-128
15 schema:productId N462f9397df714d04a316fc5889879859
16 N7fc67d5b7935407394eed9698a97dfa9
17 Ncc3832d3203b4533aa30ab6ea054bda6
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024471235
19 https://doi.org/10.1007/s00453-001-0107-6
20 schema:sdDatePublished 2019-04-10T19:08
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nd65c33ef696b4a1c8ec9fb667e1c4e80
23 schema:url http://link.springer.com/10.1007%2Fs00453-001-0107-6
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N148005b21eeb40d3926b5c230e12195c schema:issueNumber 1
28 rdf:type schema:PublicationIssue
29 N1e342f1bc056466b81b629a5678e5267 rdf:first sg:person.010251111315.42
30 rdf:rest N2800719c64bd4fdcb8dbea458c45b063
31 N2800719c64bd4fdcb8dbea458c45b063 rdf:first sg:person.011723525523.00
32 rdf:rest N49256601cb7840a88bc65f0e7da07de9
33 N462f9397df714d04a316fc5889879859 schema:name doi
34 schema:value 10.1007/s00453-001-0107-6
35 rdf:type schema:PropertyValue
36 N49256601cb7840a88bc65f0e7da07de9 rdf:first sg:person.014603321763.94
37 rdf:rest Nc2baf63eeef74b85828ac07fe17695c0
38 N7fc67d5b7935407394eed9698a97dfa9 schema:name dimensions_id
39 schema:value pub.1024471235
40 rdf:type schema:PropertyValue
41 Nb8548680ee6243f5a18d5a87ec6a28ae schema:volumeNumber 33
42 rdf:type schema:PublicationVolume
43 Nc2baf63eeef74b85828ac07fe17695c0 rdf:first sg:person.011604033325.33
44 rdf:rest rdf:nil
45 Ncc3832d3203b4533aa30ab6ea054bda6 schema:name readcube_id
46 schema:value 7494fd1f237401f827fa7cfe42b6a50678c7c991acf73bec822d61bbaed928c6
47 rdf:type schema:PropertyValue
48 Nd65c33ef696b4a1c8ec9fb667e1c4e80 schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
51 schema:name Information and Computing Sciences
52 rdf:type schema:DefinedTerm
53 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
54 schema:name Data Format
55 rdf:type schema:DefinedTerm
56 sg:journal.1047644 schema:issn 0178-4617
57 1432-0541
58 schema:name Algorithmica
59 rdf:type schema:Periodical
60 sg:person.010251111315.42 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
61 schema:familyName Arge
62 schema:givenName L.
63 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010251111315.42
64 rdf:type schema:Person
65 sg:person.011604033325.33 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
66 schema:familyName Vitter
67 schema:givenName J. S.
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011604033325.33
69 rdf:type schema:Person
70 sg:person.011723525523.00 schema:affiliation https://www.grid.ac/institutes/grid.5949.1
71 schema:familyName Hinrichs
72 schema:givenName K. H.
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011723525523.00
74 rdf:type schema:Person
75 sg:person.014603321763.94 schema:affiliation https://www.grid.ac/institutes/grid.5949.1
76 schema:familyName Vahrenhold
77 schema:givenName J.
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014603321763.94
79 rdf:type schema:Person
80 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
81 schema:name Center for Geometric Computing, Department of Computer Science, Duke University, Durham, NC 27708, USA. \{large,jsv\}@duke.edu., US
82 rdf:type schema:Organization
83 https://www.grid.ac/institutes/grid.5949.1 schema:alternateName University of Münster
84 schema:name Institut für Informatik, Westfälische Wilhelms-Universität, 48149 Münster, Germany. \{khh,jan\}@math.uni-muenster.de., DE
85 rdf:type schema:Organization
 




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


...