The Frequent Items Problem in Online Streaming under Various Performance Measures

Joan Boyar, Kim Skak Larsen, Abyayananda Maiti

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

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.
OriginalsprogEngelsk
TitelFundamentals of Computation Theory : 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings
RedaktørerLeszek Gąsieniec, Frank Wolter
Vol/bind8
ForlagSpringer
Publikationsdato2013
Sider60-71
ISBN (Trykt)978-3-642-40163-3
ISBN (Elektronisk)978-3-642-40164-0
DOI
StatusUdgivet - 2013
Begivenhed19th International Symposium on Fundamentals of Computation Theory - Crowne Plaza Hotel, Liverpool, Liverpool, Storbritannien
Varighed: 19. aug. 201321. aug. 2013
Konferencens nummer: 19

Konference

Konference19th International Symposium on Fundamentals of Computation Theory
Nummer19
LokationCrowne Plaza Hotel, Liverpool
Land/OmrådeStorbritannien
ByLiverpool
Periode19/08/201321/08/2013
NavnLecture Notes in Computer Science
Vol/bind8070
ISSN0302-9743

Emneord

  • online algorithms
  • frequent items problem
  • performance measures

Citationsformater