Space Efficient Multi-dimensional Range Reporting View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Marek Karpinski , Yakov Nekrich

ABSTRACT

We present a data structure that supports three-dimensional range reporting queries in O(loglogU + (loglogn)3 + k) time and uses O(nlog1 + εn) space, where U is the size of the universe, k is the number of points in the answer, and ε is an arbitrary constant. This result improves over the data structure of Alstrup, Brodal, and Rauhe (FOCS 2000) that uses O(nlog1 + εn) space and supports queries in O(logn + k) time, the data structure of Nekrich (SoCG’07) that uses O(nlog3n) space and supports queries in O(loglogU + (loglogn)2 + k) time, and the data structure of Afshani (ESA’08) that uses O(nlog3n) space and also supports queries in O(loglogU + (loglogn)2 + k) time but relies on randomization during the preprocessing stage. Our result allows us to significantly reduce the space usage of the fastest previously known static and incremental d-dimensional data structures, d ≥ 3, at a cost of increasing the query time by a negligible O(loglogn) factor. More... »

PAGES

215-224

Book

TITLE

Computing and Combinatorics

ISBN

978-3-642-02881-6
978-3-642-02882-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-02882-3_22

DOI

http://dx.doi.org/10.1007/978-3-642-02882-3_22

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nekrich", 
        "givenName": "Yakov", 
        "id": "sg:person.014556642366.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "We present a data structure that supports three-dimensional range reporting queries in O(loglogU\u2009+\u2009(loglogn)3\u2009+\u2009k) time and uses O(nlog1\u2009+\u2009\u03b5n) space, where U is the size of the universe, k is the number of points in the answer, and \u03b5 is an arbitrary constant. This result improves over the data structure of Alstrup, Brodal, and Rauhe (FOCS 2000) that uses O(nlog1\u2009+\u2009\u03b5n) space and supports queries in O(logn\u2009+\u2009k) time, the data structure of Nekrich (SoCG\u201907) that uses O(nlog3n) space and supports queries in O(loglogU\u2009+\u2009(loglogn)2\u2009+\u2009k) time, and the data structure of Afshani (ESA\u201908) that uses O(nlog3n) space and also supports queries in O(loglogU\u2009+\u2009(loglogn)2\u2009+\u2009k) time but relies on randomization during the preprocessing stage. Our result allows us to significantly reduce the space usage of the fastest previously known static and incremental d-dimensional data structures, d\u2009\u2265\u20093, at a cost of increasing the query time by a negligible O(loglogn) factor.", 
    "editor": [
      {
        "familyName": "Ngo", 
        "givenName": "Hung Q.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-02882-3_22", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-02881-6", 
        "978-3-642-02882-3"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "data structure", 
      "dimensional data structure", 
      "query time", 
      "queries", 
      "space usage", 
      "range reporting", 
      "number of points", 
      "three-dimensional range", 
      "space", 
      "Nekrich", 
      "usage", 
      "Alstrup", 
      "Brodal", 
      "Rauhe", 
      "cost", 
      "time", 
      "answers", 
      "results", 
      "structure", 
      "number", 
      "point", 
      "reporting", 
      "randomization", 
      "stage", 
      "size", 
      "universe", 
      "range", 
      "arbitrary constants", 
      "factors", 
      "constants"
    ], 
    "name": "Space Efficient Multi-dimensional Range Reporting", 
    "pagination": "215-224", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031630744"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-02882-3_22"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-02882-3_22", 
      "https://app.dimensions.ai/details/publication/pub.1031630744"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:49", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_257.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-02882-3_22"
  }
]
 

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/978-3-642-02882-3_22'

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/978-3-642-02882-3_22'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-02882-3_22'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-02882-3_22'


 

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

