The Frequent Items Problem in Online Streaming under Various Performance Measures

Joan Boyar; Kim Skak Larsen; Abyayananda Maiti

doi:10.1007/978-3-642-40164-0_9

The Frequent Items Problem in Online Streaming under Various Performance Measures

Joan Boyar, Kim Skak Larsen, Abyayananda Maiti

Institut for Matematik og Datalogi

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstract

In this paper, we strengthen the competitive analysis results obtained for a fundamental online streaming problem, the Frequent Items Problem. Additionally, we contribute with a more detailed analysis of this problem, using alternative performance measures, supplementing the insight gained from competitive analysis. The results also contribute to the general study of performance measures for online algorithms. It has long been known that competitive analysis suffers from drawbacks in certain situations, and many alternative measures have been proposed. However, more systematic comparative studies of performance measures have been initiated recently, and we continue this work, using competitive analysis, relative interval analysis, and relative worst order analysis on the Frequent Items Problem.

Originalsprog	Engelsk
Titel	Fundamentals of Computation Theory : 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings
Redaktører	Leszek Gąsieniec, Frank Wolter
Vol/bind	8
Forlag	Springer
Publikationsdato	2013
Sider	60-71
ISBN (Trykt)	978-3-642-40163-3
ISBN (Elektronisk)	978-3-642-40164-0
DOI	https://doi.org/10.1007/978-3-642-40164-0_9
Status	Udgivet - 2013
Begivenhed	19th International Symposium on Fundamentals of Computation Theory - Crowne Plaza Hotel, Liverpool, Liverpool, Storbritannien Varighed: 19. aug. 2013 → 21. aug. 2013 Konferencens nummer: 19

Konference

Konference	19th International Symposium on Fundamentals of Computation Theory
Nummer	19
Lokation	Crowne Plaza Hotel, Liverpool
Land/Område	Storbritannien
By	Liverpool
Periode	19/08/2013 → 21/08/2013

Navn	Lecture Notes in Computer Science
Vol/bind	8070
ISSN	0302-9743

Emneord

online algorithms
frequent items problem
performance measures

Dokumenter og links

10.1007/978-3-642-40164-0_9

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

1 Organisering af eller deltagelse i workshop, kursus, seminar eller lignende

19th International Symposium on Fundamentals of Computation Theory
Boyar, J. (Deltager)
19. aug. 2013 → 21. aug. 2013
Aktivitet: Deltagelse i faglig begivenhed › Organisering af eller deltagelse i workshop, kursus, seminar eller lignende

Citationsformater

Boyar, Joan ; Larsen, Kim Skak ; Maiti, Abyayananda. / The Frequent Items Problem in Online Streaming under Various Performance Measures. Fundamentals of Computation Theory: 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings. red. / Leszek Gąsieniec ; Frank Wolter. Bind 8 Springer, 2013. s. 60-71 (Lecture Notes in Computer Science, Bind 8070).

@inproceedings{9b2c174534fc42408f06dcc3a58fbb65,

title = "The Frequent Items Problem in Online Streaming under Various Performance Measures",

abstract = "In this paper, we strengthen the competitive analysis results obtained for a fundamental online streaming problem, the Frequent Items Problem. Additionally, we contribute with a more detailed analysis of this problem, using alternative performance measures, supplementing the insight gained from competitive analysis. The results also contribute to the general study of performance measures for online algorithms. It has long been known that competitive analysis suffers from drawbacks in certain situations, and many alternative measures have been proposed. However, more systematic comparative studies of performance measures have been initiated recently, and we continue this work, using competitive analysis, relative interval analysis, and relative worst order analysis on the Frequent Items Problem.",

keywords = "online algorithms, frequent items problem, performance measures",

author = "Joan Boyar and Larsen, {Kim Skak} and Abyayananda Maiti",

year = "2013",

doi = "10.1007/978-3-642-40164-0_9",

language = "English",

isbn = "978-3-642-40163-3",

volume = "8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "60--71",

editor = "Leszek G{\c a}sieniec and { Wolter}, Frank",

booktitle = "Fundamentals of Computation Theory",

address = "Germany",

note = "19th International Symposium on Fundamentals of Computation Theory ; Conference date: 19-08-2013 Through 21-08-2013",

}

