A Framework for Index Bulk Loading and Dynamization View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2001

AUTHORS

Pankaj K. Agarwal , Lars Arge , Octavian Procopiuc , Jeffrey Scott Vitter

ABSTRACT

In this paper we investigate automated methods for externalizing internal memory data structures.We consider a class of balanced trees that we call weight-balanced partitioning trees (or wp-trees) for indexing a set of points in ℝd.Well-known examples of wp-trees include kd- trees, BBD-trees, pseudo-quad-trees, and BAR-trees. Given an efficient external wp-tree construction algorithm, we present a general framework for automatically obtaining a dynamic external data structure. Using this framework together with a new general construction (bulk loading) technique of independent interest, we obtain data structures with guaranteed good update performance in terms of I/O transfers. Our approach gives considerably improved construction and update I/O bounds for e.g. external kd-trees and BBD-trees. More... »

PAGES

115-127

References to SciGraph publications

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-42287-7
978-3-540-48224-6

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48224-5_10

DOI

http://dx.doi.org/10.1007/3-540-48224-5_10

DIMENSIONS

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


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/0905", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Civil Engineering", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/09", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Engineering", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Center for Geometric Computing, Dept. of Computer Science, Duke University, Durham, NC\u00a027708-0129, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Agarwal", 
        "givenName": "Pankaj K.", 
        "id": "sg:person.01346666674.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01346666674.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Center for Geometric Computing, Dept. of Computer Science, Duke University, Durham, NC\u00a027708-0129, 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": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Center for Geometric Computing, Dept. of Computer Science, Duke University, Durham, NC\u00a027708-0129, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Procopiuc", 
        "givenName": "Octavian", 
        "id": "sg:person.015535453027.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015535453027.07"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Center for Geometric Computing, Dept. of Computer Science, Duke University, Durham, NC\u00a027708-0129, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "Jeffrey Scott", 
        "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/361002.361007", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004029497"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(79)90110-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007301869"
        ], 
        "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/0020-0190(79)90117-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017590104"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/293347.293348", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026320994"
        ], 
        "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": "sg:pub.10.1007/3-540-49257-7_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045979130", 
          "https://doi.org/10.1007/3-540-49257-7_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49257-7_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045979130", 
          "https://doi.org/10.1007/3-540-49257-7_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/99935.99949", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047328192"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/348.318586", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049066804"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/280277.280279", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050640610"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/dimacs/050", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1097022689"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2001", 
    "datePublishedReg": "2001-01-01", 
    "description": "In this paper we investigate automated methods for externalizing internal memory data structures.We consider a class of balanced trees that we call weight-balanced partitioning trees (or wp-trees) for indexing a set of points in \u211dd.Well-known examples of wp-trees include kd- trees, BBD-trees, pseudo-quad-trees, and BAR-trees. Given an efficient external wp-tree construction algorithm, we present a general framework for automatically obtaining a dynamic external data structure. Using this framework together with a new general construction (bulk loading) technique of independent interest, we obtain data structures with guaranteed good update performance in terms of I/O transfers. Our approach gives considerably improved construction and update I/O bounds for e.g. external kd-trees and BBD-trees.", 
    "editor": [
      {
        "familyName": "Orejas", 
        "givenName": "Fernando", 
        "type": "Person"
      }, 
      {
        "familyName": "Spirakis", 
        "givenName": "Paul G.", 
        "type": "Person"
      }, 
      {
        "familyName": "van Leeuwen", 
        "givenName": "Jan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48224-5_10", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42287-7", 
        "978-3-540-48224-6"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "name": "A Framework for Index Bulk Loading and Dynamization", 
    "pagination": "115-127", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48224-5_10"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "4b8fde51974ae2bbb145a72e3e9f9f89c7e02a29e45ad360ee5c64d1f5127440"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1015858439"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48224-5_10", 
      "https://app.dimensions.ai/details/publication/pub.1015858439"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T13: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_8663_00000584.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-48224-5_10"
  }
]
 

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-48224-5_10'

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-48224-5_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48224-5_10'

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-48224-5_10'


 

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

