Tight lower bound for linear sketches of moments

Alexandr Andoni; Huy L. Nguyên; Yury Polyanskiy; Yihong Wu

doi:10.1007/978-3-642-39206-1_3

Tight lower bound for linear sketches of moments

Alexandr Andoni, Huy L. Nguyên, Yury Polyanskiy, Yihong Wu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The problem of estimating frequency moments of a data stream has attracted a lot of attention since the onset of streaming algorithms [AMS99]. While the space complexity for approximately computing the p^th moment, for p ∈ (0,2] has been settled [KNW10], for p > 2 the exact complexity remains open. For p > 2 the current best algorithm uses O(n^1-2/p log n) words of space [AKO11,BO10], whereas the lower bound is of Ω(n ^1-2/p) [BJKS04]. In this paper, we show a tight lower bound of Ω(n^1-2/p log n) words for the class of algorithms based on linear sketches, which store only a sketch Ax of input vector x and some (possibly randomized) matrix A. We note that all known algorithms for this problem are linear sketches.

Original language	English (US)
Title of host publication	Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings
Pages	25-32
Number of pages	8
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-39206-1_3
State	Published - 2013
Externally published	Yes
Event	40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 - Riga, Latvia Duration: Jul 8 2013 → Jul 12 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	7965 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	40th International Colloquium on Automata, Languages, and Programming, ICALP 2013
Country/Territory	Latvia
City	Riga
Period	7/8/13 → 7/12/13

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Online availability

10.1007/978-3-642-39206-1_3

Library availability

Discover UIUC Full Text

Cite this

Andoni, A., Nguyên, H. L., Polyanskiy, Y., & Wu, Y. (2013). Tight lower bound for linear sketches of moments. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings (PART 1 ed., pp. 25-32). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7965 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-39206-1_3

Tight lower bound for linear sketches of moments. / Andoni, Alexandr; Nguyên, Huy L.; Polyanskiy, Yury et al.
Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1. ed. 2013. p. 25-32 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7965 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Andoni, A, Nguyên, HL, Polyanskiy, Y & Wu, Y 2013, Tight lower bound for linear sketches of moments. in Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 7965 LNCS, pp. 25-32, 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013, Riga, Latvia, 7/8/13. https://doi.org/10.1007/978-3-642-39206-1_3

Andoni A, Nguyên HL, Polyanskiy Y, Wu Y. Tight lower bound for linear sketches of moments. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1 ed. 2013. p. 25-32. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-39206-1_3

Andoni, Alexandr ; Nguyên, Huy L. ; Polyanskiy, Yury et al. / Tight lower bound for linear sketches of moments. Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings. PART 1. ed. 2013. pp. 25-32 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{23fda2761f0d46d98b31a16c7399369e,

title = "Tight lower bound for linear sketches of moments",

abstract = "The problem of estimating frequency moments of a data stream has attracted a lot of attention since the onset of streaming algorithms [AMS99]. While the space complexity for approximately computing the pth moment, for p ∈ (0,2] has been settled [KNW10], for p > 2 the exact complexity remains open. For p > 2 the current best algorithm uses O(n1-2/p log n) words of space [AKO11,BO10], whereas the lower bound is of Ω(n 1-2/p) [BJKS04]. In this paper, we show a tight lower bound of Ω(n1-2/p log n) words for the class of algorithms based on linear sketches, which store only a sketch Ax of input vector x and some (possibly randomized) matrix A. We note that all known algorithms for this problem are linear sketches.",

author = "Alexandr Andoni and Nguy{\^e}n, {Huy L.} and Yury Polyanskiy and Yihong Wu",

year = "2013",

doi = "10.1007/978-3-642-39206-1_3",

language = "English (US)",

isbn = "9783642392054",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "25--32",

booktitle = "Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings",

edition = "PART 1",

note = "40th International Colloquium on Automata, Languages, and Programming, ICALP 2013 ; Conference date: 08-07-2013 Through 12-07-2013",

}

TY - GEN

T1 - Tight lower bound for linear sketches of moments

AU - Andoni, Alexandr

AU - Nguyên, Huy L.

AU - Polyanskiy, Yury

AU - Wu, Yihong

PY - 2013

Y1 - 2013

N2 - The problem of estimating frequency moments of a data stream has attracted a lot of attention since the onset of streaming algorithms [AMS99]. While the space complexity for approximately computing the pth moment, for p ∈ (0,2] has been settled [KNW10], for p > 2 the exact complexity remains open. For p > 2 the current best algorithm uses O(n1-2/p log n) words of space [AKO11,BO10], whereas the lower bound is of Ω(n 1-2/p) [BJKS04]. In this paper, we show a tight lower bound of Ω(n1-2/p log n) words for the class of algorithms based on linear sketches, which store only a sketch Ax of input vector x and some (possibly randomized) matrix A. We note that all known algorithms for this problem are linear sketches.

AB - The problem of estimating frequency moments of a data stream has attracted a lot of attention since the onset of streaming algorithms [AMS99]. While the space complexity for approximately computing the pth moment, for p ∈ (0,2] has been settled [KNW10], for p > 2 the exact complexity remains open. For p > 2 the current best algorithm uses O(n1-2/p log n) words of space [AKO11,BO10], whereas the lower bound is of Ω(n 1-2/p) [BJKS04]. In this paper, we show a tight lower bound of Ω(n1-2/p log n) words for the class of algorithms based on linear sketches, which store only a sketch Ax of input vector x and some (possibly randomized) matrix A. We note that all known algorithms for this problem are linear sketches.

UR - http://www.scopus.com/inward/record.url?scp=84880267390&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880267390&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39206-1_3

DO - 10.1007/978-3-642-39206-1_3

M3 - Conference contribution

AN - SCOPUS:84880267390

SN - 9783642392054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 25

EP - 32

BT - Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings

T2 - 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

Y2 - 8 July 2013 through 12 July 2013

ER -

Tight lower bound for linear sketches of moments

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this