Optimal Color Range Reporting in One Dimension View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Yakov Nekrich , Jeffrey Scott Vitter

ABSTRACT

Color (or categorical) range reporting is a variant of the orthogonal range reporting problem in which every point in the input is assigned a color. While the answer to an orthogonal point reporting query contains all points in the query range Q, the answer to a color reporting query contains only distinct colors of points in Q. In this paper we describe an O(N)-space data structure that answers one-dimensional color reporting queries in optimal O(k + 1) time, where k is the number of colors in the answer and N is the number of points in the data structure. Our result can be also dynamized and extended to the external memory model. More... »

PAGES

743-754

Book

TITLE

Algorithms – ESA 2013

ISBN

978-3-642-40449-8
978-3-642-40450-4

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-40450-4_63

DOI

http://dx.doi.org/10.1007/978-3-642-40450-4_63

DIMENSIONS

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


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/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Kansas", 
          "id": "https://www.grid.ac/institutes/grid.266515.3", 
          "name": [
            "The University of Kansas, USA"
          ], 
          "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"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Kansas", 
          "id": "https://www.grid.ac/institutes/grid.266515.3", 
          "name": [
            "The University of Kansas, 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/2213556.2213575", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003329814"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ipl.2005.04.008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003934120"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ipl.2005.04.008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003934120"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jcss.1998.1577", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014639269"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(05)80064-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017760034"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/380752.380842", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020167399"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jcss.2002.1822", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022063478"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-31155-0_26", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023334636", 
          "https://doi.org/10.1007/978-3-642-31155-0_26"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/316542.316548", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027318638"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jagm.1995.1038", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038591561"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/303976.304010", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043153209"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01683268", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053048814", 
          "https://doi.org/10.1007/bf01683268"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01683268", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053048814", 
          "https://doi.org/10.1007/bf01683268"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0214021", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841810"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0215051", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841913"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s009753970240481x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879369"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539797322425", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880184"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s021819599300004x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062960750"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "Color (or categorical) range reporting is a variant of the orthogonal range reporting problem in which every point in the input is assigned a color. While the answer to an orthogonal point reporting query contains all points in the query range Q, the answer to a color reporting query contains only distinct colors of points in Q. In this paper we describe an O(N)-space data structure that answers one-dimensional color reporting queries in optimal O(k\u2009+\u20091) time, where k is the number of colors in the answer and N is the number of points in the data structure. Our result can be also dynamized and extended to the external memory model.", 
    "editor": [
      {
        "familyName": "Bodlaender", 
        "givenName": "Hans L.", 
        "type": "Person"
      }, 
      {
        "familyName": "Italiano", 
        "givenName": "Giuseppe F.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-40450-4_63", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-40449-8", 
        "978-3-642-40450-4"
      ], 
      "name": "Algorithms \u2013 ESA 2013", 
      "type": "Book"
    }, 
    "name": "Optimal Color Range Reporting in One Dimension", 
    "pagination": "743-754", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-40450-4_63"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "cf99874a70ecf74b040ac66f13787b2b682521aa86eefae493ce30aa0eb08bf3"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1043582666"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-40450-4_63", 
      "https://app.dimensions.ai/details/publication/pub.1043582666"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T21:04", 
    "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_8690_00000270.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-40450-4_63"
  }
]
 

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-40450-4_63'

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-40450-4_63'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-40450-4_63'

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-40450-4_63'


 

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

