The Frequent Items Problem in Online Streaming Under Various Performance Measures

Joan Boyar, Kim Skak Larsen, Abyayananda Maiti

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstrakt

This is a contribution to the ongoing study of properties of performance measures for online algorithms. It has long been known that competitive analysis suffers from draw-backs in certain situations, and many alternative measures have been proposed. More systematic comparative studies of performance measures have been initiated recently, and we continue this work, considering competitive analysis, relative interval analysis, and relative worst order analysis on the frequent items problem, a fundamental online streaming problem.
OriginalsprogEngelsk
TidsskriftInternational Journal of Foundations of Computer Science
Vol/bind26
Udgave nummer4
Sider (fra-til)413-439
ISSN0129-0541
DOI
StatusUdgivet - 2015

Citationsformater