Streaming Algorithms with One-Sided Estimation View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Joshua Brody , David P. Woodruff

ABSTRACT

We study the space complexity of randomized streaming algorithms that provide one-sided approximation guarantees; e.g., the algorithm always returns an overestimate of the function being computed, and with high probability, the estimate is not too far from the true answer. We also study algorithms which always provide underestimates.We also give lower bounds for several one-sided estimators that match the deterministic space complexity, thus showing that to get a space-efficient solution, two-sided approximations are sometimes necessary. For some of these problems, including estimating the longest increasing sequence in a stream, and estimating the Earth Mover Distance, these are the first lower bounds for randomized algorithms of any kind.We show that for several problems, including estimating the radius of the Minimum Enclosing Ball (MEB), one-sided estimation is possible. We provide a natural function for which the space for one-sided estimation is asymptotically less than the space required for deterministic algorithms, but more than what is required for general randomized algorithms.What if an algorithm has a one-sided approximation from both sides? In this case, we show the problem has what we call a Las Vegas streaming algorithm. We show that even for two-pass algorithms, a quadratic improvement in space is possible and give a natural problem, counting non-isolated vertices in a graph, which achieves this separation. More... »

PAGES

436-447

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-642-22934-3
978-3-642-22935-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22935-0_37

DOI

http://dx.doi.org/10.1007/978-3-642-22935-0_37

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "IIIS, Tsinghua University, China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "IIIS, Tsinghua University, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Brody", 
        "givenName": "Joshua", 
        "id": "sg:person.015653755577.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015653755577.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Research-Almaden, USA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Research-Almaden, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Woodruff", 
        "givenName": "David P.", 
        "id": "sg:person.012727410605.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "We study the space complexity of randomized streaming algorithms that provide one-sided approximation guarantees; e.g., the algorithm always returns an overestimate of the function being computed, and with high probability, the estimate is not too far from the true answer. We also study algorithms which always provide underestimates.We also give lower bounds for several one-sided estimators that match the deterministic space complexity, thus showing that to get a space-efficient solution, two-sided approximations are sometimes necessary. For some of these problems, including estimating the longest increasing sequence in a stream, and estimating the Earth Mover Distance, these are the first lower bounds for randomized algorithms of any kind.We show that for several problems, including estimating the radius of the Minimum Enclosing Ball (MEB), one-sided estimation is possible. We provide a natural function for which the space for one-sided estimation is asymptotically less than the space required for deterministic algorithms, but more than what is required for general randomized algorithms.What if an algorithm has a one-sided approximation from both sides? In this case, we show the problem has what we call a Las Vegas streaming algorithm. We show that even for two-pass algorithms, a quadratic improvement in space is possible and give a natural problem, counting non-isolated vertices in a graph, which achieves this separation.", 
    "editor": [
      {
        "familyName": "Goldberg", 
        "givenName": "Leslie Ann", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Ravi", 
        "givenName": "R.", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-22935-0_37", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-22934-3", 
        "978-3-642-22935-0"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "Minimum Enclosing Balls", 
      "lower bounds", 
      "two-sided approximations", 
      "space complexity", 
      "one-sided approximation", 
      "first lower bounds", 
      "non-isolated vertices", 
      "deterministic space complexity", 
      "approximation guarantee", 
      "natural problem", 
      "randomized algorithm", 
      "deterministic algorithm", 
      "two-pass algorithm", 
      "quadratic improvement", 
      "space-efficient solution", 
      "approximation", 
      "bounds", 
      "algorithm", 
      "estimation", 
      "space", 
      "Earth Mover's Distance", 
      "true answer", 
      "problem", 
      "estimator", 
      "high probability", 
      "complexity", 
      "vertices", 
      "graph", 
      "probability", 
      "guarantees", 
      "solution", 
      "function", 
      "estimates", 
      "radius", 
      "ball", 
      "distance", 
      "Vegas", 
      "kind", 
      "cases", 
      "overestimate", 
      "answers", 
      "sequence", 
      "underestimate", 
      "Las Vegas", 
      "streams", 
      "side", 
      "improvement", 
      "separation", 
      "natural function"
    ], 
    "name": "Streaming Algorithms with One-Sided Estimation", 
    "pagination": "436-447", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1034813492"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22935-0_37"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22935-0_37", 
      "https://app.dimensions.ai/details/publication/pub.1034813492"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:18", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_42.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-22935-0_37"
  }
]
 

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-22935-0_37'

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-22935-0_37'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22935-0_37'

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-22935-0_37'


 

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