127 TRIPLES      23 PREDICATES      43 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-40450-4_63 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Ncea0980e581b4f35b5f1a9a15cdc62b0
4 schema:citation sg:pub.10.1007/978-3-642-31155-0_26
5 sg:pub.10.1007/bf01683268
6 https://doi.org/10.1006/jagm.1995.1038
7 https://doi.org/10.1006/jcss.1998.1577
8 https://doi.org/10.1006/jcss.2002.1822
9 https://doi.org/10.1016/j.ipl.2005.04.008
10 https://doi.org/10.1016/s0022-0000(05)80064-9
11 https://doi.org/10.1137/0214021
12 https://doi.org/10.1137/0215051
13 https://doi.org/10.1137/s009753970240481x
14 https://doi.org/10.1137/s0097539797322425
15 https://doi.org/10.1142/s021819599300004x
16 https://doi.org/10.1145/2213556.2213575
17 https://doi.org/10.1145/303976.304010
18 https://doi.org/10.1145/316542.316548
19 https://doi.org/10.1145/380752.380842
20 schema:datePublished 2013
21 schema:datePublishedReg 2013-01-01
22 schema:description Color (or categorical) range reporting is a variant of the orthogonal range reporting problem in which every point in the input is assigned a color. While the answer to an orthogonal point reporting query contains all points in the query range Q, the answer to a color reporting query contains only distinct colors of points in Q. In this paper we describe an O(N)-space data structure that answers one-dimensional color reporting queries in optimal O(k + 1) time, where k is the number of colors in the answer and N is the number of points in the data structure. Our result can be also dynamized and extended to the external memory model.
23 schema:editor Ne548218ec0ee4b558581ad5c75e50b7f
24 schema:genre chapter
25 schema:inLanguage en
26 schema:isAccessibleForFree true
27 schema:isPartOf N90605f68146044ada526dc1631008a63
28 schema:name Optimal Color Range Reporting in One Dimension
29 schema:pagination 743-754
30 schema:productId N7cb1a16aad3a485fbe0cf3122c162a0e
31 Nd14f11910dce4fb29fb6c43a898a3953
32 Nd40004ab1e014ca0b43484a726e5f5c7
33 schema:publisher N75ed468f2a52485dba6ee9a6ce1435f2
34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043582666
35 https://doi.org/10.1007/978-3-642-40450-4_63
36 schema:sdDatePublished 2019-04-15T21:04
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher N941ab647be95472a851f96e3bd830628
39 schema:url http://link.springer.com/10.1007/978-3-642-40450-4_63
40 sgo:license sg:explorer/license/
41 sgo:sdDataset chapters
42 rdf:type schema:Chapter
43 N0617b396c481459480c75fb1d398f6b0 schema:familyName Bodlaender
44 schema:givenName Hans L.
45 rdf:type schema:Person
46 N208eb960a49f4cbd84927b4d82d554d0 schema:familyName Italiano
47 schema:givenName Giuseppe F.
48 rdf:type schema:Person
49 N3e7854f641dd434d85a072c398daf51f rdf:first sg:person.0613677314.28
50 rdf:rest rdf:nil
51 N62cfbcc7f57846eebc6fd10ff51eddaf rdf:first N208eb960a49f4cbd84927b4d82d554d0
52 rdf:rest rdf:nil
53 N75ed468f2a52485dba6ee9a6ce1435f2 schema:location Berlin, Heidelberg
54 schema:name Springer Berlin Heidelberg
55 rdf:type schema:Organisation
56 N7cb1a16aad3a485fbe0cf3122c162a0e schema:name doi
57 schema:value 10.1007/978-3-642-40450-4_63
58 rdf:type schema:PropertyValue
59 N90605f68146044ada526dc1631008a63 schema:isbn 978-3-642-40449-8
60 978-3-642-40450-4
61 schema:name Algorithms – ESA 2013
62 rdf:type schema:Book
63 N941ab647be95472a851f96e3bd830628 schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 Ncea0980e581b4f35b5f1a9a15cdc62b0 rdf:first sg:person.014556642366.63
66 rdf:rest N3e7854f641dd434d85a072c398daf51f
67 Nd14f11910dce4fb29fb6c43a898a3953 schema:name dimensions_id
68 schema:value pub.1043582666
69 rdf:type schema:PropertyValue
70 Nd40004ab1e014ca0b43484a726e5f5c7 schema:name readcube_id
71 schema:value cf99874a70ecf74b040ac66f13787b2b682521aa86eefae493ce30aa0eb08bf3
72 rdf:type schema:PropertyValue
73 Ne548218ec0ee4b558581ad5c75e50b7f rdf:first N0617b396c481459480c75fb1d398f6b0
74 rdf:rest N62cfbcc7f57846eebc6fd10ff51eddaf
75 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
76 schema:name Mathematical Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
79 schema:name Pure Mathematics
80 rdf:type schema:DefinedTerm
81 sg:person.014556642366.63 schema:affiliation https://www.grid.ac/institutes/grid.266515.3
82 schema:familyName Nekrich
83 schema:givenName Yakov
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63
85 rdf:type schema:Person
86 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.266515.3
87 schema:familyName Vitter
88 schema:givenName Jeffrey Scott
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
90 rdf:type schema:Person
91 sg:pub.10.1007/978-3-642-31155-0_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023334636
92 https://doi.org/10.1007/978-3-642-31155-0_26
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/bf01683268 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053048814
95 https://doi.org/10.1007/bf01683268
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1006/jagm.1995.1038 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038591561
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1006/jcss.1998.1577 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014639269
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1006/jcss.2002.1822 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022063478
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1016/j.ipl.2005.04.008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003934120
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1016/s0022-0000(05)80064-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017760034
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1137/0214021 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841810
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1137/0215051 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841913
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1137/s009753970240481x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879369
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1137/s0097539797322425 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880184
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1142/s021819599300004x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062960750
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1145/2213556.2213575 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003329814
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1145/303976.304010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043153209
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1145/316542.316548 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027318638
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1145/380752.380842 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020167399
124 rdf:type schema:CreativeWork
125 https://www.grid.ac/institutes/grid.266515.3 schema:alternateName University of Kansas
126 schema:name The University of Kansas, USA
127 rdf:type schema:Organization
 




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


...