A Tight Lower Bound for High Frequency Moment Estimation with Small Error View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Yi Li , David P. Woodruff

ABSTRACT

We show an Ω((n1 − 2/p logM)/ε2) bits of space lower bound for (1 + ε)-approximating the p-th frequency moment \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$F_p = \|x\|_p^p = \sum_{i=1}^n |x_i|^p$\end{document} of a vector x ∈ { − M, − M + 1, …, M}n with constant probability in the turnstile model for data streams, for any p > 2 and ε ≥ 1/n1/p (we require ε ≥ 1/n1/p since there is a trivial O(n logM) upper bound). This lower bound matches the space complexity of an upper bound of Ganguly for any ε < 1/logO(1)n, and is the first of any bound in the long sequence of work on estimating Fp to be shown to be optimal up to a constant factor for any setting of parameters. Moreover, our technique improves the dependence on ε in known lower bounds for cascaded moments, also known as mixed norms. We also continue the study of tight bounds on the dimension of linear sketches (drawn from some distribution) required for estimating Fp over the reals. We show a dimension lower bound of Ω(n1 − 2/p/ε2) for sketches providing a (1 + ε)-approximation to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\|x\|_p^p$\end{document} with constant probability, for any p > 2 and ε ≥ 1/n1/p. This is again optimal for ε < 1/logO(1)n. More... »

PAGES

623-638

Book

TITLE

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

ISBN

978-3-642-40327-9
978-3-642-40328-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-40328-6_43

DOI

http://dx.doi.org/10.1007/978-3-642-40328-6_43

DIMENSIONS

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


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/09", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Engineering", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0906", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Electrical and Electronic Engineering", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of EECS, University of Michigan, Ann Arbor, USA", 
          "id": "http://www.grid.ac/institutes/grid.214458.e", 
          "name": [
            "Department of EECS, University of Michigan, Ann Arbor, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "Yi", 
        "id": "sg:person.07361330656.72", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07361330656.72"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Almaden Research Center, USA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center, 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": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "We show an \u03a9((n1\u2009\u2212\u20092/p logM)/\u03b52) bits of space lower bound for (1\u2009+\u2009\u03b5)-approximating the p-th frequency moment \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$F_p = \\|x\\|_p^p = \\sum_{i=1}^n |x_i|^p$\\end{document} of a vector x\u2009\u2208\u2009{\u2009\u2212\u2009M,\u2009\u2212\u2009M\u2009+\u20091, \u2026, M}n with constant probability in the turnstile model for data streams, for any p\u2009>\u20092 and \u03b5\u2009\u2265\u20091/n1/p (we require \u03b5\u2009\u2265\u20091/n1/p since there is a trivial O(n logM) upper bound). This lower bound matches the space complexity of an upper bound of Ganguly for any \u03b5\u2009<\u20091/logO(1)n, and is the first of any bound in the long sequence of work on estimating Fp to be shown to be optimal up to a constant factor for any setting of parameters. Moreover, our technique improves the dependence on \u03b5 in known lower bounds for cascaded moments, also known as mixed norms. We also continue the study of tight bounds on the dimension of linear sketches (drawn from some distribution) required for estimating Fp over the reals. We show a dimension lower bound of \u03a9(n1\u2009\u2212\u20092/p/\u03b52) for sketches providing a (1\u2009+\u2009\u03b5)-approximation to \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\|x\\|_p^p$\\end{document} with constant probability, for any p\u2009>\u20092 and \u03b5\u2009\u2265\u20091/n1/p. This is again optimal for \u03b5\u2009<\u20091/logO(1)n.", 
    "editor": [
      {
        "familyName": "Raghavendra", 
        "givenName": "Prasad", 
        "type": "Person"
      }, 
      {
        "familyName": "Raskhodnikova", 
        "givenName": "Sofya", 
        "type": "Person"
      }, 
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Rolim", 
        "givenName": "Jos\u00e9 D. P.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-40328-6_43", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-40327-9", 
        "978-3-642-40328-6"
      ], 
      "name": "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques", 
      "type": "Book"
    }, 
    "keywords": [
      "constant probability", 
      "linear sketches", 
      "lower bounds", 
      "tight bounds", 
      "vector x", 
      "turnstile model", 
      "moment estimation", 
      "setting of parameters", 
      "frequency moments", 
      "space complexity", 
      "constant factor", 
      "mixed norm", 
      "small errors", 
      "bounds", 
      "bits of space", 
      "moment", 
      "approximation", 
      "probability", 
      "dimensions", 
      "long sequences", 
      "estimation", 
      "space", 
      "data streams", 
      "error", 
      "complexity", 
      "parameters", 
      "Real", 
      "dependence", 
      "model", 
      "Ganguly", 
      "norms", 
      "FP", 
      "sketch", 
      "technique", 
      "match", 
      "bits", 
      "work", 
      "sequence", 
      "streams", 
      "setting", 
      "study", 
      "factors"
    ], 
    "name": "A Tight Lower Bound for High Frequency Moment Estimation with Small Error", 
    "pagination": "623-638", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050815906"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-40328-6_43"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-40328-6_43", 
      "https://app.dimensions.ai/details/publication/pub.1050815906"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:52", 
    "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_379.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-40328-6_43"
  }
]
 

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-40328-6_43'

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-40328-6_43'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-40328-6_43'

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-40328-6_43'


 

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

