The Frequent Items Problem in Online Streaming under Various Performance Measures

Joan Boyar, Kim Skak Larsen, Abyayananda Maiti

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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 languageEnglish
Title of host publicationFundamentals of Computation Theory : 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings
EditorsLeszek Gąsieniec, Frank Wolter
Volume8
PublisherSpringer
Publication date2013
Pages60-71
ISBN (Print)978-3-642-40163-3
ISBN (Electronic)978-3-642-40164-0
DOIs
Publication statusPublished - 2013
Event19th International Symposium on Fundamentals of Computation Theory - Crowne Plaza Hotel, Liverpool, Liverpool, United Kingdom
Duration: 19. Aug 201321. Aug 2013
Conference number: 19

Conference

Conference19th International Symposium on Fundamentals of Computation Theory
Number19
LocationCrowne Plaza Hotel, Liverpool
Country/TerritoryUnited Kingdom
CityLiverpool
Period19/08/201321/08/2013
SeriesLecture Notes in Computer Science
Volume8070
ISSN0302-9743

Fingerprint

Dive into the research topics of 'The Frequent Items Problem in Online Streaming under Various Performance Measures'. Together they form a unique fingerprint.

Cite this