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


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
Publication date2013
ISBN (Print)978-3-642-40163-3
ISBN (Electronic)978-3-642-40164-0
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


Conference19th International Symposium on Fundamentals of Computation Theory
LocationCrowne Plaza Hotel, Liverpool
Country/TerritoryUnited Kingdom
SeriesLecture Notes in Computer Science

Cite this