Boyar, J , Larsen, KS & Maiti, A 2013, The Frequent Items Problem in Online Streaming under Various Performance Measures. i L Gąsieniec & F Wolter (red), Fundamentals of Computation Theory: 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings. bind 8, Springer, Lecture Notes in Computer Science, bind 8070, s. 60-71, 19th International Symposium on Fundamentals of Computation Theory, Liverpool, Storbritannien, 19/08/2013. https://doi.org/10.1007/978-3-642-40164-0_9

The Frequent Items Problem in Online Streaming under Various Performance Measures. / Boyar, Joan ; Larsen, Kim Skak; Maiti, Abyayananda.
Fundamentals of Computation Theory: 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings. red. / Leszek Gąsieniec; Frank Wolter. Bind 8 Springer, 2013. s. 60-71 (Lecture Notes in Computer Science, Bind 8070).

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - The Frequent Items Problem in Online Streaming under Various Performance Measures

AU - Boyar, Joan

AU - Larsen, Kim Skak

AU - Maiti, Abyayananda

N1 - Conference code: 19

PY - 2013

Y1 - 2013

N2 - In this paper, we strengthen the competitive analysis results obtained for a fundamental online streaming problem, the Frequent Items Problem. Additionally, we contribute with a more detailed analysis of this problem, using alternative performance measures, supplementing the insight gained from competitive analysis. The results also contribute to the general study of performance measures for online algorithms. It has long been known that competitive analysis suffers from drawbacks in certain situations, and many alternative measures have been proposed. However, more systematic comparative studies of performance measures have been initiated recently, and we continue this work, using competitive analysis, relative interval analysis, and relative worst order analysis on the Frequent Items Problem.

AB - In this paper, we strengthen the competitive analysis results obtained for a fundamental online streaming problem, the Frequent Items Problem. Additionally, we contribute with a more detailed analysis of this problem, using alternative performance measures, supplementing the insight gained from competitive analysis. The results also contribute to the general study of performance measures for online algorithms. It has long been known that competitive analysis suffers from drawbacks in certain situations, and many alternative measures have been proposed. However, more systematic comparative studies of performance measures have been initiated recently, and we continue this work, using competitive analysis, relative interval analysis, and relative worst order analysis on the Frequent Items Problem.

KW - online algorithms

KW - frequent items problem

KW - performance measures

U2 - 10.1007/978-3-642-40164-0_9

DO - 10.1007/978-3-642-40164-0_9

M3 - Article in proceedings

SN - 978-3-642-40163-3

VL - 8

T3 - Lecture Notes in Computer Science

SP - 60

EP - 71

BT - Fundamentals of Computation Theory

A2 - Gąsieniec, Leszek

A2 - Wolter, Frank

PB - Springer

T2 - 19th International Symposium on Fundamentals of Computation Theory

Y2 - 19 August 2013 through 21 August 2013

ER -

Boyar J , Larsen KS, Maiti A. The Frequent Items Problem in Online Streaming under Various Performance Measures. I Gąsieniec L, Wolter F, red., Fundamentals of Computation Theory: 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings. Bind 8. Springer. 2013. s. 60-71. (Lecture Notes in Computer Science, Bind 8070). doi: 10.1007/978-3-642-40164-0_9

The Frequent Items Problem in Online Streaming under Various Performance Measures

Abstract

Konference

Emneord

Dokumenter og links

SDU link

Fingeraftryk

Relaterede aktiviteter

19th International Symposium on Fundamentals of Computation Theory

Citationsformater