We consider the problem of maintaining a fixed number k of items observed over a data stream, so as to optimize the maximum value over a fixed number n of recent observations. Unlike previous approaches, we use the competitive analysis framework and compare the performance of the online streaming algorithm against an optimal adversary that knows the entire sequence in advance. We consider the problem of maximizing the aggregate max, i.e., the sum of the values of the largest items in the algorithm's memory over the entire sequence. For this problem, we prove an asymptotically tight competitive ratio, achieved by a simple heuristic, called partition-greedy, that performs stream updates efficiently and has almost optimal performance. In contrast, we prove that the problem of maximizing, for every time t, the value maintained by the online algorithm in memory, is considerably harder: in particular, we show a tight competitive ratio that depends on the maximum value of the stream. We further prove negative results for the closely related problem of maintaining the aggregate minimum and for the generalized version of the aggregate max problem in which every item comes with an individual window. © 2009 Springer Berlin Heidelberg.

Competitive analysis of aggregate max in windowed streaming / Becchetti, Luca; Elias, Koutsoupias. - 5555 LNCS:PART 1(2009), pp. 156-170. (Intervento presentato al convegno 36th International Colloquium on Automata, Languages and Programming, ICALP 2009 tenutosi a Rhodes; Greece nel 5 July 2009 through 12 July 2009) [10.1007/978-3-642-02927-1_15].

Competitive analysis of aggregate max in windowed streaming

BECCHETTI, Luca;
2009

Abstract

We consider the problem of maintaining a fixed number k of items observed over a data stream, so as to optimize the maximum value over a fixed number n of recent observations. Unlike previous approaches, we use the competitive analysis framework and compare the performance of the online streaming algorithm against an optimal adversary that knows the entire sequence in advance. We consider the problem of maximizing the aggregate max, i.e., the sum of the values of the largest items in the algorithm's memory over the entire sequence. For this problem, we prove an asymptotically tight competitive ratio, achieved by a simple heuristic, called partition-greedy, that performs stream updates efficiently and has almost optimal performance. In contrast, we prove that the problem of maximizing, for every time t, the value maintained by the online algorithm in memory, is considerably harder: in particular, we show a tight competitive ratio that depends on the maximum value of the stream. We further prove negative results for the closely related problem of maintaining the aggregate minimum and for the generalized version of the aggregate max problem in which every item comes with an individual window. © 2009 Springer Berlin Heidelberg.
2009
36th International Colloquium on Automata, Languages and Programming, ICALP 2009
Competitive analysis; Competitive ratio; Data stream
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Competitive analysis of aggregate max in windowed streaming / Becchetti, Luca; Elias, Koutsoupias. - 5555 LNCS:PART 1(2009), pp. 156-170. (Intervento presentato al convegno 36th International Colloquium on Automata, Languages and Programming, ICALP 2009 tenutosi a Rhodes; Greece nel 5 July 2009 through 12 July 2009) [10.1007/978-3-642-02927-1_15].
File allegati a questo prodotto
File Dimensione Formato  
VE_2009_11573-55129.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 471.33 kB
Formato Adobe PDF
471.33 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/55129
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 12
social impact