126 TRIPLES      22 PREDICATES      67 URIs      60 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-40328-6_43 schema:about anzsrc-for:09
2 anzsrc-for:0906
3 schema:author N557bdc87c7004f6c8e641ed510606747
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description We show an Ω((n1 − 2/p logM)/ε2) bits of space lower bound for (1 + ε)-approximating the p-th frequency moment \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$F_p = \|x\|_p^p = \sum_{i=1}^n |x_i|^p$\end{document} of a vector x ∈ { − M, − M + 1, …, M}n with constant probability in the turnstile model for data streams, for any p > 2 and ε ≥ 1/n1/p (we require ε ≥ 1/n1/p since there is a trivial O(n logM) upper bound). This lower bound matches the space complexity of an upper bound of Ganguly for any ε < 1/logO(1)n, and is the first of any bound in the long sequence of work on estimating Fp to be shown to be optimal up to a constant factor for any setting of parameters. Moreover, our technique improves the dependence on ε in known lower bounds for cascaded moments, also known as mixed norms. We also continue the study of tight bounds on the dimension of linear sketches (drawn from some distribution) required for estimating Fp over the reals. We show a dimension lower bound of Ω(n1 − 2/p/ε2) for sketches providing a (1 + ε)-approximation to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\|x\|_p^p$\end{document} with constant probability, for any p > 2 and ε ≥ 1/n1/p. This is again optimal for ε < 1/logO(1)n.
7 schema:editor N2d573bc15e5f4a1ea8d1c505fff24fe3
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N85be212ac36c4975a562ecc65cb73c50
11 schema:keywords FP
12 Ganguly
13 Real
14 approximation
15 bits
16 bits of space
17 bounds
18 complexity
19 constant factor
20 constant probability
21 data streams
22 dependence
23 dimensions
24 error
25 estimation
26 factors
27 frequency moments
28 linear sketches
29 long sequences
30 lower bounds
31 match
32 mixed norm
33 model
34 moment
35 moment estimation
36 norms
37 parameters
38 probability
39 sequence
40 setting
41 setting of parameters
42 sketch
43 small errors
44 space
45 space complexity
46 streams
47 study
48 technique
49 tight bounds
50 turnstile model
51 vector x
52 work
53 schema:name A Tight Lower Bound for High Frequency Moment Estimation with Small Error
54 schema:pagination 623-638
55 schema:productId N044afecd361c4b7e9d792cad6a4d8003
56 Na1212a603d9e4fbaa13ce60d2e8e1fb7
57 schema:publisher N97c639acd23548f6b7e99de5282991ab
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050815906
59 https://doi.org/10.1007/978-3-642-40328-6_43
60 schema:sdDatePublished 2022-12-01T06:52
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher N292095b8b2714c369e246f3888d3afed
63 schema:url https://doi.org/10.1007/978-3-642-40328-6_43
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N044afecd361c4b7e9d792cad6a4d8003 schema:name doi
68 schema:value 10.1007/978-3-642-40328-6_43
69 rdf:type schema:PropertyValue
70 N292095b8b2714c369e246f3888d3afed schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N2d573bc15e5f4a1ea8d1c505fff24fe3 rdf:first N6c01f034266548a6a380273d94f1662b
73 rdf:rest Ne7294f944ecc49dd8acbdfb2966d677a
74 N39590c994c2c4e8c926635201c9e7a2f schema:familyName Jansen
75 schema:givenName Klaus
76 rdf:type schema:Person
77 N557bdc87c7004f6c8e641ed510606747 rdf:first sg:person.07361330656.72
78 rdf:rest N87ba7ed876a940deb6a06ddf03e1bd01
79 N6c01f034266548a6a380273d94f1662b schema:familyName Raghavendra
80 schema:givenName Prasad
81 rdf:type schema:Person
82 N7342fd7b781243a89daaafb980ee12e2 rdf:first Ncf52677170914bf591597afcd62c53a0
83 rdf:rest rdf:nil
84 N85be212ac36c4975a562ecc65cb73c50 schema:isbn 978-3-642-40327-9
85 978-3-642-40328-6
86 schema:name Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
87 rdf:type schema:Book
88 N87ba7ed876a940deb6a06ddf03e1bd01 rdf:first sg:person.012727410605.86
89 rdf:rest rdf:nil
90 N97c639acd23548f6b7e99de5282991ab schema:name Springer Nature
91 rdf:type schema:Organisation
92 Na1212a603d9e4fbaa13ce60d2e8e1fb7 schema:name dimensions_id
93 schema:value pub.1050815906
94 rdf:type schema:PropertyValue
95 Ncf52677170914bf591597afcd62c53a0 schema:familyName Rolim
96 schema:givenName José D. P.
97 rdf:type schema:Person
98 Ne5d4343890e74975a157557f23a9a914 rdf:first N39590c994c2c4e8c926635201c9e7a2f
99 rdf:rest N7342fd7b781243a89daaafb980ee12e2
100 Ne7294f944ecc49dd8acbdfb2966d677a rdf:first Nedd73de76a7c4e73a2378b7ed69d246d
101 rdf:rest Ne5d4343890e74975a157557f23a9a914
102 Nedd73de76a7c4e73a2378b7ed69d246d schema:familyName Raskhodnikova
103 schema:givenName Sofya
104 rdf:type schema:Person
105 anzsrc-for:09 schema:inDefinedTermSet anzsrc-for:
106 schema:name Engineering
107 rdf:type schema:DefinedTerm
108 anzsrc-for:0906 schema:inDefinedTermSet anzsrc-for:
109 schema:name Electrical and Electronic Engineering
110 rdf:type schema:DefinedTerm
111 sg:person.012727410605.86 schema:affiliation grid-institutes:grid.481551.c
112 schema:familyName Woodruff
113 schema:givenName David P.
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
115 rdf:type schema:Person
116 sg:person.07361330656.72 schema:affiliation grid-institutes:grid.214458.e
117 schema:familyName Li
118 schema:givenName Yi
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07361330656.72
120 rdf:type schema:Person
121 grid-institutes:grid.214458.e schema:alternateName Department of EECS, University of Michigan, Ann Arbor, USA
122 schema:name Department of EECS, University of Michigan, Ann Arbor, USA
123 rdf:type schema:Organization
124 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center, USA
125 schema:name IBM Almaden Research Center, USA
126 rdf:type schema:Organization
 




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


...