TY - JOUR
T1 - The Frequent Items Problem in Online Streaming Under Various Performance Measures
AU - Boyar, Joan
AU - Larsen, Kim Skak
AU - Maiti, Abyayananda
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
U2 - 10.1142/S0129054115500239
DO - 10.1142/S0129054115500239
M3 - Journal article
SN - 0129-0541
VL - 26
SP - 413
EP - 439
JO - International Journal of Foundations of Computer Science
JF - International Journal of Foundations of Computer Science
IS - 4
ER -