96 TRIPLES      22 PREDICATES      55 URIs      48 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-02882-3_22 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N989799d3444b4e00ae2b2c3fcfc7c4d0
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description We present a data structure that supports three-dimensional range reporting queries in O(loglogU + (loglogn)3 + k) time and uses O(nlog1 + εn) space, where U is the size of the universe, k is the number of points in the answer, and ε is an arbitrary constant. This result improves over the data structure of Alstrup, Brodal, and Rauhe (FOCS 2000) that uses O(nlog1 + εn) space and supports queries in O(logn + k) time, the data structure of Nekrich (SoCG’07) that uses O(nlog3n) space and supports queries in O(loglogU + (loglogn)2 + k) time, and the data structure of Afshani (ESA’08) that uses O(nlog3n) space and also supports queries in O(loglogU + (loglogn)2 + k) time but relies on randomization during the preprocessing stage. Our result allows us to significantly reduce the space usage of the fastest previously known static and incremental d-dimensional data structures, d ≥ 3, at a cost of increasing the query time by a negligible O(loglogn) factor.
7 schema:editor N2f4a69d3cb5947f59e0d500c192e7caf
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N2b61aa7260f4489eb51c75df93d5c506
11 schema:keywords Alstrup
12 Brodal
13 Nekrich
14 Rauhe
15 answers
16 arbitrary constants
17 constants
18 cost
19 data structure
20 dimensional data structure
21 factors
22 number
23 number of points
24 point
25 queries
26 query time
27 randomization
28 range
29 range reporting
30 reporting
31 results
32 size
33 space
34 space usage
35 stage
36 structure
37 three-dimensional range
38 time
39 universe
40 usage
41 schema:name Space Efficient Multi-dimensional Range Reporting
42 schema:pagination 215-224
43 schema:productId N9341f1bfa75643619fac85631b9d627b
44 Ndbd9c413c06d45ba900ad67004cfbbd1
45 schema:publisher Nf69599d7352044119aad8f5edcc53ed0
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031630744
47 https://doi.org/10.1007/978-3-642-02882-3_22
48 schema:sdDatePublished 2022-12-01T06:49
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher Nf7e683f396cf49c18b9439553a8a7e30
51 schema:url https://doi.org/10.1007/978-3-642-02882-3_22
52 sgo:license sg:explorer/license/
53 sgo:sdDataset chapters
54 rdf:type schema:Chapter
55 N2b61aa7260f4489eb51c75df93d5c506 schema:isbn 978-3-642-02881-6
56 978-3-642-02882-3
57 schema:name Computing and Combinatorics
58 rdf:type schema:Book
59 N2f4a69d3cb5947f59e0d500c192e7caf rdf:first Na43fbd63a05c4496a72cce8d12a7ac7d
60 rdf:rest rdf:nil
61 N9341f1bfa75643619fac85631b9d627b schema:name dimensions_id
62 schema:value pub.1031630744
63 rdf:type schema:PropertyValue
64 N989799d3444b4e00ae2b2c3fcfc7c4d0 rdf:first sg:person.011636042271.02
65 rdf:rest Nc49cabafa2b64d79bc8d5c18c4a9ca5c
66 Na43fbd63a05c4496a72cce8d12a7ac7d schema:familyName Ngo
67 schema:givenName Hung Q.
68 rdf:type schema:Person
69 Nc49cabafa2b64d79bc8d5c18c4a9ca5c rdf:first sg:person.014556642366.63
70 rdf:rest rdf:nil
71 Ndbd9c413c06d45ba900ad67004cfbbd1 schema:name doi
72 schema:value 10.1007/978-3-642-02882-3_22
73 rdf:type schema:PropertyValue
74 Nf69599d7352044119aad8f5edcc53ed0 schema:name Springer Nature
75 rdf:type schema:Organisation
76 Nf7e683f396cf49c18b9439553a8a7e30 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
79 schema:name Information and Computing Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
82 schema:name Artificial Intelligence and Image Processing
83 rdf:type schema:DefinedTerm
84 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
85 schema:familyName Karpinski
86 schema:givenName Marek
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
88 rdf:type schema:Person
89 sg:person.014556642366.63 schema:affiliation grid-institutes:grid.10388.32
90 schema:familyName Nekrich
91 schema:givenName Yakov
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63
93 rdf:type schema:Person
94 grid-institutes:grid.10388.32 schema:alternateName Dept. of Computer Science, University of Bonn, Germany
95 schema:name Dept. of Computer Science, University of Bonn, Germany
96 rdf:type schema:Organization
 




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


...