134 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48224-5_10 schema:about anzsrc-for:09
2 anzsrc-for:0905
3 schema:author N244afdd997794925974ee9bcab97f7f4
4 schema:citation sg:pub.10.1007/3-540-49257-7_17
5 sg:pub.10.1007/bf00288683
6 https://doi.org/10.1016/0020-0190(79)90110-8
7 https://doi.org/10.1016/0020-0190(79)90117-0
8 https://doi.org/10.1090/dimacs/050
9 https://doi.org/10.1145/280277.280279
10 https://doi.org/10.1145/293347.293348
11 https://doi.org/10.1145/348.318586
12 https://doi.org/10.1145/356770.356776
13 https://doi.org/10.1145/361002.361007
14 https://doi.org/10.1145/48529.48535
15 https://doi.org/10.1145/99935.99949
16 schema:datePublished 2001
17 schema:datePublishedReg 2001-01-01
18 schema:description In this paper we investigate automated methods for externalizing internal memory data structures.We consider a class of balanced trees that we call weight-balanced partitioning trees (or wp-trees) for indexing a set of points in ℝd.Well-known examples of wp-trees include kd- trees, BBD-trees, pseudo-quad-trees, and BAR-trees. Given an efficient external wp-tree construction algorithm, we present a general framework for automatically obtaining a dynamic external data structure. Using this framework together with a new general construction (bulk loading) technique of independent interest, we obtain data structures with guaranteed good update performance in terms of I/O transfers. Our approach gives considerably improved construction and update I/O bounds for e.g. external kd-trees and BBD-trees.
19 schema:editor N638999dd1467490481ad5789dd46b802
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree true
23 schema:isPartOf Naa89133c4f5745feb2abaed0baf722bb
24 schema:name A Framework for Index Bulk Loading and Dynamization
25 schema:pagination 115-127
26 schema:productId N220e08643ed546218f49788ebf9f1e62
27 Nc55ec2a570764d76ab7277bba7411f06
28 Nf799bc5c04e84c188c5a9cea25d95e7f
29 schema:publisher Nadcc427ef50a4b21b09356ab4a656938
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015858439
31 https://doi.org/10.1007/3-540-48224-5_10
32 schema:sdDatePublished 2019-04-15T13:08
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher Nb531061a3a1d4fcaa8fbc20b8643c70c
35 schema:url http://link.springer.com/10.1007/3-540-48224-5_10
36 sgo:license sg:explorer/license/
37 sgo:sdDataset chapters
38 rdf:type schema:Chapter
39 N220e08643ed546218f49788ebf9f1e62 schema:name doi
40 schema:value 10.1007/3-540-48224-5_10
41 rdf:type schema:PropertyValue
42 N244afdd997794925974ee9bcab97f7f4 rdf:first sg:person.01346666674.21
43 rdf:rest N3eac5249c3c04e08884240bccad44d4a
44 N3eac5249c3c04e08884240bccad44d4a rdf:first sg:person.010251111315.42
45 rdf:rest Nfe7925ff0a6e43a1902f63f9de515c80
46 N585d0bfa37984f9fb06d526d509bb95c schema:familyName Spirakis
47 schema:givenName Paul G.
48 rdf:type schema:Person
49 N61af5813dfca4727abc05a52a9e6517c rdf:first sg:person.0613677314.28
50 rdf:rest rdf:nil
51 N638999dd1467490481ad5789dd46b802 rdf:first N8a26c999b2ed49e3b1170660bf317c83
52 rdf:rest N84c937c68f7245f39cf5dd1500bcad9a
53 N81267e795fcb4f30aa9896968095f625 schema:familyName van Leeuwen
54 schema:givenName Jan
55 rdf:type schema:Person
56 N84c937c68f7245f39cf5dd1500bcad9a rdf:first N585d0bfa37984f9fb06d526d509bb95c
57 rdf:rest Nbb5d9c57ca914bb1980d0a719945c7e0
58 N8a26c999b2ed49e3b1170660bf317c83 schema:familyName Orejas
59 schema:givenName Fernando
60 rdf:type schema:Person
61 Naa89133c4f5745feb2abaed0baf722bb schema:isbn 978-3-540-42287-7
62 978-3-540-48224-6
63 schema:name Automata, Languages and Programming
64 rdf:type schema:Book
65 Nadcc427ef50a4b21b09356ab4a656938 schema:location Berlin, Heidelberg
66 schema:name Springer Berlin Heidelberg
67 rdf:type schema:Organisation
68 Nb531061a3a1d4fcaa8fbc20b8643c70c schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 Nbb5d9c57ca914bb1980d0a719945c7e0 rdf:first N81267e795fcb4f30aa9896968095f625
71 rdf:rest rdf:nil
72 Nc55ec2a570764d76ab7277bba7411f06 schema:name readcube_id
73 schema:value 4b8fde51974ae2bbb145a72e3e9f9f89c7e02a29e45ad360ee5c64d1f5127440
74 rdf:type schema:PropertyValue
75 Nf799bc5c04e84c188c5a9cea25d95e7f schema:name dimensions_id
76 schema:value pub.1015858439
77 rdf:type schema:PropertyValue
78 Nfe7925ff0a6e43a1902f63f9de515c80 rdf:first sg:person.015535453027.07
79 rdf:rest N61af5813dfca4727abc05a52a9e6517c
80 anzsrc-for:09 schema:inDefinedTermSet anzsrc-for:
81 schema:name Engineering
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0905 schema:inDefinedTermSet anzsrc-for:
84 schema:name Civil Engineering
85 rdf:type schema:DefinedTerm
86 sg:person.010251111315.42 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
87 schema:familyName Arge
88 schema:givenName Lars
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010251111315.42
90 rdf:type schema:Person
91 sg:person.01346666674.21 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
92 schema:familyName Agarwal
93 schema:givenName Pankaj K.
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01346666674.21
95 rdf:type schema:Person
96 sg:person.015535453027.07 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
97 schema:familyName Procopiuc
98 schema:givenName Octavian
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015535453027.07
100 rdf:type schema:Person
101 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
102 schema:familyName Vitter
103 schema:givenName Jeffrey Scott
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
105 rdf:type schema:Person
106 sg:pub.10.1007/3-540-49257-7_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045979130
107 https://doi.org/10.1007/3-540-49257-7_17
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/bf00288683 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032694395
110 https://doi.org/10.1007/bf00288683
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/0020-0190(79)90110-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007301869
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/0020-0190(79)90117-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017590104
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1090/dimacs/050 schema:sameAs https://app.dimensions.ai/details/publication/pub.1097022689
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1145/280277.280279 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050640610
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1145/293347.293348 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026320994
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1145/348.318586 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049066804
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/356770.356776 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030753621
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/361002.361007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004029497
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1145/48529.48535 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014013712
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1145/99935.99949 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047328192
131 rdf:type schema:CreativeWork
132 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
133 schema:name Center for Geometric Computing, Dept. of Computer Science, Duke University, Durham, NC 27708-0129, USA
134 rdf:type schema:Organization
 




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


...