133 TRIPLES      22 PREDICATES      74 URIs      67 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22935-0_37 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N112b226a07cc443caa2d980d78d75c72
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description We study the space complexity of randomized streaming algorithms that provide one-sided approximation guarantees; e.g., the algorithm always returns an overestimate of the function being computed, and with high probability, the estimate is not too far from the true answer. We also study algorithms which always provide underestimates.We also give lower bounds for several one-sided estimators that match the deterministic space complexity, thus showing that to get a space-efficient solution, two-sided approximations are sometimes necessary. For some of these problems, including estimating the longest increasing sequence in a stream, and estimating the Earth Mover Distance, these are the first lower bounds for randomized algorithms of any kind.We show that for several problems, including estimating the radius of the Minimum Enclosing Ball (MEB), one-sided estimation is possible. We provide a natural function for which the space for one-sided estimation is asymptotically less than the space required for deterministic algorithms, but more than what is required for general randomized algorithms.What if an algorithm has a one-sided approximation from both sides? In this case, we show the problem has what we call a Las Vegas streaming algorithm. We show that even for two-pass algorithms, a quadratic improvement in space is possible and give a natural problem, counting non-isolated vertices in a graph, which achieves this separation.
7 schema:editor N62f287523c5e48109b333f9a5367b4e8
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N75cff798fe2449dea01e376e52537ad7
11 schema:keywords Earth Mover's Distance
12 Las Vegas
13 Minimum Enclosing Balls
14 Vegas
15 algorithm
16 answers
17 approximation
18 approximation guarantee
19 ball
20 bounds
21 cases
22 complexity
23 deterministic algorithm
24 deterministic space complexity
25 distance
26 estimates
27 estimation
28 estimator
29 first lower bounds
30 function
31 graph
32 guarantees
33 high probability
34 improvement
35 kind
36 lower bounds
37 natural function
38 natural problem
39 non-isolated vertices
40 one-sided approximation
41 overestimate
42 probability
43 problem
44 quadratic improvement
45 radius
46 randomized algorithm
47 separation
48 sequence
49 side
50 solution
51 space
52 space complexity
53 space-efficient solution
54 streams
55 true answer
56 two-pass algorithm
57 two-sided approximations
58 underestimate
59 vertices
60 schema:name Streaming Algorithms with One-Sided Estimation
61 schema:pagination 436-447
62 schema:productId N670f5007f2d84cb7a57df2e76c7b18cc
63 Nf49f198c7e0d42799161a716a6d655ff
64 schema:publisher Nd75ee1f6acca41daa047962548982861
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034813492
66 https://doi.org/10.1007/978-3-642-22935-0_37
67 schema:sdDatePublished 2022-11-24T21:18
68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
69 schema:sdPublisher N6d0f7c5b57804f539a13d79da85f89fe
70 schema:url https://doi.org/10.1007/978-3-642-22935-0_37
71 sgo:license sg:explorer/license/
72 sgo:sdDataset chapters
73 rdf:type schema:Chapter
74 N112b226a07cc443caa2d980d78d75c72 rdf:first sg:person.015653755577.76
75 rdf:rest Ne5b08de348924c369f9b4798d608210d
76 N322e65d22f6343b7bcd4039312d7f6c2 schema:familyName Ravi
77 schema:givenName R.
78 rdf:type schema:Person
79 N3358afc93369472fa758f1f3a0c81f4b rdf:first N88ceda4b72154900949f2420a52107cc
80 rdf:rest rdf:nil
81 N62f287523c5e48109b333f9a5367b4e8 rdf:first Ne2f9e14b7b06457c947a3a91fe117369
82 rdf:rest Nb42ff516ad9241bfacfc5b854d4a073a
83 N670f5007f2d84cb7a57df2e76c7b18cc schema:name dimensions_id
84 schema:value pub.1034813492
85 rdf:type schema:PropertyValue
86 N6d0f7c5b57804f539a13d79da85f89fe schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 N75cff798fe2449dea01e376e52537ad7 schema:isbn 978-3-642-22934-3
89 978-3-642-22935-0
90 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
91 rdf:type schema:Book
92 N804763842161490b8b2d8a084f2a4e49 rdf:first N322e65d22f6343b7bcd4039312d7f6c2
93 rdf:rest N3358afc93369472fa758f1f3a0c81f4b
94 N8320bb9bc86f43deb75744a725d02a83 schema:familyName Jansen
95 schema:givenName Klaus
96 rdf:type schema:Person
97 N88ceda4b72154900949f2420a52107cc schema:familyName Rolim
98 schema:givenName José D. P.
99 rdf:type schema:Person
100 Nb42ff516ad9241bfacfc5b854d4a073a rdf:first N8320bb9bc86f43deb75744a725d02a83
101 rdf:rest N804763842161490b8b2d8a084f2a4e49
102 Nd75ee1f6acca41daa047962548982861 schema:name Springer Nature
103 rdf:type schema:Organisation
104 Ne2f9e14b7b06457c947a3a91fe117369 schema:familyName Goldberg
105 schema:givenName Leslie Ann
106 rdf:type schema:Person
107 Ne5b08de348924c369f9b4798d608210d rdf:first sg:person.012727410605.86
108 rdf:rest rdf:nil
109 Nf49f198c7e0d42799161a716a6d655ff schema:name doi
110 schema:value 10.1007/978-3-642-22935-0_37
111 rdf:type schema:PropertyValue
112 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
113 schema:name Information and Computing Sciences
114 rdf:type schema:DefinedTerm
115 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
116 schema:name Computation Theory and Mathematics
117 rdf:type schema:DefinedTerm
118 sg:person.012727410605.86 schema:affiliation grid-institutes:grid.481551.c
119 schema:familyName Woodruff
120 schema:givenName David P.
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
122 rdf:type schema:Person
123 sg:person.015653755577.76 schema:affiliation grid-institutes:grid.12527.33
124 schema:familyName Brody
125 schema:givenName Joshua
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015653755577.76
127 rdf:type schema:Person
128 grid-institutes:grid.12527.33 schema:alternateName IIIS, Tsinghua University, China
129 schema:name IIIS, Tsinghua University, China
130 rdf:type schema:Organization
131 grid-institutes:grid.481551.c schema:alternateName IBM Research-Almaden, USA
132 schema:name IBM Research-Almaden, USA
133 rdf:type schema:Organization
 




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


...