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

Department of Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › 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.

Original language	English
Title of host publication	Fundamentals of Computation Theory : 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings
Editors	Leszek Gąsieniec, Frank Wolter
Volume	8
Publisher	Springer
Publication date	2013
Pages	60-71
ISBN (Print)	978-3-642-40163-3
ISBN (Electronic)	978-3-642-40164-0
DOIs	https://doi.org/10.1007/978-3-642-40164-0_9
Publication status	Published - 2013
Event	19th International Symposium on Fundamentals of Computation Theory - Crowne Plaza Hotel, Liverpool, Liverpool, United Kingdom Duration: 19. Aug 2013 → 21. Aug 2013 Conference number: 19

Conference

Conference	19th International Symposium on Fundamentals of Computation Theory
Number	19
Location	Crowne Plaza Hotel, Liverpool
Country/Territory	United Kingdom
City	Liverpool
Period	19/08/2013 → 21/08/2013

Series	Lecture Notes in Computer Science
Volume	8070
ISSN	0302-9743

Documents & Links

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

19th International Symposium on Fundamentals of Computation Theory
Joan Boyar (Participant)
19. Aug 2013 → 21. Aug 2013
Activity: Attending an event › Organisation or participation in workshops, courses or seminars

Cite this

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

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. editor / Leszek Gąsieniec ; Frank Wolter. Vol. 8 Springer, 2013. pp. 60-71 (Lecture Notes in Computer Science, Vol. 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. in L Gąsieniec & F Wolter (eds), Fundamentals of Computation Theory: 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings. vol. 8, Springer, Lecture Notes in Computer Science, vol. 8070, pp. 60-71, 19th International Symposium on Fundamentals of Computation Theory, Liverpool, United Kingdom, 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. ed. / Leszek Gąsieniec; Frank Wolter. Vol. 8 Springer, 2013. p. 60-71 (Lecture Notes in Computer Science, Vol. 8070).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › 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. In Gąsieniec L, Wolter F, editors, Fundamentals of Computation Theory: 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings. Vol. 8. Springer. 2013. p. 60-71. (Lecture Notes in Computer Science, Vol. 8070). doi: 10.1007/978-3-642-40164-0_9

The Frequent Items Problem in Online Streaming under Various Performance Measures

Abstract

Conference

Documents & Links

Related Activities

19th International Symposium on Fundamentals of Computation Theory

Cite this